数据结十大排序之（选排，希尔，插排，堆排）

发布于：2024-12-18 ⋅ 阅读:(11) ⋅ 点赞:(0)
微信交流群：https://732903.hlcode.cn/?id=NK1fWUR

1. 引言

排序算法是计算机科学中最基础的算法之一，它在很多领域都有广泛的应用。例如，在数据存储、搜索引擎、数据库优化、图形渲染等方面，排序都是必不可少的操作。是日常编程任务，还是更复杂的计算问题，理解排序算法的实现与高效性能表现，帮助我们写出更多和优化的程序。

排序算法的种类不同，不同的算法具有不同的时间复杂度、空间复杂度和稳定性特点，适用于不同规模和不同特性的应用场景。学习排序算法，不仅可以加深对算法思想的理解，也可以为解决实际问题提供了更灵活的选择。

本文将重点介绍选择排序（Selection Sort）、希尔排序（Shell Sort）、插入排序（Insertion Sort）和堆排序（Heap Sort）四种常见的排序算法。我们将通过详细分析一个排序算法的原理、实现、时间和空间复杂度，帮助读者深入理解多种算法的优缺点，并结合实际应用场景进行比较。

通过本篇博客，你将能够：

  • 理解排序算法的工作原理和实现方式；
  • 掌握这些排序算法的时间复杂度和空间复杂度；
  • 在实际项目中，根据数据量和排序需求，选择合适的排序算法。

无论你是算法初学者，还是正在为更多的代码优化而努力，掌握这些高效排序算法的核心思想，都让你在算法和编程方面的能力提升大有裨益。

2. 排序算法概述

排序算法是计算机科学中的基础性算法之一，广泛评估数据存储、查询优化、搜索引擎、数据库管理等多个领域。其主要任务是一个无序的元素序列遵循某种规则（如升序）或降序）重新排列，从而使得数据更加小区，随后进行后续的处理和使用。

在不同的应用场景中，排序算法的选择往往受到多种因素的影响，如时间效率、空间效率、算法稳定性、输入数据的特性等。为了解决排序问题，计算机科学家提出了多种不同的排序算法，极限算法在不同的条件下都有其优点和适用场景。

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持 不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳 定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

排序算法有很多种，根据不同的特点，我们可以对它们进行分类。主要的排序算法可以分为以下几类：

  1. 插入排序类
    排序算法通过逐步插入元素来构建排序序列。包括：

    • 插入排序（插入排序）
    • 希尔排序（Shell Sort）

  2. 交换排序类
    排序算法通过交换元素的位置来逐步排序，常见的有：

    • 冒泡排序（Bubble Sort）
    • 快速排序（Quick Sort）

  3. 选择排序
    一类排序算法通过不断选择最小（或最大）元素并进行交换来实现排序，包括：

    • 选择排序（Selection Sort）
    • 堆排序（Heap Sort）

  4. 归并排序类
    排序算法利用分治法的思想，将大问题分解成小问题来流程图。包括：

    • 归并排序（Merge Sort）

  5. 计数排序
    算法适用于整数排序，通过统计每个元素出现的次数来确定其最终位置，包括：

    • 计数排序（计数排序）
    • 基数排序（Radix Sort）
    • 桶排序（Bucket Sort）

本文关注的四种排序算法

在这篇博客中，我们将重点讨论四种常见的排序算法，它们分别是：选择排序、希尔排序、插入排序和堆排序。这四种算法在很多实际场景中都有广泛的应用，并且它们的实现相对简单，容易理解。

  1. 排序（Selection Sort）：每次未排序部分的最小（或最大）元素，放置已排序部分的补充。其实现简单，但时间复杂度同样，适用于小规模数据排序。

  2. 希尔排序（Shell Sort）：插入排序的改进版本，通过分区和递增步长来加速排序过程。它在某些步长序列下面比插入排序更高效，但仍然存在改进空间。

  3. 插入排序（Insertion Sort）：通过构建数组序列，将每个待排序元素插入到已排序部分的适当位置。对于小规模数据，它非常高效，并且在数据部分数组时表现非常优秀。

  4. 堆排序（Heap Sort）：利用堆数据结构，将最大元素（或最小元素）取出来，逐步构建排序序列。它的时间复杂度较稳定，适用于大规模数据的排序。

排序算法核心因素

