常见排序算法

2017-12-21

常见排序算法分类

十种常见排序算法一般分为以下几种：

总结

交换类排序

交换排序的基本方法是：两两比较待排序记录的排序码，交换不满足书序要求的偶对，直到全部满足位置。常见的冒泡排序和快速排序就属于交换类排序。

冒泡排序

从数组中第一个数开始，一次遍历数组中的每一个数，通过相邻比较交换，每一轮循环下来找出剩余未排序数中的最大数并“冒泡”至数列的顶端。

1 从数组中第一个数开始，一次与下一个数比较，并且依次交换比自己小的数，直到最后一个数。如果发生交换，则继续下面的步骤；如果未发生交换，则数组有序，排序结束，此时时间复杂度为(n)。

2 每一轮“冒泡”结束后，最大的数将出现在乱序数列的最后一位。重复步骤(1)

稳定排序

O(n)至O(n^2)，平均时间复杂度为O(n^2)。

最好的情况：如果待排序数据序列为正序，则一趟冒泡就可以完成排序，排序码的比较次数为n-1，且没有移动，时间复杂度为O(n)。

最坏的情况：如果待排序的数据序列为逆序，则冒泡排序需要n-1次起泡，每趟进行n-i次排序码的比较和移动，即比较和移动次数均达到最大值，因此最坏的时间复杂度为O(n^2)。

快排

冒泡排序是在相邻的两个记录进行比较和交换，每次交换只能上移或下移一个位置，导致总的比较次数与移动次数角度。快速排序又称为分区交换排序，是对冒泡排序的改进，快速排序采用的思想是分治思想。

1 从待排序的n个记录中任意选取一个记录作为分区标准；

2 把所有小于该排序列的记录移动到左边，把所有大于该排序码的记录移动到右边，中间放所选记录，称之为第一趟排序；

3 然后对前后两个子序列分别重复上述过程，知道所有记录都排好序。

不稳定排序

O(nlg(n))至O(n^2)，平均时间复杂度为O(nlogn)。

最好的情况：是每趟排序结束后，每次划分使两个子文件的长度大致相等，时间复杂度为O(nlogn)。最坏的情况：待排序记录已经排好序，第一趟经过n-1次比较后第一个记录保持位置不变，并得到一个n-1个元素的子记录；第二趟经过n-2次比较，将第二个记录定位在原来的位置上，并得到一个包括n-2个记录的子文件，依次类推，比较次数是O(n^2)。

插入类排序

插入类排序的基本方法是：每步将一个待排序的记录，按其排序码大小，插入前面已经排序的文件中的适当位置，知道全部插入为止。

直接插入排序(转化成为一个未知元素如何向一个有序数列中插入数据)

从待排序的n个记录中的第二个记录开始，一次与前面的记录比较，并寻找插入的位置，每次外循环结束后，将当前的数插入到合适的位置。

稳定排序

-时间复杂度：

O(n)至O(n^2)，平均时间复杂度O(n^2)。

最好的情况：当待排序记录已经有序，比较次数是O(n)

最坏的情况：如果待排序记录为逆序，则最多的比较次数为O(n^2)

Shell排序

Shell排序又称缩小增量排序，由D.L.Shell在1959年提出的，是对直接插入排序的改进。

Shell排序是对相邻指定举例（又称为增量）的元素进行比较，并不断吧增量缩小至1，完成排序。

Shell排序开始时增量较大，分组较多，魅族的记录数据较少，故在各族内采用直接插入排序较快，后来增量di主键缩小，分组数减少，各组的记录数增多，但是由于已经按di-1分组排序，文件较接近于有序状态，所以新的一趟排序过程较快。因此Shell排序在效率上比直接插入排序有较大的改进。

在直接排序的基础上，将直接插入排序中的1全部改成增量d即可，因为Shell排序最后一轮的增量d就为1。

不稳定排序

O(n^1.3)到O(n^2)

Shell排序算法的时间复杂度分析比较复杂，研究表明，若增量的取值比较合理，Shell的排序算法的时间复杂度约为O(n^1.3)。

对于增量的选择，Shell最初建议增量选择为n/2，并且对增量取半，直到1。

选择类排序

选择类排序的基本方法是：每步从待排序列记录中选出排序码最小的记录，顺序放到已排序的记录序列的后面，直到全部排序完成。

简单选择排序（又称直接选择排序）

从所有记录中选出最小的一个数据元素与第一个位置的记录交换，然后在剩下的记录中再找最小的与第二个位置的记录交换，循环只剩下最后一个数据元素为止。

不稳定排序

最坏、最好的平局复杂度均为O(n^2)，因此，简单选择排序也是常见的排序算法中性能最差的排序算法。简单选择排序的比较次数与文件的初始状态没有关系，在第i趟排序中选出最小排序码的记录，需要做n-i次比较，总的时间复杂度O(n^2)。

堆排序

