🔑数据结构_第八章:排序
一、排序的概念
排序Sort
,就是重新排列表中的元素,使表中的元素满足按关键字有序的过程。
- 输入:$n$个记录$R_1,R_2,…,R_n$,对应关键字为$k_1,k_2,…,k_n$。
- 输出:输出序列的一个重排$R_1^{‘},R_2^{‘},…,R_n^{‘}$,使得有$K_1^{‘} \le K_2^{‘} \le … \le K_n^{‘}$(也可以递减)。
排序算法的评价指标:
时间复杂度
空间复杂度
稳定性:
若待排序表中有两个元素$R_i$和$R_j$,其对应的关键字相等——即$key_i= key_j$,且在排序前$R_i$在$R_j$的前面,若使用某一排序算法排序后,$R_i$仍然在$R_j$的前面,则称这个排序算法是稳定的,否则称排序算法是不稳定的。
问:稳定的排序算法一定要比不稳定的好吗?
答:不一定!看实际业务需求!
排序算法的分类:
- 内部排序:数据都在内存中,主要关注时间复杂度和空间复杂度。
- 外部排序:数据太多,无法全部放入内存,不仅要关注时间空间复杂度,还要关注如何使读写磁盘的次数更少!
数据结构算法可视化网站:Data Structure Visualizations
二、插入排序
直接插入排序、折半插入排序、希尔排序
(一)直接插入排序

1 | //直接插入排序——王道咸鱼 |
性能评估:
空间复杂度:$O(1)$;
时间复杂度:$O(n^2)$:
主要来自于对比关键字、移动元素,若有$n$个元素,则需要$n-1$躺处理。
最好情况:$O(n)$;
最坏:原本为逆序——$O(n^2)$。
稳定性:稳定。
(二)折半插入排序:
因为已排好序的部分肯定是有序的,所以可以将查找插入位置的部分换成折半查找的方式。
当low>high
时折半查找停止,应将[low, high]区间内的元素全部右移,再将temp
复制到low
所指位置。
而如果要保持算法稳定性,当A[mid]=temp
时,应继续在mid
所指位置右边寻找插入位置。
1 | //折半插入排序 |
折半插入排序只能用于顺序表,链表就用不了!
若将插入排序应用于链表,那么排序过程中只需更改指针而不用挪动元素,但是关键字的对比次数仍然是O(n2)数量级,整体看起来时间复杂度仍然是$O(n^2)$。