排序算法的性能和适用性往往依赖于以下几个方面：

  1. 时间复杂度：缓慢算法执行时间随数据规模变化的速率。大多数排序算法的时间复杂度都取决于输入数据的规模（n），例如O(n²)、O(n log n)等。

  2. 空间复杂度：简单算法使用额外空间的多少。对于大多数排序算法，空间复杂度都为O(1)，即原地排序。

  3. 稳定性：一个排序算法是否保持不同的元素之间的相对顺序。稳定性对某些应用（如排序学生成绩时保持相同成绩的学生排序）非常重要。

  4. 适用：场景不同的排序算法在不同的应用场景中效果各异。例如，堆排序适合大规模数据，插入排序适合部分小区的情况，希尔排序适合中小数据规模，选择排序适合小数据量或不关心稳定性的场合。

排序算法的优缺点

  • 选择排序：

    • 优点：实现简单，空间复杂度O(1)，适合小规模数据排序。
    • 缺点：时间复杂度O(n²)，不适合大规模数据排序，且不稳定。

  • 希尔排序：

    • 优点：比插入排序更高效，时间复杂度较低，空间复杂度O(1)，适用于中小型数据。
    • 缺点：不稳定，步长序列的选择对性能影响增大。

  • 安装排序：

    • 优点：实现简单，稳定，适用于小规模数据，且在数据部分小区时效率非常高。
    • 缺点：时间复杂度O(n²)，不适合大规模数据排序。

  • 堆排序：

    • 优点：时间复杂度O(n log n)，稳定性较好，适用于大规模数据排序，且是原地排序。
    • 缺点：突发，且首次快速排序，首次增加。

小结

排序算法的选择补充依赖于算法的时间复杂度，需要考虑实际应用中的数据特性。例如，数据规模较小时，插入排序、选择排序可能简单而高效；而在数据量较大时，堆排序或归并排序等高效算法更加合适。 高精度排序算法有其优势和随身，掌握高精度算法的实现和适用场景，让您在编程时更加得心应手。

接下来，我们将深入探讨选择排序、希尔排序、插入排序和堆排序的详细原理与实现。

3. 常见排序算法的实现

3.1 插入排序

3.1.1基本思想：

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到 一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想。

3.1.2 直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

原理

插入排序的基本思想是：将待排序的元素逐个插入到已经排序的部分中，直到整个队列都成为集群。

  1. 假设第一个元素已经是数组的，从第二个元素开始，依次将每个元素插入到已排序的序列子中。
  2. 对于每个新元素，找到它在已排序部分中应该插入的位置，将其插入，并且保持已排序部分的顺序。
  3. 首先插入操作完成一个元素移动到合适的位置，直到所有元素都被插入到已排序部分，排序。
算法步骤
  1. 从第二个元素开始，假设第一个元素已经是村庄的。
  2. 选择一个待排序元素，将其与已排序部分的元素依次进行比较。
  3. 如果待排序元素小于当前比较元素，就将当前元素移动移动。
  4. 当找到待排序元素应该插入的位置时，将待排序元素插入到该位置。
  5. 重复完成上述过程，直到所有元素排序。

我们从上述视频可以看出插排的思路：

定义两个for  我们每次从 i 下标开始 ，当只有一个元素时，我们认为他是有序的，所以我们要看下一个下标，和前一个值比较 如果大了 就不变 ，小了就交换位置    此时第二个for存储下标j 就从i - 1 开始来便利数组  由此可得：

private static void InsetSor(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int temp = arr[i];
        int j = i - 1;
        for (; j >= 0; j--) {
            if( arr[j] > temp) {
                arr[j+1] = arr[j];
            }
            else {
                arr[j+1] = temp;
                break;
            }
        }
        arr[j+1] = temp;
    }
}

  • 外循环( for (int i = 1; i < arr.length; i++)):

    • 此循环从第二个元素 ( ) 开始遍历数组i = 1。第一个元素 ( arr[0]) 最初被视为数组的“已排序”部分。
    • 此循环的目标是将每个元素插入到数组已排序部分中的正确位置（即索引之前i）。

  • 临时存储（int temp = arr[i];）：

    • 索引处的元素i暂时存储在变量中temp。这是需要插入到数组已排序部分的元素。

  • 内循环（for (; j >= 0; j--)）：

    • 此循环从 开始i - 1并向后进行，比较已排序部分中的每个元素（从索引i-1向下到0）。
    • 这个想法是将大于的元素temp向右移动一个位置，为腾出空间temp。

  • 移动元素( arr[j + 1] = arr[j];):

    • 如果某个元素大于temp( if (arr[j] > temp))，则它会向右移动一个位置 ( arr[j + 1] = arr[j])，从而为 腾出空间temp。

  • 插入temp：

    • 如果元素小于或等于temp（else条件），temp则插入到位置arr[j + 1]。内循环随即中断，因为我们找到了正确的位置temp。

  • temp（arr[j + 1] = temp;）的最终排序：

    • 此行确保将其temp放置在数组排序部分的正确位置。
    • 它解释了小于排序部分所有元素的情况temp，使得j变成-1，temp位于数组的开头（arr[0]）。
