WUST数据结构复习-排序（选择、综合题）

一、算法稳定性

• 1.稳定： 插入、归并、基数、冒泡
• 2.不稳定： 选择、希尔、堆、快速

二、算法思想

1.直接插入排序

思想： 将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录+1的有序表

时间复杂度：

T=O（n^2)

例题：

49 38 65 97 76 13 27 49*
初始关键字：[49] 38 65 97 76 13 27 49*
i=2: [38 49] 65 97 76 13 27 49*
i=3: [38 49 65] 97 76 13 27 49*
i=4:[38 49 65 97] 76 13 27 49*
i=5:[38 49 65 76 97] 13 27 49*
i=6:[13 38 49 65 76 97] 27 49*
i=7:[13 27 38 49 65 76 97] 49*
i=8:[13 27 38 49 49* 65 76 97]

2.希尔排序

思想： 将整个待排序记录序列分割成若干个子序列分别进行直接插入排序，带整个序列中的记录基本“有序”时，再集体进行一次直接插入排序

时间复杂度：
平均：T=O（ n*log2n）与增量有关 O（nlogn）～O（n2）

例图：

49 38 65 97 76 13 27 49*（增量选择 4 2 1）
增量4：49 13 27 49* 76 38 65 97
（a[1],a[5]),(a[2],a[6]),(a[3],a[7]),(a[4],a[8])排序

增量2：13 27 49*49 38 65 76 91
（a[1],a[5],a[2],a[6]),(a[3],a[7],a[4],a[8])排序

增量1：13 27 38 49 49* 65 76 97
（a[1],a[5],a[2],a[6],a[3],a[7],a[4],a[8])排序

3.冒泡排序

思想： 将第一个记录和第二个记录对比，若为逆序则交换位置，比较第二个值和第三个记录的值，依此类推，直至第n-1个值和第n个值进行比较位置，此时为第一次起泡排序，其结果值得最大值被安置在最后一个记录的位置上，然后进行第二次起泡排序，对前n-1个记录进行同样操作，直至在一次起泡排序过程中没有交换记录的操作。
时间复杂度：

T=(O（n^2))

例题：

49 38 65 97 76 13 27 49*
i=1:38 49 65 76 13 27 49* 97
(49>38交换位置，49<65，比较49后面的值,65<97比较65后面的值，
97>76交换位置，97>13交换位置，97>27交换位置,97>49*，交换位置）
i=2:38 49 65 13 27 49* 76 97
i=3:38 49 13 27 49* 65 76 97
i=4:38 13 27 49 49* 65 76 97
i=5:13 27 38 49 49* 65 76 97
i=6:13 27 38 49 49* 65 76 97

4.快速排序

思想： 通过一趟排序把待排记录分割成两部分，其中一部分记录的关键字均比另一部分记录小，则分别对这两记录进行排序。

简而言之：两个指针low、hight,第一个设为枢纽p，从high所指位置向前搜索出第一个小于p的值，交换位置，从low往后找到奥第一个小于p的值，交换位置，直至low=high。依此类推

时间复杂度：

T=O(n*log2n)

例题：

5.简单选择排序

思想： 第一次循环，遍历数组找出数组中最小的数字，放入a[0]，第二次循环，找出剩下数组中最小的数字放入a[1]一次类推。

时间复杂度： `

最小值：T=（0），最大值T=（3（n-1))

例题：

49 38 65 97 76 13 27 49*
i=1:[13] 49 38 65 97 76 27 49*
i=2:[13 27] 49 38 65 97 76 49*
i=3:[13 27 38] 49 65 97 76 49*
i=4:[13 27 38 49] 65 97 76 49*
i=5:[13 27 38 49* 49] 65 97 76 
i=6:[13 27 38 49* 49 65] 97 76 
i=7:[13 27 38 49* 49 65 76] 97
i=8:[13 27 38 49* 49 65 76 97]

6.堆排序

思想：建立完全二叉树，根据最后一个非叶子结点（n/2 下界)对完全二叉树进行调整，然后再对前一个非叶子结点进行调整，依此类推，建立大根堆。然后将根与最后一个叶子结点交换位置，调整->根与n-2进行交换位置，调整，一次类推
时间复杂度：

T=O(nlogn)

例题：
查看此处

7.归并排序

思想： 首先将这个数组分成一半
时间复杂度：

T=O（nlogn）

例题：

8.链式基数排序

思想： 通过“分配”和“收集”两个过程来实现排序的。
时间复杂度：

O(k*(n+m))

空间复杂度：

O(n+m)

例题：查看此处

P142 综合题第8题是对以上排序的简单应用

注：如有不到之处，请多多指教