八大排序算法

!

排序算法	最差时间复杂度	最优时间复杂度	平均时间复杂度	空间复杂度	稳定性
选择排序	O(n2)	O(n2)	O(n2)	O(1)	稳定
插入排序	O(n2)	O(n)	O(n2)	O(1)	稳定
冒泡排序	O(n2)	O(n)	O(n2)	O(1)	稳定
快速排序	O(n2)	O(nlog(n))	O(nlog(n))	O(nlog(n))	不稳定
希尔排序	O(n2)	O(n)	O(n1.3)	O(1)	不稳定
归并排序	O(nlog(n))	O(nlog(n))	O(nlog(n))	O(n)	稳定
堆排序	O(nlog(n))	O(nlog(n))	O(nlog(n))	O(1)	不稳定
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(n+r)	不稳定

*n为数字个数，r为基数（10），d为位数
*稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

1. 选择排序

每次在后面n−i,(i=0,1,2...n−2)个记录中选取关键字最小的记录，和第i个记录进行交换，作为有序序列的第i个记录。

2. 插入排序

每次将第i,(i=1,2,...,n−1)个记录插入到前面含有i个元素的有序表中（原地操作）。

3. 冒泡排序

倒序依次比较相邻的两个数，将较小的数放在前面，较大的数放在后面。内层逆向循环n−i−1次，外层正向循环n−1次。

4. 快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

5. 希尔排序

将记录按增量increment分组，对每组记录进行插入排序；随着增量逐渐减小，所分成的组包含的记录越来越多，当增量减小到1时，整个数据合为一组有序记录，则完成排序。

6. 归并排序

将待排序序列R[0...n−1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。

7. 堆排序

将原始序列构造成一个最大堆（父结点比其孩子结点数值大），交换第一个结点（根结点）和最后一个结点，输出最后一个结点（当前最大值），将剩下的元素重新构造成最大堆，重复以上过程最终得到一个有序序列。

8. 基数排序

按照个位、十位、百位……上数字的大小进行排序，浮点数处理较麻烦。