静态分析

假设我们有一个仓库[5, 2, 9, 1, 5, 6]，我们将通过插入排序将其排序：

  1. 初始数组：[5, 2, 9, 1, 5, 6]
  2. 第一轮：从第二个元素（2）开始，与第一个元素比较（）5 > 2，将5移至右侧，插入2。[2, 5, 9, 1, 5, 6]
  3. 第二轮：下一个要素是9，9大于5，不需要移动。 存储保持不变：[2, 5, 9, 1, 5, 6]。
  4. 第三轮：元素1与9、、5比较2，将它们逐一移至右侧，插入1。[1, 2, 5, 9, 5, 6]
  5. 第四轮：元素5与9比较，将9移至右侧，再与5比较，不需要移动[1, 2, 5, 5, 9, 6]。
  6. 第五轮：元素6与9比较，将9移至右侧，再与5比较，插入6。库存增加[1, 2, 5, 5, 6, 9]。

排序完成后的备份是：[1, 2, 5, 5, 6, 9]。

 

时间复杂度
  • 最好的情况（备份已经社区）：每个元素仅与前一个元素比较一次，时间复杂度为O(n)。
  • 最坏的情况（吞吐量是逆序的）：每个元素都需要与前面的每个元素比较并移动，时间复杂度为O(n²)。
  • 平均情况：平均需要进行O(n²)次比较和移动。

因此，插入排序的时间复杂度在最差情况下是O(n²)，在最好情况下是O(n)，平均情况下也是O(n²)。

空间复杂度

插入排序是原地排序算法，不需要额外的存储空间。它只需要常量空间来存储临时变量，因此空间复杂度为O(1)。

稳定性

插入排序是一种稳定的排序算法。因为在插入元素时，如果有两个元素满足，插入排序不会改变它们的相对位置。

优缺点

优点：

  • 简单易实现：插入排序算法非常插入且易于实现。
  • 适用于部分集群的吞吐量：如果输入阵列已经接近集群，插入排序的表现会高效，接近 O(n) 的时间复杂度。
  • 稳定性：插入排序是稳定的，能够保持多个元素的相对顺序。

缺点：

  • 时间复杂度较高：最坏的情况下，插入排序的时间复杂度为O(n²)，不适合处理大规模数据。
  • 不适合大规模数据排序：在处理大量数据时，插入排序的效率较低，尤其是在逆序或大部分无序时，性能明显下降。
适用场景

插入排序适用于以下场景：

  • 数据量变小：当数据量变小或者已经接近小区时，插入排序的性能非常好。
  • 部分小区的数据：如果数据本身已经接近小区，插入排序可以快速完成排序。
  • 在线排序：在一些实时系统中，插入排序可以逐个插入新数据并保留分组，适合在线（实时）排序。

希尔排序（Shell Sort）

尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组， 所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达 =1时，所有记录在统一组内排好序。

原理

希尔排序的核心思想是通过分组插入排序来对数据进行排序。具体来说，希尔排序首先将整个待排序数组分成若干个小的子序列（这些子序列之间的间隔由步长序列决定），然后在每个子序列上分别进行插入排序。通过逐步减少步长，使得最终整个数组被排序。

其基本步骤如下：

  1. 初始化步长：首先选择一个步长序列（通常是从大到小的数字序列），常见的序列有 n/2,n/4,…,1n/2, n/4, \dots, 1n/2,n/4,…,1，其中 nnn 是数组的长度。
  2. 分组插入排序：按照当前步长将数组划分为若干个子序列，并在每个子序列上进行插入排序。每个子序列中的元素按照步长距离排序。
  3. 减小步长：步长逐渐减小（通常是每次将步长减半），直到步长为 1 时，对整个数组进行一次插入排序，最终完成排序。