(三)希尔排序ShellSort
1、算法逻辑
希尔排序:先将待排序表分割成若干形如$L[i,i+ d,i+ 2d,..,i+ kd$的“特殊”子表,对各个子表分别进行直接插入排序。
缩小增量$d$,重复上述过程,直到$d=1$为止。


演示1:

演示2:

2、代码实现
1 | void ShellSort(int A[], int n){ |
3、性能分析
空间复杂度:$O(1)$;
时间复杂度:
目前无法用数学手段证明确切的时间复杂度。
最坏时间复杂度为$O(n^2)$,当$n$在某个范围内时,可达$O(n^{1.3})$。
稳定性:
不稳定!
适用性:
只适用于顺序表,不适用于链表。
总结:

三、冒泡排序和快排序
(一)冒泡排序

1、概念
从后往前(或从前往后)两两比较相邻元素的值,若为逆序——即$A[i-1]>A[i]$——则交换它们,直到序列比较完。
称这样过程为“一趟”冒泡排序。
2、代码
王道咸鱼学长:
1 | //交换函数 |
我自己手撸(从前往后遍历升序排序):
1 |
|
运行结果:

3、性能评估
稳定性:稳定
时间复杂度:
- 最好(有序):$O(n)$;
- 最坏(倒序):$O(n^2)$;
- 平均:$O(n^2)$.
空间复杂度:$O(1)$.
可以应用于链表!
每次执行交换
swap()
需要执行三次交换!需注意每次循环开始前检查是否已排好序,如果是直接结束!(上文中王道11、19、20行代码)
(二)快速排序

1、算法逻辑
算法思想:
在待排序表$L[1…n]$中任取一个元素pivot
作为枢轴(或基准,通常取首元素),通过一趟排序将待排序表划分为独立的两部分$L[1…k-1]$和$L[k+1…n]$,使得$L[1…k-1]$中的所有元素小于pivot
,$L[k+1…n]$中的所有元素大于等于pivot
,则pivot
放在了其最终位置$L(k)$上,这个过程称为一次“划分”。
然后分别递归地对两个子表重复上述过程,直至每部分内只有一个元素或空为止,即所有元素放在了其最终位置上。
2、代码实现
1 | //对表进行划分 |
3、性能评估
可以将其看作n个结点的二叉树:最小高度为$[log2n]+1$,最大高度为$n$。

时间复杂度:
受递归层数影响:
- 最好:$O(nlog_2n)$(每次选的枢轴元素都能将序列划分成均匀的两部分)。
- 最坏:$O(n^2)$(若序列原本就有序或逆序,则时空复杂度最高(可优化,尽量选择可以把数据中分的枢轴元素))。
- ❗平均时间复杂度:$O(nlog_2n)$(实际情况中更接近最好情况)。
空间复杂度:
也受递归层数影响:
- 最好:$O(log_2n)$.
- 最坏:$O(n)$.
稳定性:不稳定!
快速排序是所有内部排序算法中平均性能最优的排序算法!
四、直接选择排序和堆排序
(一)简单选择排序

1、算法思想
选择排序:每一趟在待排序元素中选取关键字最小(或最大)的元素加入有序子序列。
2、代码实现

1 | //快速排序 |
3、性能评估
时间复杂度:$O(n^2)$.
无论有序、逆序还是乱序都要进行n-1躺处理。
空间复杂度:$O(1)$.
稳定性:不稳定。
适用性:顺序表和链表都适用。
(二)堆排序
1、相关概念与算法思想
(1)数据结构——“堆”



- 大根堆:根结点$\ge$左右子树的完全二叉树;
- 小根堆:根结点$\le$左右子树的完全二叉树;
(2)算法思想
*注:以下是升序排序为例:
- 先将待排序序列改造成大根堆,这样子对应完全二叉树(以下称为“树”)的根结点就是整个序列中最大的那一个;
- 然后将根结点和最后一个叶子结点交换,此时整个序列中最后一个元素就是排序好了的;
- 再把除去最后一个已排好序的结点的子树重新改造为大根堆;
- 循环2、3步骤,直至只剩最后一个根节点未排序,那么此时整个序列已经排好序了!
2、代码实现

1 | //将以k为根的子树调整为大根堆 |
3、性能分析
- 时间复杂度:$O(n\log_2n)$.
- 空间复杂度:$O(1)$.
- 稳定性:不稳定。
4、堆的插入和删除
❗是在堆里面不是在排序序列里面❗
(1)插入
- 先将新的元素放到表尾;
- 再根据实际情况将元素不断“上升”,直到无法继续上升为止。
(2)删除
- 将目标元素删除,用表尾元素代替删除元素;
- 再根据实际情况将元素不断“下坠”,直到无法继续下坠为止。

五、归并排序
(一)算法思想


(二)代码实现


1 | int *B=(int *)malloc(n*sizeof(int)); //辅助数组B |
(三)性能评估
- 时间复杂度:$O(nlog_2n)$.
- 空间复杂度:$O(n)$.
- 稳定性:稳定。
总结:

六、各种排序算法性能分析总结
算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
---|---|---|---|
直接插入排序InsertSort |
$O(n^2)$ | $O(1)$ | 稳定 |
折半插入排序 | $O(n^2)$ | $O(1)$ | 稳定 |
希尔排序ShellSort |
最坏$O(n^2)$,当$n$在某个范围内时可达$O(n^{1.3})$ | $O(1)$ | 不稳定 |
冒泡排序BubbleSort |
$O(n^2)$ | $O(1)$ | 稳定 |
快速排序QuickSort |
$O(nlog_2n)$ | 最好$O(log_2n)$,最坏$O(n)$ | 不稳定 |
(简单)选择排序SelectSort |
$O(n^2)$ | $O(1)$ | 不稳定 |
堆排序HeapSort |
$O(nlog_2n)$ | $O(1)$ | 不稳定 |
归并排序MergeSort |
$O(nlog_2n)$ | $O(n)$ | 稳定 |