1. 引言排序算法是计算机科学中最基础的算法之一它在很多领域都有广泛的应用。例如在数据存储、搜索引擎、数据库优化、图形渲染等方面排序都是必不可少的操作。是日常编程任务还是更复杂的计算问题理解排序算法的实现与高效性能表现帮助我们写出更多和优化的程序。排序算法的种类不同不同的算法具有不同的时间复杂度、空间复杂度和稳定性特点适用于不同规模和不同特性的应用场景。学习排序算法不仅可以加深对算法思想的理解也可以为解决实际问题提供了更灵活的选择。本文将重点介绍选择排序Selection Sort、希尔排序Shell Sort、插入排序Insertion Sort和堆排序Heap Sort四种常见的排序算法。我们将通过详细分析一个排序算法的原理、实现、时间和空间复杂度帮助读者深入理解多种算法的优缺点并结合实际应用场景进行比较。通过本篇博客你将能够理解排序算法的工作原理和实现方式掌握这些排序算法的时间复杂度和空间复杂度在实际项目中根据数据量和排序需求选择合适的排序算法。无论你是算法初学者还是正在为更多的代码优化而努力掌握这些高效排序算法的核心思想都让你在算法和编程方面的能力提升大有裨益。2. 排序算法概述排序算法是计算机科学中的基础性算法之一广泛评估数据存储、查询优化、搜索引擎、数据库管理等多个领域。其主要任务是一个无序的元素序列遵循某种规则如升序或降序重新排列从而使得数据更加小区随后进行后续的处理和使用。在不同的应用场景中排序算法的选择往往受到多种因素的影响如时间效率、空间效率、算法稳定性、输入数据的特性等。为了解决排序问题计算机科学家提出了多种不同的排序算法极限算法在不同的条件下都有其优点和适用场景。排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持 不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳 定的否则称为不稳定的。内部排序数据元素全部放在内存中的排序。外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。排序算法有很多种根据不同的特点我们可以对它们进行分类。主要的排序算法可以分为以下几类插入排序类排序算法通过逐步插入元素来构建排序序列。包括插入排序插入排序希尔排序Shell Sort交换排序类排序算法通过交换元素的位置来逐步排序常见的有冒泡排序Bubble Sort快速排序Quick Sort选择排序一类排序算法通过不断选择最小或最大元素并进行交换来实现排序包括选择排序Selection Sort堆排序Heap Sort归并排序类排序算法利用分治法的思想将大问题分解成小问题来流程图。包括归并排序Merge Sort计数排序算法适用于整数排序通过统计每个元素出现的次数来确定其最终位置包括计数排序计数排序基数排序Radix Sort桶排序Bucket Sort本文关注的四种排序算法在这篇博客中我们将重点讨论四种常见的排序算法它们分别是选择排序、希尔排序、插入排序和堆排序。这四种算法在很多实际场景中都有广泛的应用并且它们的实现相对简单容易理解。选择排序Selection Sort每次未排序部分的最小或最大元素放置已排序部分的补充。其实现简单但时间复杂度同样适用于小规模数据排序。希尔排序Shell Sort插入排序的改进版本通过分区和递增步长来加速排序过程。它在某些步长序列下面比插入排序更高效但仍然存在改进空间。插入排序Insertion Sort通过构建数组序列将每个待排序元素插入到已排序部分的适当位置。对于小规模数据它非常高效并且在数据部分数组时表现非常优秀。堆排序Heap Sort利用堆数据结构将最大元素或最小元素取出来逐步构建排序序列。它的时间复杂度较稳定适用于大规模数据的排序。排序算法核心因素排序算法的性能和适用性往往依赖于以下几个方面时间复杂度缓慢算法执行时间随数据规模变化的速率。大多数排序算法的时间复杂度都取决于输入数据的规模n例如O(n²)、O(n log n)等。空间复杂度简单算法使用额外空间的多少。对于大多数排序算法空间复杂度都为O(1)即原地排序。稳定性一个排序算法是否保持不同的元素之间的相对顺序。稳定性对某些应用如排序学生成绩时保持相同成绩的学生排序非常重要。适用场景不同的排序算法在不同的应用场景中效果各异。例如堆排序适合大规模数据插入排序适合部分小区的情况希尔排序适合中小数据规模选择排序适合小数据量或不关心稳定性的场合。排序算法的优缺点选择排序优点实现简单空间复杂度O(1)适合小规模数据排序。缺点时间复杂度O(n²)不适合大规模数据排序且不稳定。希尔排序优点比插入排序更高效时间复杂度较低空间复杂度O(1)适用于中小型数据。缺点不稳定步长序列的选择对性能影响增大。插入排序优点实现简单稳定适用于小规模数据且在数据部分小区时效率非常高。缺点时间复杂度O(n²)不适合大规模数据排序。堆排序优点时间复杂度O(n log n)稳定性较好适用于大规模数据排序且是原地排序。缺点突发且首次快速排序首次增加。小结排序算法的选择补充依赖于算法的时间复杂度需要考虑实际应用中的数据特性。例如数据规模较小时插入排序、选择排序可能简单而高效而在数据量较大时堆排序或归并排序等高效算法更加合适。 高精度排序算法有其优势和随身掌握高精度算法的实现和适用场景让您在编程时更加得心应手。接下来我们将深入探讨选择排序、希尔排序、插入排序和堆排序的详细原理与实现。3. 常见排序算法的实现3.1 插入排序3.1.1基本思想直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到 一个新的有序序列 。实际中我们玩扑克牌时就用了插入排序的思想。3.1.2 直接插入排序当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移原理插入排序的基本思想是将待排序的元素逐个插入到已经排序的部分中直到整个队列都成为集群。假设第一个元素已经是数组的从第二个元素开始依次将每个元素插入到已排序的序列子中。对于每个新元素找到它在已排序部分中应该插入的位置将其插入并且保持已排序部分的顺序。首先插入操作完成一个元素移动到合适的位置直到所有元素都被插入到已排序部分排序。算法步骤从第二个元素开始假设第一个元素已经是最小的。选择一个待排序元素将其与已排序部分的元素依次进行比较。如果待排序元素小于当前比较元素就将当前元素移动移动。当找到待排序元素应该插入的位置时将待排序元素插入到该位置。重复完成上述过程直到所有元素排序。我们从上述视频可以看出插排的思路定义两个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[j1] arr[j]; } else { arr[j1] temp; break; } } arr[j1] 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如果元素小于或等于tempelse条件temp则插入到位置arr[j 1]。内循环随即中断因为我们找到了正确的位置temp。temparr[j 1] temp;的最终排序此行确保将其temp放置在数组排序部分的正确位置。它解释了小于排序部分所有元素的情况temp使得j变成-1temp位于数组的开头arr[0]。静态分析假设我们有一个数组[5, 2, 9, 1, 5, 6]我们将通过插入排序将其排序初始数组[5, 2, 9, 1, 5, 6]第一轮从第二个元素2开始与第一个元素比较 5 2将5移至右侧插入2。[2, 5, 9, 1, 5, 6]第二轮下一个要素是99大于5不需要移动。 存储保持不变[2, 5, 9, 1, 5, 6]。第三轮元素1与9、、5比较2将它们逐一移至右侧插入1。[1, 2, 5, 9, 5, 6]第四轮元素5与9比较将9移至右侧再与5比较不需要移动[1, 2, 5, 5, 9, 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时所有记录在统一组内排好序。原理希尔排序的核心思想是通过分组插入排序来对数据进行排序。具体来说希尔排序首先将整个待排序数组分成若干个小的子序列这些子序列之间的间隔由步长序列决定然后在每个子序列上分别进行插入排序。通过逐步减少步长使得最终整个数组被排序。其基本步骤如下初始化步长首先选择一个步长序列通常是从大到小的数字序列常见的序列有 n/2,n/4,…,1n/2, n/4, \dots, 1n/2,n/4,…,1其中 nnn 是数组的长度。分组插入排序按照当前步长将数组划分为若干个子序列并在每个子序列上进行插入排序。每个子序列中的元素按照步长距离排序。减小步长步长逐渐减小通常是每次将步长减半直到步长为 1 时对整个数组进行一次插入排序最终完成排序。希尔排序通过较大的步长来进行初步排序逐步减小步长使得大部分数据能尽早被排序最终使插入排序的效率大大提高。算法步骤选择一个步长序列 gapgapgap通常是 n/2,n/4,…,1n/2, n/4, \dots, 1n/2,n/4,…,1。按照步长将数组分成若干个子序列。对每个子序列进行插入排序。重复上述步骤直到步长为 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]使用希尔排序来进行排序初始数组[5, 2, 9, 1, 5, 6]第一轮步长为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]第二轮步长为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(nlogn)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[i1]--array[n-1]集合中重复上述步骤直到集合剩余1个元素原理直接选择排序的基本思想是假设待排序数组的第一个元素已被排序。在剩下的元素中找到最小或最大的元素将其与已排序部分的最后一个元素交换位置。重复上述过程直到所有元素都被排序。具体来说直接选择排序可以分为以下步骤从未排序部分中选择最小或最大的元素。将这个元素与未排序部分的第一个元素交换位置使得已排序部分的元素增加一位。逐步缩小未排序部分直到所有元素都被排序。算法步骤初始状态将数组分为已排序部分和未排序部分开始时已排序部分为空未排序部分是整个数组。从未排序部分中选择最小元素将其与未排序部分的第一个元素交换位置。将已排序部分扩大未排序部分缩小继续选择未排序部分中的最小元素并交换。重复上述步骤直到未排序部分为空排序完成。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]使用直接选择排序进行排序初始数组[64, 25, 12, 22, 11]第一轮[64, 25, 12, 22, 11]计算选择最小元素11将其与第一个元素64交换然后[11, 25, 12, 22, 64]。第二轮[25, 12, 22, 64]其余选择最小元素12将其与第一个元素25交换然后[11, 12, 25, 22, 64]。第三轮[25, 22, 64]计算选择最小元素22将其与第一个元素25交换然后[11, 12, 22, 25, 64]。第四轮[25, 64]所需选择最小要素25需要交换储备保持保证[11, 12, 22, 25, 64]。排序完成最终结果为[11, 12, 22, 25, 64]。时间复杂度时间复杂度最坏情况、最好情况和平均情况的时间复杂度都是O(n²)因为需要对每个元素执行一次选择操作每次选择操作中又需要扫描剩余的元素。具体来说对于每个元素选择最小元素需要遍历剩余 n−1n - 1n−1 个元素对第二个元素需要遍历 n−2n - 2n−2 个元素依此类推。所以总的比较次数为总比较次数(n−1)(n−2)⋯1n(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)⋯12n(n−1)≈O(n2)空间复杂度选择排序是原地排序算法不需要额外的存储空间因此空间复杂度为O(1)。稳定性直接选择排序不稳定。因为在选择最小元素时如果遇到相等的元素它们的相对顺序可能会发生变化。例如如果array[i]和array[j]的值相同但i小于j那么交换操作可能会改变它们的相对顺序。优缺点优点实现简单直接选择排序的算法非常简单容易理解和实现。空间复杂度低它是原地排序算法不需要额外的存储空间。缺点时间复杂度较高由于其时间复杂度为 O(n2)O(n^2)O(n2)在大数据量时性能较差。不稳定直接选择排序是一个不稳定的排序算法相等元素的相对顺序可能会改变。适用场景小数据量排序由于直接选择排序的时间复杂度较高因此它通常用于处理小数据量的排序问题。内存受限的场合选择排序是一种原地排序算法适合在内存受限的环境中使用因为它只需要常数空间。堆排堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆 来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。堆排序Heap Sort是一种基于堆数据结构的排序算法。它的基本思想是利用堆的特性通常是最大堆或最小堆来进行排序。堆排序首先将输入数据构建成一个堆结构然后通过不断地交换根节点与最后一个节点缩小堆的范围逐步实现排序。由于堆排序是一个不稳定的排序算法但它具有较好的时间复杂度。堆的概念在堆排序之前我们需要理解“堆”这一数据结构。堆是一种完全二叉树具有以下特点最大堆在最大堆中每个父节点的值都大于或等于其子节点的值即根节点的值是最大值。最小堆在最小堆中每个父节点的值都小于或等于其子节点的值即根节点的值是最小值。堆排序通常使用最大堆来进行排序利用堆的性质来逐步将最大值移动到数组的末尾最终得到有序数组。堆排序的基本思想堆排序的核心思想是构建最大堆首先将给定的无序数组构建成一个最大堆。最大堆的性质是根节点的值最大。交换根节点与最后一个节点将堆顶元素最大元素与堆的最后一个元素交换然后将堆的有效元素数量减少 1。调整堆将新的根节点进行调整使其满足最大堆的性质。通过“堆化”过程将交换后的元素重新调整为堆结构。重复以上过程每次交换堆顶元素与最后一个元素后减少堆的大小再进行堆化操作直到堆的大小为 1排序完成。堆排序的算法步骤构建最大堆将输入数组构建为最大堆。对于一个索引为i的元素它的左右子节点分别为2i 1和2i 2父节点为i。交换堆顶元素与最后一个元素将堆顶元素与堆的最后一个元素交换并且减少堆的大小。堆化从堆顶开始通过调整堆的结构即“堆化”操作使其重新符合最大堆的性质。重复过程重复上述步骤直到堆的大小为 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*21; while (child length) { if (child 1 length arr[child] arr[child1] ) { child; } if (arr[child] arr[pvl]) { swap(arr,pvl,child); pvl child; child pvl*21; }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]我们通过堆排序对其进行排序构建最大堆最终数组[4, 10, 3, 5, 1]从最后一个非叶子节点开始依次进行堆化操作对索引i1进行堆化arr[1]是父节点arr[3]和arr[4]是它的子节点。堆化后队列为[4, 10, 3, 5, 1]。对索引i0进行堆化arr[0]是根节点arr[1]和arr[2]是它的子节点。堆化后栈为[10, 5, 3, 4, 1]。交换堆顶元素与最后一个元素交换arr[0]和arr[4]得到[1, 5, 3, 4, 10]。调整堆进行堆化得到[5, 4, 3, 1, 10]。重复交换和堆化过程交换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. 总结排序算法是计算机科学中非常重要的一类算法不仅在理论上具有广泛的应用也在实践中经常遇到。在本篇文章中我们详细探讨了几种经典的排序算法包括选择排序、插入排序、希尔排序和堆排序。坐标排序算法都有其独特的实现方式、时间复杂度、空间复杂度以及适用场景。通过对这些算法的分析我们可以看到不同的排序方法在不同情况下的表现差异如何选择合适的排序算法在实际应用中至关重要。选择排序实现简单但时间复杂度较高适合小规模数据的排序。插入排序同样适合小规模数据尤其是当数据近乎小区时表现非常高效。希尔排序通过优化插入排序的方式在大多数情况下表现相当但其稳定性较差。堆排序在时间复杂度上表现良好适合大规模数据排序但尚未达到增量增量。在选择排序算法时需要考虑数据规模、数据的初始状态是否接近分组以及算法的稳定性要求等因素。在实际应用中有很多高级排序算法如快速排序、归并排序和计数等排序能够提供更高效的排序效果。而对于一些特定的场景经典的排序算法如堆排序仍然发挥着重要的作用。总之了解各种排序算法的特点和应用场景能够帮助我们在不同的条件下做出最优化的选择为解决实际问题提供更、实用的解决方案。希望通过本篇文章的讲解能够帮助读者更好地理解排序算法为日后的算法学习和实践打下坚实的基础。
数据结构十大排序之（选排，希尔，插排，堆排）
1. 引言排序算法是计算机科学中最基础的算法之一它在很多领域都有广泛的应用。例如在数据存储、搜索引擎、数据库优化、图形渲染等方面排序都是必不可少的操作。是日常编程任务还是更复杂的计算问题理解排序算法的实现与高效性能表现帮助我们写出更多和优化的程序。排序算法的种类不同不同的算法具有不同的时间复杂度、空间复杂度和稳定性特点适用于不同规模和不同特性的应用场景。学习排序算法不仅可以加深对算法思想的理解也可以为解决实际问题提供了更灵活的选择。本文将重点介绍选择排序Selection Sort、希尔排序Shell Sort、插入排序Insertion Sort和堆排序Heap Sort四种常见的排序算法。我们将通过详细分析一个排序算法的原理、实现、时间和空间复杂度帮助读者深入理解多种算法的优缺点并结合实际应用场景进行比较。通过本篇博客你将能够理解排序算法的工作原理和实现方式掌握这些排序算法的时间复杂度和空间复杂度在实际项目中根据数据量和排序需求选择合适的排序算法。无论你是算法初学者还是正在为更多的代码优化而努力掌握这些高效排序算法的核心思想都让你在算法和编程方面的能力提升大有裨益。2. 排序算法概述排序算法是计算机科学中的基础性算法之一广泛评估数据存储、查询优化、搜索引擎、数据库管理等多个领域。其主要任务是一个无序的元素序列遵循某种规则如升序或降序重新排列从而使得数据更加小区随后进行后续的处理和使用。在不同的应用场景中排序算法的选择往往受到多种因素的影响如时间效率、空间效率、算法稳定性、输入数据的特性等。为了解决排序问题计算机科学家提出了多种不同的排序算法极限算法在不同的条件下都有其优点和适用场景。排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持 不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳 定的否则称为不稳定的。内部排序数据元素全部放在内存中的排序。外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。排序算法有很多种根据不同的特点我们可以对它们进行分类。主要的排序算法可以分为以下几类插入排序类排序算法通过逐步插入元素来构建排序序列。包括插入排序插入排序希尔排序Shell Sort交换排序类排序算法通过交换元素的位置来逐步排序常见的有冒泡排序Bubble Sort快速排序Quick Sort选择排序一类排序算法通过不断选择最小或最大元素并进行交换来实现排序包括选择排序Selection Sort堆排序Heap Sort归并排序类排序算法利用分治法的思想将大问题分解成小问题来流程图。包括归并排序Merge Sort计数排序算法适用于整数排序通过统计每个元素出现的次数来确定其最终位置包括计数排序计数排序基数排序Radix Sort桶排序Bucket Sort本文关注的四种排序算法在这篇博客中我们将重点讨论四种常见的排序算法它们分别是选择排序、希尔排序、插入排序和堆排序。这四种算法在很多实际场景中都有广泛的应用并且它们的实现相对简单容易理解。选择排序Selection Sort每次未排序部分的最小或最大元素放置已排序部分的补充。其实现简单但时间复杂度同样适用于小规模数据排序。希尔排序Shell Sort插入排序的改进版本通过分区和递增步长来加速排序过程。它在某些步长序列下面比插入排序更高效但仍然存在改进空间。插入排序Insertion Sort通过构建数组序列将每个待排序元素插入到已排序部分的适当位置。对于小规模数据它非常高效并且在数据部分数组时表现非常优秀。堆排序Heap Sort利用堆数据结构将最大元素或最小元素取出来逐步构建排序序列。它的时间复杂度较稳定适用于大规模数据的排序。排序算法核心因素排序算法的性能和适用性往往依赖于以下几个方面时间复杂度缓慢算法执行时间随数据规模变化的速率。大多数排序算法的时间复杂度都取决于输入数据的规模n例如O(n²)、O(n log n)等。空间复杂度简单算法使用额外空间的多少。对于大多数排序算法空间复杂度都为O(1)即原地排序。稳定性一个排序算法是否保持不同的元素之间的相对顺序。稳定性对某些应用如排序学生成绩时保持相同成绩的学生排序非常重要。适用场景不同的排序算法在不同的应用场景中效果各异。例如堆排序适合大规模数据插入排序适合部分小区的情况希尔排序适合中小数据规模选择排序适合小数据量或不关心稳定性的场合。排序算法的优缺点选择排序优点实现简单空间复杂度O(1)适合小规模数据排序。缺点时间复杂度O(n²)不适合大规模数据排序且不稳定。希尔排序优点比插入排序更高效时间复杂度较低空间复杂度O(1)适用于中小型数据。缺点不稳定步长序列的选择对性能影响增大。插入排序优点实现简单稳定适用于小规模数据且在数据部分小区时效率非常高。缺点时间复杂度O(n²)不适合大规模数据排序。堆排序优点时间复杂度O(n log n)稳定性较好适用于大规模数据排序且是原地排序。缺点突发且首次快速排序首次增加。小结排序算法的选择补充依赖于算法的时间复杂度需要考虑实际应用中的数据特性。例如数据规模较小时插入排序、选择排序可能简单而高效而在数据量较大时堆排序或归并排序等高效算法更加合适。 高精度排序算法有其优势和随身掌握高精度算法的实现和适用场景让您在编程时更加得心应手。接下来我们将深入探讨选择排序、希尔排序、插入排序和堆排序的详细原理与实现。3. 常见排序算法的实现3.1 插入排序3.1.1基本思想直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到 一个新的有序序列 。实际中我们玩扑克牌时就用了插入排序的思想。3.1.2 直接插入排序当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移原理插入排序的基本思想是将待排序的元素逐个插入到已经排序的部分中直到整个队列都成为集群。假设第一个元素已经是数组的从第二个元素开始依次将每个元素插入到已排序的序列子中。对于每个新元素找到它在已排序部分中应该插入的位置将其插入并且保持已排序部分的顺序。首先插入操作完成一个元素移动到合适的位置直到所有元素都被插入到已排序部分排序。算法步骤从第二个元素开始假设第一个元素已经是最小的。选择一个待排序元素将其与已排序部分的元素依次进行比较。如果待排序元素小于当前比较元素就将当前元素移动移动。当找到待排序元素应该插入的位置时将待排序元素插入到该位置。重复完成上述过程直到所有元素排序。我们从上述视频可以看出插排的思路定义两个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[j1] arr[j]; } else { arr[j1] temp; break; } } arr[j1] 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如果元素小于或等于tempelse条件temp则插入到位置arr[j 1]。内循环随即中断因为我们找到了正确的位置temp。temparr[j 1] temp;的最终排序此行确保将其temp放置在数组排序部分的正确位置。它解释了小于排序部分所有元素的情况temp使得j变成-1temp位于数组的开头arr[0]。静态分析假设我们有一个数组[5, 2, 9, 1, 5, 6]我们将通过插入排序将其排序初始数组[5, 2, 9, 1, 5, 6]第一轮从第二个元素2开始与第一个元素比较 5 2将5移至右侧插入2。[2, 5, 9, 1, 5, 6]第二轮下一个要素是99大于5不需要移动。 存储保持不变[2, 5, 9, 1, 5, 6]。第三轮元素1与9、、5比较2将它们逐一移至右侧插入1。[1, 2, 5, 9, 5, 6]第四轮元素5与9比较将9移至右侧再与5比较不需要移动[1, 2, 5, 5, 9, 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时所有记录在统一组内排好序。原理希尔排序的核心思想是通过分组插入排序来对数据进行排序。具体来说希尔排序首先将整个待排序数组分成若干个小的子序列这些子序列之间的间隔由步长序列决定然后在每个子序列上分别进行插入排序。通过逐步减少步长使得最终整个数组被排序。其基本步骤如下初始化步长首先选择一个步长序列通常是从大到小的数字序列常见的序列有 n/2,n/4,…,1n/2, n/4, \dots, 1n/2,n/4,…,1其中 nnn 是数组的长度。分组插入排序按照当前步长将数组划分为若干个子序列并在每个子序列上进行插入排序。每个子序列中的元素按照步长距离排序。减小步长步长逐渐减小通常是每次将步长减半直到步长为 1 时对整个数组进行一次插入排序最终完成排序。希尔排序通过较大的步长来进行初步排序逐步减小步长使得大部分数据能尽早被排序最终使插入排序的效率大大提高。算法步骤选择一个步长序列 gapgapgap通常是 n/2,n/4,…,1n/2, n/4, \dots, 1n/2,n/4,…,1。按照步长将数组分成若干个子序列。对每个子序列进行插入排序。重复上述步骤直到步长为 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]使用希尔排序来进行排序初始数组[5, 2, 9, 1, 5, 6]第一轮步长为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]第二轮步长为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(nlogn)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[i1]--array[n-1]集合中重复上述步骤直到集合剩余1个元素原理直接选择排序的基本思想是假设待排序数组的第一个元素已被排序。在剩下的元素中找到最小或最大的元素将其与已排序部分的最后一个元素交换位置。重复上述过程直到所有元素都被排序。具体来说直接选择排序可以分为以下步骤从未排序部分中选择最小或最大的元素。将这个元素与未排序部分的第一个元素交换位置使得已排序部分的元素增加一位。逐步缩小未排序部分直到所有元素都被排序。算法步骤初始状态将数组分为已排序部分和未排序部分开始时已排序部分为空未排序部分是整个数组。从未排序部分中选择最小元素将其与未排序部分的第一个元素交换位置。将已排序部分扩大未排序部分缩小继续选择未排序部分中的最小元素并交换。重复上述步骤直到未排序部分为空排序完成。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]使用直接选择排序进行排序初始数组[64, 25, 12, 22, 11]第一轮[64, 25, 12, 22, 11]计算选择最小元素11将其与第一个元素64交换然后[11, 25, 12, 22, 64]。第二轮[25, 12, 22, 64]其余选择最小元素12将其与第一个元素25交换然后[11, 12, 25, 22, 64]。第三轮[25, 22, 64]计算选择最小元素22将其与第一个元素25交换然后[11, 12, 22, 25, 64]。第四轮[25, 64]所需选择最小要素25需要交换储备保持保证[11, 12, 22, 25, 64]。排序完成最终结果为[11, 12, 22, 25, 64]。时间复杂度时间复杂度最坏情况、最好情况和平均情况的时间复杂度都是O(n²)因为需要对每个元素执行一次选择操作每次选择操作中又需要扫描剩余的元素。具体来说对于每个元素选择最小元素需要遍历剩余 n−1n - 1n−1 个元素对第二个元素需要遍历 n−2n - 2n−2 个元素依此类推。所以总的比较次数为总比较次数(n−1)(n−2)⋯1n(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)⋯12n(n−1)≈O(n2)空间复杂度选择排序是原地排序算法不需要额外的存储空间因此空间复杂度为O(1)。稳定性直接选择排序不稳定。因为在选择最小元素时如果遇到相等的元素它们的相对顺序可能会发生变化。例如如果array[i]和array[j]的值相同但i小于j那么交换操作可能会改变它们的相对顺序。优缺点优点实现简单直接选择排序的算法非常简单容易理解和实现。空间复杂度低它是原地排序算法不需要额外的存储空间。缺点时间复杂度较高由于其时间复杂度为 O(n2)O(n^2)O(n2)在大数据量时性能较差。不稳定直接选择排序是一个不稳定的排序算法相等元素的相对顺序可能会改变。适用场景小数据量排序由于直接选择排序的时间复杂度较高因此它通常用于处理小数据量的排序问题。内存受限的场合选择排序是一种原地排序算法适合在内存受限的环境中使用因为它只需要常数空间。堆排堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆 来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。堆排序Heap Sort是一种基于堆数据结构的排序算法。它的基本思想是利用堆的特性通常是最大堆或最小堆来进行排序。堆排序首先将输入数据构建成一个堆结构然后通过不断地交换根节点与最后一个节点缩小堆的范围逐步实现排序。由于堆排序是一个不稳定的排序算法但它具有较好的时间复杂度。堆的概念在堆排序之前我们需要理解“堆”这一数据结构。堆是一种完全二叉树具有以下特点最大堆在最大堆中每个父节点的值都大于或等于其子节点的值即根节点的值是最大值。最小堆在最小堆中每个父节点的值都小于或等于其子节点的值即根节点的值是最小值。堆排序通常使用最大堆来进行排序利用堆的性质来逐步将最大值移动到数组的末尾最终得到有序数组。堆排序的基本思想堆排序的核心思想是构建最大堆首先将给定的无序数组构建成一个最大堆。最大堆的性质是根节点的值最大。交换根节点与最后一个节点将堆顶元素最大元素与堆的最后一个元素交换然后将堆的有效元素数量减少 1。调整堆将新的根节点进行调整使其满足最大堆的性质。通过“堆化”过程将交换后的元素重新调整为堆结构。重复以上过程每次交换堆顶元素与最后一个元素后减少堆的大小再进行堆化操作直到堆的大小为 1排序完成。堆排序的算法步骤构建最大堆将输入数组构建为最大堆。对于一个索引为i的元素它的左右子节点分别为2i 1和2i 2父节点为i。交换堆顶元素与最后一个元素将堆顶元素与堆的最后一个元素交换并且减少堆的大小。堆化从堆顶开始通过调整堆的结构即“堆化”操作使其重新符合最大堆的性质。重复过程重复上述步骤直到堆的大小为 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*21; while (child length) { if (child 1 length arr[child] arr[child1] ) { child; } if (arr[child] arr[pvl]) { swap(arr,pvl,child); pvl child; child pvl*21; }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]我们通过堆排序对其进行排序构建最大堆最终数组[4, 10, 3, 5, 1]从最后一个非叶子节点开始依次进行堆化操作对索引i1进行堆化arr[1]是父节点arr[3]和arr[4]是它的子节点。堆化后队列为[4, 10, 3, 5, 1]。对索引i0进行堆化arr[0]是根节点arr[1]和arr[2]是它的子节点。堆化后栈为[10, 5, 3, 4, 1]。交换堆顶元素与最后一个元素交换arr[0]和arr[4]得到[1, 5, 3, 4, 10]。调整堆进行堆化得到[5, 4, 3, 1, 10]。重复交换和堆化过程交换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. 总结排序算法是计算机科学中非常重要的一类算法不仅在理论上具有广泛的应用也在实践中经常遇到。在本篇文章中我们详细探讨了几种经典的排序算法包括选择排序、插入排序、希尔排序和堆排序。坐标排序算法都有其独特的实现方式、时间复杂度、空间复杂度以及适用场景。通过对这些算法的分析我们可以看到不同的排序方法在不同情况下的表现差异如何选择合适的排序算法在实际应用中至关重要。选择排序实现简单但时间复杂度较高适合小规模数据的排序。插入排序同样适合小规模数据尤其是当数据近乎小区时表现非常高效。希尔排序通过优化插入排序的方式在大多数情况下表现相当但其稳定性较差。堆排序在时间复杂度上表现良好适合大规模数据排序但尚未达到增量增量。在选择排序算法时需要考虑数据规模、数据的初始状态是否接近分组以及算法的稳定性要求等因素。在实际应用中有很多高级排序算法如快速排序、归并排序和计数等排序能够提供更高效的排序效果。而对于一些特定的场景经典的排序算法如堆排序仍然发挥着重要的作用。总之了解各种排序算法的特点和应用场景能够帮助我们在不同的条件下做出最优化的选择为解决实际问题提供更、实用的解决方案。希望通过本篇文章的讲解能够帮助读者更好地理解排序算法为日后的算法学习和实践打下坚实的基础。