希尔排序通过较大的步长来进行初步排序，逐步减小步长，使得大部分数据能尽早被排序，最终使插入排序的效率大大提高。

算法步骤
  1. 选择一个步长序列 gapgapgap，通常是 n/2,n/4,…,1n/2, n/4, \dots, 1n/2,n/4,…,1。
  2. 按照步长将数组分成若干个子序列。
  3. 对每个子序列进行插入排序。
  4. 重复上述步骤，直到步长为 1 时，对整个数组进行插入排序。

private static void ShellSort(int[] arr, int length) {
    int gep = length ;
    while (gep > 1) {
        gep /=2;
        shell(arr, gep);
    }
}

private static void shell(int[] arr, int get) {
      for (int i = get; i < arr.length; i++) {// 从索引 get 开始遍历 
      int temp = arr[i]; // 保存当前元素 
      int j = i - get; // 计算出和当前元素的间隔位置
            for (; j >= 0; j -= get) { // 从当前位置向左遍历，间隔为 get 
               if (arr[j] > temp) { // 如果前面的元素大于当前元素 
                         arr[j + get] = arr[j]; // 将当前元素向右移动 
                   } else {
                        arr[j + get] = temp; // 找到合适位置后，插入当前元素 
                        break;
                          } 
                      } 
                     arr[j + get] = temp; // 插入当前元素到合适的位置 
                 } 
           }

ShellSort 方法

  • gep = length：初始化间隔 gep 为数组的长度。
  • while (gep > 1)：这个循环会持续执行直到 gep 小于或等于 1。每次执行时，gep 会减半。
  • gep /= 2：在每次迭代中，将间隔 gep 除以 2，从而逐渐减小增量。
  • shell(arr, gep)：每次减小增量后，调用 shell 方法来执行插入排序。这里是逐步优化插入排序的过程，通过增量间隔分组进行排序。

shell 方法

  • for (int i = get; i < arr.length; i++)：从 get 开始遍历数组。get 是当前的增量，也就是我们当前分组的大小。起始位置是 get，因为之前的小组已经经过排序。
  • int temp = arr[i]：保存当前要插入的元素 arr[i]，以便后续比较和插入。
  • int j = i - get：计算出 j 的位置，即 i 对应的元素在当前增量下的分组对应的左边的元素。
  • for (; j >= 0; j -= get)：向左遍历元素，间隔为 get，比较当前元素与左侧元素的大小。
  • if (arr[j] > temp)：如果左侧元素比当前元素大，则将左侧元素右移，为当前元素腾出位置。
  • arr[j + get] = temp;：一旦找到合适的位置（即左侧元素不再大于当前元素），将 temp 放入该位置。
  • arr[j + get] = temp;：如果 j 没有变成负数，则在 j + get 位置插入 temp。
静态分析

假设我们有一个仓库[5, 2, 9, 1, 5, 6]，使用希尔排序来进行排序：

  1. 初始数组：[5, 2, 9, 1, 5, 6]
  2. 第一轮（步长为3）：
    • 分组：[5, 1]，[2, 5]，[9, 6]
    • 对每个子序列进行插入排序：
      • [5, 1]排序后为[1, 5]
      • [2, 5]排序后为[2, 5]
      • [9, 6]排序后为[6, 9]
    • 排序后的阵列为：[1, 2, 6, 5, 5, 9]
  3. 第二轮（步长为1）：
    • 此时仓库已经接近社区，执行一次插入排序：
      • 排序后的阵列为：[1, 2, 5, 5, 6, 9]

最终结果为：[1, 2, 5, 5, 6, 9]。

时间复杂度

希尔排序的时间复杂度受步长序列的影响，不同的步长序列导致不同的时间复杂度：

  • 最坏情况时间复杂度：根据不同的步长序列，最坏情况下希尔排序的时间复杂度为 O(n2)O(n^2)O(n2)，但是通过选取合适的步长序列，时间复杂度可以得到显著的改善。
  • 最佳情况时间复杂度：如果数组已经有序，时间复杂度为 O(n)O(n)O(n)，因为最终步长为 1 时进行的是插入排序，插入排序对于已排序数据是最优的。
  • 平均情况时间复杂度：根据不同的步长序列，平均时间复杂度通常为 O(n3/2)O(n^{3/2})O(n3/2) 到 O(nlog⁡n)O(n \log n)O(nlogn) 之间。