直接选择排序中，第一次选择经过了n-1次比较，只是从排序码序列中选择除了一个最小的排序码，而没有保存其他中间比较结果。所以后一趟排序时又要重复许多比较操作，降低了效率。J.Willioms和Floyd在1964年提出了堆排序方法，避免这一缺点。

性质：完全二叉树或者近似完全二叉树

分类：大顶堆：父节点不小于子节点键值；小顶堆：父节点不大于子节点键值

左右孩子：没有大小的顺序

堆的存储

般都用数组来存储堆，i节点的父节点下表就为(i-1)/2。它的左右子节点下表分别为2i+1和2i+2。如第0个节点左右子节点下标分别为1和2.

堆的操作

建立：

以最小堆为例，如果以数组存储元素时，一个数组具有对应的树表示形式，单树并不满足堆的要求，需要重新排列元素，可以建立堆化树。

插入：

将一个新元素插入到表尾，即数组末尾时，如果新构成的儿茶素不满足堆的性质，需要重新排列元素。

删除：

堆排序中，删除一个元素总是发生在堆顶，因为堆顶的元素是最小的（小顶堆中）。表中最后一个元素用来填补空缺位置，结果树被更新以满足堆条件。

由于堆也是用数组来存储的，故对数组进行堆化后，第一次将a[0]与a[n-1]交换，再对a[0…n-2]重新恢复堆。第二次将a[0]与a[n-2]交换，再对a[0…n-3]重新恢复堆，重复这样的操作直到a[0]与a[1]交换。由于每次都是将最小堆的数据并入到后面的有序区间，故操作完成后，整个数组就有序了。有点类似于直接选择排序。

由于每次重新恢复堆的时间复杂度为O(logN)，共N-1次堆调整操作，再加上前面建立堆时N/2次向下调整，每次调整的时间复杂度也为O(logN)。两次操作时间相加还是O(NlogN)。故堆排序的时间复杂度为O(NlogN)。

最坏情况：如果待排序数组是有序的，仍然需要O(N*logN)复杂度的比较操作，只是减少了移动的操作

最好情况：如果待排序数组是逆序的，不仅需要O(NlogN)复杂度的比较操作，而且需要O(NlogN)复杂度的交换操作。总的时间复杂度还是O(N*logN)。

因此，堆排序和快排在时间效率上市差不多的，但是堆排序一般优于快速排序的重要一点是，数据的初始分布情况对堆排序的效率没有大的影响。

归并排序

归并排序属于比较类非线性时间排序，号称比较类排序中性能最佳者，在数据中应用较广。

归并排序是分治法（Divide and Conquer）的一个典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，则成为二路归并。

稳定排序算法

最坏、最好和平均时间复杂度都为0(nlgn)。

线性时间非比较类排序

计数排序

计数排序是一个非基于比较的排序算法，该算法于1954年由Harold H. Seward提出，它的优势在于在对于比较小范围内测整数排序。它的复杂度为O(n+k)(k是待排序数的范围)，快于任何比较排序算法，缺点是非常消耗空间。很明显，如果当O(k)>O(n*log(n))的时候，其效率反而不如基于比较的排序，比如堆排序和归并排序和快速排序。

基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一位置上，在代码中做适当修改即可。

计数排序是典型的以空间换时间的排序算法，对待排序的数据有严格的要求，比如待排序的数值中包含负数，最大值都有限，请谨慎使用。

基数排序算法

基数排序属于“分配式排序”（distribution sort），是非比较类线性时间排序的一种，又称“桶子法”（bucket sort）。顾名思义，它是透过键值的部分信息，将要排序的元素分配至某些“桶”中，借以达到排序作用。

基数排序（以整型为例），将整型10进制按每位拆分，然后从低到高一次比较各个位。主要分为两个过程：

1) 分配，先从个位开始，根据位置(0-9)分别放到0-9号桶中（比如64个位是4，放入4号桶中）

2) 收集，再将放置在0-9号桶中的数据按顺序放到数组中

3) 重复12过程，从个位到最高位。

平均时间复杂度： O(dn) d表示整型的最高位

空间复杂度：O(10n) 10表示0-9，用于存储临时的序列

桶排序

桶排序也是分配排序的一种，但其实基于比较排序的，这也是与基数排序最大的区别所在。

桶排序算法想法类似于散列表。首先要假设待排序的元素输入符合某种均匀分布，例如数据均匀分布在[0, 1)区间上，则可将该区域划分成为10个小区间，成为桶，对散布在同一个桶中的元素再排序。

1) 设置一个定量的数组当做空桶子

2) 寻访序列，并且把记录一个一个放到对应的桶子去

3) 对每个不是空的桶子进行排序

4) 从不是空的桶子里把项目再放回原来的序列

平均时间复杂度为线性O(N+C)，其中C为桶内排序所花费的时间。当每个桶子只有一个数时，最好时间复杂度为O(N)

参考