本文共 2044 字，大约阅读时间需要 6 分钟。

可参考：

简单排序中的 冒泡排序

思想：两两相邻数值比较，如果逆序则交换，直到没有逆序的记录为止;

复杂度分析：最好的情况是待排序表是正序，不需要交换，复杂度是O(n)；最坏情况待排序表是逆序，每次都要交换，复杂度是O(n^2);平均是O(n^2)。辅助空间O(1)

快速排序

思想：通过一趟排序将代排记录分割成独立的前后两部分，其中一部分的值均比另一部分小，接着又可以分别对这两部分继续进行排序，从而达到整个序列有序。

复杂度分析：快速排序的时间性能取决于快速排序递归的深度。 最优的情况下，partition函数每次都划分很均匀（枢轴选取每次都是序列中间值），如果排序n个关键字，其递归树的深度就是log n ,时间复杂度为O(n log n)，最坏的情况下，待排序数列是正序或者逆序，其递归树就是一个颗斜树,深度为n，时间复杂度为O(n^2)，平均情况是O(n log n)。辅助空间为O(log n)~O(n)

简单排序中的 选择排序

思想：通过n-i次数值的比较，从n-i+1个数中选出最小的值，将该最小值和第i个数值交换。特点是交换数据次数非常少。

复杂度分析：不管是什么情况，比较次数都是一样的，但是对于交换次数来说：最好情况是正序不需要交换，最差情况是逆序，交换次数n-1次。但是时间复杂度都是O(n^2),最好和最差都是一样的。因此和冒泡法排序相比，在正序情况下，冒泡法排序是O(n)更加好，虽然平均都是O(n^2)，但是选择排序性能略好于冒泡法。

堆排序算法

思想：将待排序列构造成一个大顶堆（所有节点大于等于其子孩子）。此时整个序列的最大值是堆顶的根节点。将它移走，然后将将剩余的n-1个序列重新构造成一个堆，这样就得到ｎ个元素中的次大值。如此反复执行，便能得到一个有序序列。

复杂度分析：运行时间主要消耗在初始构建堆和重建堆（准确来说是微调堆）上面。最好情况，最坏情况，平均情况全部都是一样的为O(n log n),对原始记录的排序状态不敏感。在空间复杂度上面只使用一个用来交换的短暂单元（largest)为O(1)。同时，这是一个不稳定的排序方法，因为比较和交换是跳跃进行的。

简单排序中的 插入排序

思想：将一个值插入到已经排好序的序列中，原来排好序的，只要大于该插入值就逐个往后移动，从而得到一个新的，记录增加1的有序表

复杂度分析： 当最好的情况下，序列是正序，则时间复杂度为O(n);   当最坏情况，初始序列是逆序，则时间复杂度为O(n^2)；平均时间复杂度是O(n^2)。对于空间复杂度只使用一个短暂的交换单元（key变量）O(1)。

简单排序的比较： 简单排序，对于初始序列如果是正序的情况下，插入排序和冒泡排序的复杂度是一样的O(n),但是选择排序都是O(n^2)。在最坏情况下即逆序下，都是O(n^2)，但是如果给的序列是无序的随机序列，那么表现最好的是插入排序！

希尔排序算法

思想: 直接插入排序对序列基本有序或者序列比较小的情况下效率非常高。

当有大量的数据需要排序时，可以将大量的数据分组成若干子序列，此时每个子序列的数据比较少，可以对每个子序列使用直接插入排序。 当整个序列基本有序时(基本有序：小的关键字基本在前，大的基本在后，不大不小的基本在中间)。再对整体的数据进行一次直接插入排序。 对原始数据进行分割的目的就是减少待排序数据的个数，使得整个序列朝着基本有序方向发展。 采用的分割策略（关键）是：将相距某个增量increment的数据组成一个子序列，实现跳跃式的移动，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序的。

复杂度分析:增量选取是关键，最简单的就是直接取半。希尔排序最好的情况，正序情况下为O(n^1.3);  最坏情况是逆序情况为O(n^2),但是平均情况下时间复杂度为O(nlog n)~O(n^2)。辅助空间只需要一个短暂的交换单元（key变量）O(1)。

这是第一次平均时间复杂度能超越简单排序(冒泡，选择，插入排序)的慢速排序时代（超越了时间复杂度为O(n^2）)

归并排序算法,考虑使用非递归方法

思想： 使用归并的思想实现排序的方法。

原理是：假设待排序列长度为n,则可以看成n个有序的子序列，每个序列长度为1，然后两两归并，得到cell(n/2)个长度为2或者1的有序子序列； 再两两归并，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法成为2路并归排序。归并法是分治法（Divide and Conquer）的一个非常典型的应用。 复杂度分析： 最好情况和最坏情况都是一样的都为O(n log n),所以平均时间复杂度为O(n log n)。但是对于空间复杂度来说，当归并算法使用递归法时的辅助空间复杂度为O(n+log n);但是使用非递归方法时的辅助空间复杂度为O(n)。综合来说，空间复杂度是目前所有排序算法中最大的。从稳定性来说，归并算法是复杂排序算法中唯一稳定的。  

 

转载地址：https://blog.csdn.net/zz2230633069/article/details/102621516 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！