常见的步长序列有：

  • Hibbard 序列（步长为 1,3,7,15,…1, 3, 7, 15, \dots1,3,7,15,…），最坏情况下时间复杂度为 O(n3/2)O(n^{3/2})O(n3/2)。
  • Sedgewick 序列（步长为 1,5,19,41,…1, 5, 19, 41, \dots1,5,19,41,…），在实际应用中表现较好，时间复杂度较优。
空间复杂度

希尔排序是原地排序算法，其空间复杂度为 O(1)，因为它只需要常数空间来存储临时变量。

稳定性

希尔排序不稳定。因为在分组插入排序过程中，相同的元素可能会改变相对顺序。

优缺点

优点：

  • 比插入排序更高效：通过减小元素间的间隔，希尔排序在大多数情况下比插入排序更快，尤其是数据量较大时。
  • 原地排序：空间复杂度为 O(1)，没有额外的内存开销。
  • 可以改善插入排序的效率：希尔排序通过步长的引入，使得数据在排序过程中更为分散，减少了插入排序的“交换次数”。

缺点：

  • 不稳定：由于步长的引入，相同元素的相对顺序可能被打乱，希尔排序是一个不稳定的排序算法。
  • 依赖步长序列：不同的步长序列会导致不同的性能表现，选择合适的步长序列至关重要。
  • 最坏时间复杂度较高：在一些步长序列下，最坏情况下的时间复杂度可能仍然接近 O(n²)。
适用场景

希尔排序适用于：

  • 中等规模的数据排序：当数据规模较大时，插入排序效率较低，希尔排序通过引入步长序列改善了效率，适合处理中等规模的数据。
  • 在线排序：与插入排序类似，希尔排序也可以用于数据流中的实时排序（即实时处理和插入新数据）。

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很 快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排 序的时间复杂度都不固定：

3.2 选择排序

3.2.1 基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元 素排完 。

3.2.2 直接选择排序:

在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素

若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换

在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

原理

直接选择排序的基本思想是：

  1. 假设待排序数组的第一个元素已被排序。
  2. 在剩下的元素中找到最小（或最大）的元素，将其与已排序部分的最后一个元素交换位置。
  3. 重复上述过程，直到所有元素都被排序。

具体来说，直接选择排序可以分为以下步骤：

  1. 从未排序部分中选择最小（或最大）的元素。
  2. 将这个元素与未排序部分的第一个元素交换位置，使得已排序部分的元素增加一位。
  3. 逐步缩小未排序部分，直到所有元素都被排序。
算法步骤
  1. 初始状态：将数组分为已排序部分和未排序部分，开始时已排序部分为空，未排序部分是整个数组。
  2. 从未排序部分中选择最小元素，将其与未排序部分的第一个元素交换位置。
  3. 将已排序部分扩大，未排序部分缩小，继续选择未排序部分中的最小元素并交换。
  4. 重复上述步骤，直到未排序部分为空，排序完成。

private static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {  // 遍历数组的每个元素
        int min = i;  // 假设当前位置的元素是最小的
        for (int j = i + 1; j < arr.length; j++) {  // 从当前位置 i 后面的元素中找最小的
            if (arr[j] < arr[min]) {  // 如果找到了比当前 min 更小的元素
                min = j;  // 更新 min
            }
        }
        swap(arr, i, min);  // 将当前位置的元素与最小元素交换
    }
}

private static void swap(int[] arr, int i, int min) {
    int temp = arr[i];
    arr[i] = arr[min];
    arr[min] = temp;
}

selectSort 方法

  • 外层循环 (for (int i = 0; i < arr.length; i++))：
    • 外层循环遍历整个数组，从第一个元素到最后一个元素。i 代表当前正在处理的元素索引。
  • min 变量：
    • 每次内层循环开始时，我们假设当前位置的元素是最小的，因此将 min 初始化为 i（当前外层循环的索引）。接下来，我们通过内层循环检查是否存在比当前 arr[min] 更小的元素。
  • 内层循环 (for (int j = i + 1; j < arr.length; j++))：
    • 内层循环从 i + 1 开始遍历剩余的未排序元素，比较它们和当前最小元素。如果找到了更小的元素，就更新 min 为该元素的索引。
  • 交换操作 (swap(arr, i, min))：
    • 每次内层循环结束后，min 存储了当前范围内最小元素的索引。然后，我们将当前元素 arr[i] 与最小元素 arr[min] 交换位置。这样，数组的前部分始终保持有序。

