排序算法总结

所谓排序，就是要整理文件中的记录，使之按关键字递增或递减次序排列起来。当待排序记录的关键字均不相同时，排序结果是唯一的，否则排序结果不唯一。

1.插入排序

插入排序基本思想：每步将一个待排序的记录按其排序码值的大小，插入到前面已经排好的文件中的适当位置，直到全部插入完为止。

（1）直接插入排序

在插入第i个记录时，R1,R2,…，Ri-1已经排好序，将第i个记录依次和R1,R2,…，Ri-1进行比较，找到适当的位置。

（2）希尔排序/缩小增量排序

希尔排序是不稳定的。

2.选择排序

选择排序的基本思想：每步从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列的后面，直到全部排完。

（1）直接选择排序

过程：首先在所有记录中选出排序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换……依此类推，直到所有记录排完为止。

直接选择排序是不稳定的。

（2）堆排序

父结点>子结点，大顶堆

父结点<子结点，小顶堆

注意：对于结点i，i>=n/2时，表示结点i为叶子结点

调整：从n/2结点开始，然后2/n -1个结点

把根结点和最后一个结点对调，把指针断开，调整，继续对调，调整。

堆排序不适宜于记录数较少的文件。堆排序是就地排序，为不稳定的排序算法。

3.交换排序

交换排序的基本思想：两两比较待排序记录的排序码，并交换不满足顺序要求的那些偶对，直到满足条件为止。

（1）冒泡排序

两两比较，轻气泡向上漂浮，每次循环求出最大值。

冒泡排序是就地排序，且是稳定的。

（2）快速排序

采用分治法，基本思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题，递归的解这些子问题，然后将这些子问题的解组合为原问题的解。

如，对关键码{7,2,5,1,9,6,8,3}进行排序，选择第一个元素为基准

第一步：【3 2 51 6】7【8 9】

第二步：【1 2】3【5 6】7【8 9】

第三步： 1 2 3 【5 6】7【8 9】

第四步： 12 3 5 6 7【8 9】

结果： 1 2 3 5 6 7 8 9

快速排序是不稳定的。

4.归并排序

将两个或两个以上的有序子表合并成一个新的有序表，初始看作n个长度为1的有序子表，依次两两合并得到长度为2的若干有序子表，再两两合并，直到得到长度为n的有序表。

如，对关键码{72,28,51,17,96,62,87,33}进行排序，过程如下：

72 28 51 17 96 62 87 33

【2872】【1751】【62 96】【33 87】

【17 28 51 72】【33 62 87 96】

【17 2833 51 62 72 87 96】

归并排序是一种稳定的排序，不是就地排序。

5.基数排序（收集个位，收集十位，收集百位）

从低位到高位依次对待排序的关键码进行分配和手机，经过d趟分配和收集可以得到一个有序序列。

基数排序是稳定的。

6.算法复杂性比较

稳定排序算法：在排序过程中是否会改变相同关键字的顺序。