准备：排序用到的结构和函数
先提供一个用于排序用的顺序表结构，此结构也将用于后面要讲的所有排序算法
#define MAXSIZE 10 // 用于要排序数组个数的最大值，可根据需要修改
typedef struct {
int r[MAXSIZE + 1]; // 用于存储要排序数组，r[0]用作哨兵或者临时变量
int length; // 用于记录顺序表的长度
}SqList;
由于排序最常用到的操作是数组两元素的交换，将其封装为函数
void swap(SqList *L, int i, int j) { // 变换L中数组r的下标为i和j的值
int temp = L->r[I];
L->r[i]=L->r[j];
L->r[j]=L->r[I];
}
一、冒泡排序
冒泡排序（Bubble Sort）是一种交换排序，基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
- 1.1、对顺序表L做交换排序（冒泡排序初级版）
void BulleSort0(SqList *L) {
int i, j;
for (i = 1; i < L->length; i ++) {
for (j = i + 1; j <= L->length; j ++) {
if (L->r[i] > L->r[j]) {
swap(L, i, j); // 交换 L->r[i]于 L->r[j]的值
}
}
}
}
严格意义上说，这不算标准的冒泡排序算法，应为它不满足“两两比较相邻记录”的冒泡排序思想，它更应该是最简单的交换排序而已，这个算法的效率是非常低的
- 1.2、冒泡排序算法
void BulleSort(SqList *L) {
int i, j;
for (i = 1; i < L->length; i ++) {
for (j = L->length - 1; j >= i; j --) { // 注意j是从后向前循环
if (L->r[j] > L->r[j + 1]) { // 若前者大于后者（注意这里与上一算法差异）
swap(L, j, j + 1); // 交换 L->r[j]于 L->r[j + 1]的值
}
}
}
}
- 1.3、冒泡排序优化
试想一下，如果我们待排序的系列是{2, 1, 3, 4, 5, 6, 7, 8, 9}，除了第一和第二的关键字需要交换外，别的都是正常的顺序。当 i = 1时，交换完 2 和 1，此时序列已经有序，后面大量的比较还是大大多余了。为此，增加一个标记变量flag来实现这一算法的改进
void BulleSort2(SqList *L) {
int i, j;
BOOL flag = true; // flag 用来作为标记
for (i = 1; i < L->length && flag; i ++) { // 若flag为true则对出循环
flag = false; // 初始为flase
for (j = L->length - 1; j <= i; j --) {
if (L->r[j] > L->r[j + 1]) {
swap(L, j, j); // 交换 L->r[j]于 L->r[j + 1]的值
flag = true; // 如果有数据交换，则flag为true
}
}
}
}
- 1.4、时间复杂度分析
最好的情况：要排序的表本身就是有序的，进行了n-1次比较，没有数据交换，时间复杂度为O(n);
最坏的情况：待排序表是逆序的情况，此时需要比较n(n - 1)/2次，并作等数量级的记录移动，时间复杂度为O(n²)。
二、简单选择排序
简单选择排序法（Simple Selection Sort）就是通过 n-i 次关键字间的比较，从 n-i+1 个记录中选出关键字较小的记录，并和第 i (1 <= i <= n)个记录交换之
void SelectSort(SqList *L) {
int i, j, min;
for (i = 1; i < L->length; i ++) {
min = i; // 将当前下标定义为最小值下标
for (j = i + 1; j <= L->length; j ++) { // 循环之后的数据
if (L->r[min] > L->length) { // 如果有小于当前最小值的关键字
min = j; // 将此关键字的下标赋值给min
}
}
if (i != min) { // 若min不等于i，说明找到最小值，交换
swap(L, i, min); // 交换 L->r[i]于 L->r[min]的值
}
}
}
- 时间复杂度分析
简单选择排序最大的忒单就是 交换移动数据次数相当少 ，节约相应的时间;
分析时间复杂度发现，无论是最好、最差的情况，其比较次数都是一样多；对于交换次数而言，最好的时候交换次数为0，最差的时候，也就是初始降序，交换次数为 n-1 次，总的时间复杂度依然为O(n²);
尽管与冒泡排序同为O(n²)，但简单选择排序的性能还是要优于冒泡排序。
三、直接插入排序
直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序列表中，从而得到一个新的、记录数增1的有序表。
void InsertSort(SqList *L) {
int i, j;
for (i = 2; i < L->length - 1; i ++) {
if (L->r[i] < L->r[i - 1]) {
for (j = i - 1; L->r[j] > L->r[0]; j --) {
L->r[j + 1] = L->r[j];
}
L->r[j + 1] = L->r[0];
}
}
}
从空间上来看，它只需要一个记录的辅助空间，因此关键还是看时间复杂度：
最好的情况，要排序的表本来就是有序的，没有移动记录，时间复杂度为O(n)；
最坏的情况，要排序的表是逆序的，记录的移动次数也达到最大值 (n + 4)(n - 1) / 2次，所以，时间复杂度为O(n²)。
从这里我们也可看出，同样的 O(n²) 时间复杂度，性能上看
直接排序 > 简单排序 > 冒泡排序
四、希尔排序
// 对顺序表L作希尔排序
void ShellSort(SqList *L) {
int i, j;
int increment = L->length;
do {
increment = increment / 3 + 1; // 增量序列
for (i = increment + 1; i <= L->length; i ++) { // 需将L->[i]插入有序增量子表
if (L->r[i] < L->r[i - increment]) {
L->r[0] = L->r[i]; // 暂存在L->r[0]
for (j = i - increment; j > 0 && L->r[0] < L->r[j]; j -= increment) {
L->r[j + increment] = L->r[j]; // 记录后移，查找插入位置
}
L->r[j + increment] = L->r[0]; // 插入
}
}
} while (increment > 1);
}
希尔排序的关键并不是随便分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式的移动，使得排序的效率提高。
五、堆排序
堆是具有下列性质的完全二叉树：
- 每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆
- 或者每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆
堆排序的基本思想：
将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末元素交换，此时末尾元素就是最大值），然后将剩余的 n-1 个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了。
// 2、已知L->r[s..m]中记录的关键字除L->r[s..m]意外以外均蛮子堆的定义
// 本函数调整L->r[s]的关键字，使L->r[s..m]称为一个大顶堆
void HeapAdjust(SqList *L, int s, int m) {
int temp, j;
temp = L->r[s];
for (j = 2 * s; j <= m; j *= 2) { // 沿关键字较大的孩子结局向下筛选
if (j < m && L->r[j] < L->r[j + 1]) {
++j; // j为关键字中较大的记录的下标
}
if (temp >= L->r[j]) {
break; // rc应插入在位置 s 上
}
L->r[s] = L->r[j];
s = j;
}
L->r[s] = temp; // 插入
}
// 1、对顺序表L进行堆排序
void HeapSort(SqList *L) {
int i;
for (i = L->length/2; i > 0; i--) { // 把L中的r构建成一个大顶堆
HeapAdjust(L, i, L->length);
}
for (i = L->length; i > 1; i ++) {
swap(L, 1, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
HeapAdjust(L, 1, i - 1); // 将 L->r[i..r-1] 重新调整为大顶堆
}
}
总体来说，堆排序的时间复杂度为O(nlogn)。由于堆排序堆原始记录的排序状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。这在性能上显然要远远好过冒泡、简单选择、直接插入的O(n²)的时间复杂度了
六、快速排序
快速排序（Quick Sort）的基本思想是：通过一趟排序将待
排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
// 3、变换顺序表 L 中子表的记录，使枢轴记录到位，并返回其所在位置,
// 此时在它之前（后）的记录均不大（小）于它
int Partition(SqList *L, int low, int high) {
int pivotKey;
pivotKey = L->r[low]; // 用子表的第一个记录作枢轴记录
while (low < high) { // 从表的两端交替向中间扫描
while (low < high && L->r[high] >= pivotKey) {
high--;
}
swap(L, low, high); // 将比枢轴记录小的记录交换到底端
while (low < high && L->r[low] <= pivotKey) {
low++;
}
swap(L, low, high); // 将比枢轴记录大的记录交换到高端
}
return low; // 返回枢轴所在位置
}
// 2、对顺序表 L 中的子序列 L->[low..high]作快速排序
void QSort(SqList *L, int low, int high) {
int pivot;
if (low > high) {
pivot = Partition(L, low, high); // 将 L->r[low..high]一分为二，算出枢轴值 pivot
QSort(L, low, pivot - 1); // 对低子表递归排序
QSort(L, pivot + 1, high); // 对高子表递归排序
}
}
// 1、对顺序表L作快速排序
void QuicSort(SqList *L) {
QSort(L, 1, L->length);
}
最优情况下，快速排序算法的时间复杂度为 O(nlogn)，最坏情况下时间复杂度为 O(n²)，快速排序是一种不稳定的排序算法。
可优化点：
- 优化选取枢轴（三数取中 / 九数取中）
- 优化不必要的筛选条件
- 优化小数组时的排序方法
- 优化递归操作
总结回顾
-
指标对比
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 简单选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 稳定 |
| 直接插入排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(nlogn) ~ O(n²) | O(n1.3) | O(n²) | O(1) | 不稳定 |
| 堆排序 | O(n²) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(n²) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(n²) | O(nlogn) | O(n²) | O(logn) ~ O(n) | 不稳定 |
从算法的简单性来看，我们将7种算法分为两类
- 简单算法：冒泡、简单选择、直接插入
- 改进算法：希尔、堆、归并、快速
以下是3种简单排序算法的移动次数比较
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 |
|---|---|---|---|
| 冒泡排序 | O(n²) | 0 | O(n²) |
| 简单选择排序 | O(n) | 0 | O(n) |
| 直接插入排序 | O(n²) | O(n) | O(n²) |
从综合各项指标来说，经过优化的快速排序是性能最好的排序算法，但是不同的场合我们也应该考虑使用不同的算法来应对。