swap 方法

交换操作：swap 方法用于交换 arr[i] 和 arr[min] 两个元素。它使用一个临时变量 temp 来存储 arr[i] 的值，然后将 arr[min] 的值赋给 arr[i]，最后再将 temp（原 arr[i] 的值）赋给 arr[min]，完成两者的交换。

静态展示

假设我们有一个仓库[64, 25, 12, 22, 11]，使用直接选择排序进行排序：

  1. 初始数组：[64, 25, 12, 22, 11]
  2. 第一轮：[64, 25, 12, 22, 11]计算选择最小元素11，将其与第一个元素64交换，然后[11, 25, 12, 22, 64]。
  3. 第二轮：[25, 12, 22, 64]其余选择最小元素12，将其与第一个元素25交换，然后[11, 12, 25, 22, 64]。
  4. 第三轮：[25, 22, 64]计算选择最小元素22，将其与第一个元素25交换，然后[11, 12, 22, 25, 64]。
  5. 第四轮：[25, 64]所需选择最小要素25，需要交换，储备保持保证：[11, 12, 22, 25, 64]。
  6. 排序完成：最终结果为[11, 12, 22, 25, 64]。

 

时间复杂度

  • 时间复杂度：

    • 最坏情况、最好情况和平均情况的时间复杂度都是 O(n²)，因为需要对每个元素执行一次选择操作，每次选择操作中又需要扫描剩余的元素。

    • 具体来说，对于每个元素，选择最小元素需要遍历剩余 n−1n - 1n−1 个元素；对第二个元素需要遍历 n−2n - 2n−2 个元素，依此类推。所以总的比较次数为：

    总比较次数=(n−1)+(n−2)+⋯+1=n(n−1)2≈O(n2)\text{总比较次数} = (n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2} \approx O(n^2)总比较次数=(n−1)+(n−2)+⋯+1=2n(n−1)​≈O(n2)

  • 空间复杂度：

    • 选择排序是原地排序算法，不需要额外的存储空间，因此空间复杂度为 O(1)。
  • 稳定性：
    • 直接选择排序不稳定。因为在选择最小元素时，如果遇到相等的元素，它们的相对顺序可能会发生变化。例如，如果 array[i] 和 array[j] 的值相同，但 i 小于 j，那么交换操作可能会改变它们的相对顺序。
优缺点

优点：

  • 实现简单：直接选择排序的算法非常简单，容易理解和实现。
  • 空间复杂度低：它是原地排序算法，不需要额外的存储空间。

缺点：

  • 时间复杂度较高：由于其时间复杂度为 O(n2)O(n^2)O(n2)，在大数据量时性能较差。
  • 不稳定：直接选择排序是一个不稳定的排序算法，相等元素的相对顺序可能会改变。
适用场景
  • 小数据量排序：由于直接选择排序的时间复杂度较高，因此它通常用于处理小数据量的排序问题。
  • 内存受限的场合：选择排序是一种原地排序算法，适合在内存受限的环境中使用，因为它只需要常数空间。

   堆排

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆 来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

堆排序（Heap Sort）是一种基于堆数据结构的排序算法。它的基本思想是利用堆的特性（通常是最大堆或最小堆）来进行排序。堆排序首先将输入数据构建成一个堆结构，然后通过不断地交换根节点与最后一个节点，缩小堆的范围，逐步实现排序。由于堆排序是一个不稳定的排序算法，但它具有较好的时间复杂度。

堆的概念

在堆排序之前，我们需要理解“堆”这一数据结构。堆是一种完全二叉树，具有以下特点：

  • 最大堆：在最大堆中，每个父节点的值都大于或等于其子节点的值，即根节点的值是最大值。
  • 最小堆：在最小堆中，每个父节点的值都小于或等于其子节点的值，即根节点的值是最小值。

堆排序通常使用最大堆来进行排序，利用堆的性质来逐步将最大值移动到数组的末尾，最终得到有序数组。

堆排序的基本思想

堆排序的核心思想是：

  1. 构建最大堆：首先将给定的无序数组构建成一个最大堆。最大堆的性质是根节点的值最大。
  2. 交换根节点与最后一个节点：将堆顶元素（最大元素）与堆的最后一个元素交换，然后将堆的有效元素数量减少 1。
  3. 调整堆：将新的根节点进行调整，使其满足最大堆的性质。通过“堆化”过程，将交换后的元素重新调整为堆结构。
  4. 重复以上过程：每次交换堆顶元素与最后一个元素后，减少堆的大小，再进行堆化操作，直到堆的大小为 1，排序完成。
堆排序的算法步骤
  1. 构建最大堆：将输入数组构建为最大堆。对于一个索引为 i 的元素，它的左右子节点分别为 2i + 1 和 2i + 2，父节点为 i。
  2. 交换堆顶元素与最后一个元素：将堆顶元素与堆的最后一个元素交换，并且减少堆的大小。
  3. 堆化：从堆顶开始，通过调整堆的结构（即“堆化”操作）使其重新符合最大堆的性质。
  4. 重复过程：重复上述步骤，直到堆的大小为 1，排序完成。

主要流程

堆排序的核心思想是将输入数组构建成一个最大堆（或最小堆），然后通过反复交换堆顶元素与最后一个元素，并对堆进行调整，最终得到排序后的数组。

  • 构建堆：首先，将数组构建成一个最大堆（或最小堆）。
  • 交换堆顶元素与最后一个元素：将最大堆的根节点与最后一个元素交换。
  • 调整堆：去掉堆顶元素后，对剩余部分调整堆的结构，保持最大堆性质。
  • 重复操作：继续交换堆顶元素和剩余部分的最后一个元素，并调整堆，直到所有元素排序完成。

private static void pileSort(int[] arr) {
    for (int pvl = (arr.length-1-1)/2; pvl >=0; pvl--) {
        shiftdown(arr,pvl,arr.length);
    }
    int right = arr.length-1;
    while (right > 0) {
        swap(arr,0,right);
        shiftdown(arr,0,right);
        right--;

    }
}

private static void shiftdown(int[] arr, int pvl,int length) {
    int child = pvl*2+1;
    while (child < length) {
        if (child + 1 < length && arr[child] < arr[child+1] ) {
            child++;
        }
        if (arr[child] > arr[pvl]) {
            swap(arr,pvl,child);
            pvl = child;
            child = pvl*2+1;
        }else {
            break;
        }
    }
}

pileSort 方法

  • for (int pvl = (arr.length - 1 - 1) / 2; pvl >= 0; pvl--)：这段代码是为了从最后一个非叶子节点开始，逐层调整堆，使其满足堆的性质。(arr.length - 1 - 1) / 2 是最后一个非叶子节点的索引（完全二叉树的性质），从这里开始向上逐层调整堆。

    • 完全二叉树的性质告诉我们，数组索引为 i 的节点的左子节点索引为 2i + 1，右子节点索引为 2i + 2。
    • 对于数组索引 i，如果 i >= (arr.length - 1) / 2，说明该节点是叶子节点，不需要进行调整。

  • shiftdown(arr, pvl, arr.length)：这个方法负责将元素 arr[pvl] 向下调整，使得它满足堆的性质（最大堆）。

  • int right = arr.length - 1;：right 用来指示当前堆的有效范围，开始时指向数组的最后一个元素。

  • while (right > 0)：这个循环是核心的堆排序部分，在堆排序过程中，堆顶元素（最大元素）与数组的最后一个元素交换，交换后需要通过 shiftdown 恢复堆的性质，然后缩小有效堆的范围（right--）。

shiftdown 方法

  • int child = pvl * 2 + 1;：根据堆的性质，当前节点 pvl 的左子节点的索引是 pvl * 2 + 1。
  • while (child < length)：检查当前子节点是否有效，如果 child 超出了堆的范围，则结束调整过程。
  • if (child + 1 < length && arr[child] < arr[child + 1]) { child++; }：如果右子节点存在且大于左子节点，则将 child 更新为右子节点的索引，目的是选择较大的子节点进行交换。
  • if (arr[child] > arr[pvl])：如果子节点的值大于父节点的值，则交换它们。交换后，更新 pvl 为子节点的位置，并计算新的子节点位置。
  • else { break; }：如果子节点不大于父节点，则无需交换，跳出循环。
静态分析：

假设我们有一个仓库[4, 10, 3, 5, 1]，我们通过堆排序对其进行排序：

  1. 构建最大堆：最终仓库：[4, 10, 3, 5, 1]

    从最后一个非叶子节点开始，依次进行堆化操作：

    • 对索引i=1进行堆化，arr[1]是父节点，arr[3]和arr[4]是它的子节点。堆化后队列为：[4, 10, 3, 5, 1]。
    • 对索引i=0进行堆化，arr[0]是根节点，arr[1]和arr[2]是它的子节点。堆化后栈为：[10, 5, 3, 4, 1]。

  2. 交换堆顶元素与最后一个元素：

    • 交换arr[0]和arr[4]，得到[1, 5, 3, 4, 10]。
    • 调整堆，进行堆化，得到：[5, 4, 3, 1, 10]。

  3. 重复交换和堆化过程：

    • 交换arr[0]和arr[3]，得到[1, 4, 3, 5, 10]，然后进行堆化，得到[4, 1, 3, 5, 10]。
    • 交换arr[0]和arr[2]，得到[3, 1, 4, 5, 10]，然后进行堆化，得到[3, 1, 4, 5, 10]。
    • 交换arr[0]和arr[1]，得到[1, 3, 4, 5, 10]，然后进行堆化，得到[1, 3, 4, 5, 10]。
    • 最终是：[1, 3, 4, 5, 10]，排序完成。
时间复杂度

  • 构建堆：构建最大堆的时间复杂度为O(n)，因为我们从最后一个非叶子节点开始进行堆化，每次堆化操作的时间复杂度为O(log n)，总的时间复杂度是 O(n)。

  • 交换和化堆：每次交换堆顶元素与补充元素后，都需要进行堆化，我们堆化的时间复杂度是O(log n)。在最坏的情况下，需要进行n-1次堆化操作。因此，交换和堆积的总时间复杂度为 O(n log n)。

  • 总时间复杂度：由于构建堆的时间复杂度为 O(n)，交换和堆化的时间复杂度为 O(n log n)，因此堆排序的总时间复杂度为O(n log n)。

空间复杂度
  • 堆排序是原地排序算法，它只需要空间来存储临时变量，因此空间复杂度为O(1)。
稳定性

堆排序不稳定。在堆化过程中，相同值的元素的相对顺序可能会被改变，因此堆排序不是稳定的排序算法。

优缺点

优点：

  • 时间复杂度如下：堆排序的最差时间复杂度是O(n log n)，并且是稳定的，不受输入数据的影响。
  • 空间复杂度低：堆排序是原地排序算法，不需要额外的存储空间。
  • 适用于大规模数据：由于堆排序的时间复杂度为O(n log n)，在处理大规模数据时性能较好。

缺点：

  • 不稳定：堆排序不稳定，可能会改变相同元素的相对顺序。
  • 帕克增量：虽然时间复杂度是 O(n log n)，但由于堆排序的帕克速度增量，它的实际运行可能不如排序等其他 O(n log n) 算法。
适用场景

堆排序适用于以下场景：

  • 大规模数据的排序：当处理大规模数据时，堆排序提供了一个较好的解决方案，尤其是在内存空间设定的环境下。
  • 优先队列的实现：堆结构广泛用于实现优先队列，堆排序可以作为优先队列的一种实现方式。

4. 总结

排序算法是计算机科学中非常重要的一类算法，不仅在理论上具有广泛的应用，也在实践中经常遇到。在本篇文章中，我们详细探讨了几种经典的排序算法，包括选择排序、插入排序、希尔排序和堆排序。坐标排序算法都有其独特的实现方式、时间复杂度、空间复杂度以及适用场景。通过对这些算法的分析，我们可以看到，不同的排序方法在不同情况下的表现差异，如何选择合适的排序算法在实际应用中至关重要。

  • 选择排序：实现简单，但时间复杂度较高，适合小规模数据的排序。
  • 插入排序：同样适合小规模数据，尤其是当数据近乎小区时表现非常高效。
  • 希尔排序：通过优化插入排序的方式在大多数情况下表现相当，但其稳定性较差。
  • 堆排序：在时间复杂度上表现良好，适合大规模数据排序，但尚未达到增量增量。

在选择排序算法时，需要考虑数据规模、数据的初始状态（是否接近分组）以及算法的稳定性要求等因素。在实际应用中，有很多高级排序算法，如快速排序、归并排序和计数等排序，能够提供更高效的排序效果。而对于一些特定的场景，经典的排序算法如堆排序仍然发挥着重要的作用。

总之，了解各种排序算法的特点和应用场景，能够帮助我们在不同的条件下做出最优化的选择，为解决实际问题提供更、实用的解决方案。希望通过本篇文章的讲解，能够帮助读者更好地理解排序算法，为日后的算法学习和实践打下坚实的基础。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布