冒泡排序
作为最简单的排序算法之一，也是我们最先接触到的排序算法，简单并且一看就明白的排序算法
动画演示
算法思路
两个数之间相互比较，较大的数向后移动，较小的数向前移动，经过 n 轮的比较之后，每一轮下来都可以确定一个最小的数，最终达到小的数在前，大的数在后，完成排序。
算法优化
因为冒泡排序是实打实的判断每一轮的两个元素，当某一趟遍历并没有进行数据元素交换时，说明已经排序好了，也就不需要进行迭代。这样可以通过使用一个标记 flag 记录这个状态。
- 如果发生了交换，flag 设置为 true
- 如果没有交换就设置为 false
这样当一轮比较结束后如果 flag 仍为 false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去，排序结束。
时间复杂度：$O(n^2)$，要进行n轮的比较，每一轮的比较平均进行（n + 1）/ 2次
代码实现
void BubbleSort(int *arr) {
for (int i = 1; i <= arr[0]; i++) {
for (int j = arr[0]; j > i; j--) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
// 优化
void BubbleSort2(int *arr) {
int flag = 1;
for (int i = 1; i <= arr[0] && flag; i++) {
flag = 0;
for (int j = arr[0]; j > i; j--) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
flag = 1;
}
}
}
}
选择排序
选择排序是一种简单直观的排序算法
动画演示
算法思路
先在数列中找出最大或最小的元素，放到序列的起始，然后再余下的数据中继续寻找最大或最小的元素，一次放到排序序列中，直到所有数据样本排序完成
时间复杂度：$O(n^2)$，进行了n轮的比较，每一轮找出最大或最小值的期望是（n+1）/ 2
代码实现
void SelectionSort(int *arr) {
for (int i = 1; i <= arr[0]; i++) {
// 需要交换的位置;
int exchangePos = i;
for (int j = i + 1; j <= arr[0]; j++) {
if (arr[exchangePos] > arr[j]) {
// 每一轮遍历找到一个最小值的下标;
exchangePos = j;
}
}
// 如果下标发生改变,说明存在比该位置更小的值,需要交换;
if (i != exchangePos) {
int temp = arr[i];
arr[i] = arr[exchangePos];
arr[exchangePos] = temp;
}
}
}
插入排序
通过构建有序序列，对于未排序的数列，在已排序序列中从后向前扫描，找到相应的位置并插入。类似打扑克牌的码牌，抓到一张牌，就要和原来手中的牌逐一比较，找到前一张不再大于手中待插入的牌时，即插入的位置
动画演示
算法思路
先将待排序序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序的序列，接着从头到尾依次扫描未排序序列，并将扫描到的每一个元素插入有序序列的适当位置，直到所有数据元素都完成排序
时间复杂度： $O(n^2)$，同样要确定n个位置，每个位置需要确定的平均次数为(n + 1)/2
代码实现
void InsertionSort(int *arr) {
for (int i = 1; i < arr[0]; i++) {
for (int j = i + 1; j > 1; j--) {
// 一直找到前一个位置不再大于插入数据的位置进行交换
if (arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}else {
// 增加这个break可以提高插入排序的速度;
break;
}
}
}
}
希尔排序
希尔排序也称为递减增量排序，是插入排序的一种改进版本，效率虽然高，但它是一种不稳定的排序算法。
插入排序对几乎排好序的数列操作时，效率是非常好的，但是插入排序每次只能移动一位数据，因此插入排序效率还是比较低；希尔排序则在插入排序的基础上进行了改进，先将整个数列分割成若干子序列分别进行插入排序，待整个序列中的数据基本有序后，再对全部数据依次进行插入操作
动画演示
算法思路
- 将数列分成 n 组，并对每组数据进行插入排序
- 将 n 组数据进行合并
- 重复 1 - 2 步骤，同时将增量 n 减少为 n / 2
时间复杂度：$O(n^{2/3})$，希尔排序的时间复杂度计算与其增量的分割有关
代码实现**
void ShellSort(int *arr) {
int inc = arr[0];
do {
// 设置增量
inc = inc / 2;
// i 的待插入序列数据[inc + 1, length]
for (int i = inc + 1; i <= arr[0]; i++) {
// 如果 arr[i] 小于它的序列组元素，则进行插入排序
if (arr[i] < arr[i - inc]) {
int temp = arr[i];
int j = i - inc;
for (; j > 0 && temp < arr[j]; j -= inc) {
arr[j + inc] = arr[j];
}
arr[j + inc] = temp;
}
}
} while (inc > 1);
}
堆排序
在了解堆排序之前，先来看看什么是最大堆和最小堆
最大堆就是指每一个根结点的值都比其左右子树的值要大，这样就可以得出根结点的值是所有结点中最大的；最小堆同理
堆排序是采用二叉堆的数据结构来实现的，虽然实质上还是一维数组。二叉堆是一个近似完全二叉树（完全二叉树在之前有所涉及，这里就不过多阐述）
二叉堆具有以下性质：
- 父结点的值总数大于或等于（小于或等于）任何一个子结点的值
- 每一个结点的左右子树都是一个二叉堆（都是最大堆或最小堆）
动画演示
算法思路
- 根据初始数组，构建二叉堆，保证所有的父节点比子节点的值大
- 每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为最大堆
时间复杂度：每次重新恢复堆的时间复杂度为O(logn)，对于取元素一共进行了n - 1次，再加上前面建立堆时n / 2次向下调整，每次调整时间复杂度也为O(logn)。二次操作时间相加还是O(nlogn)。
代码实现
void max_heaplfy(int *arr, int start, int end) {
int root = start;
while (1) {
int chlid = root * 2;
if (chlid > end) {
break;
}
if (chlid + 1 <= end && arr[chlid] < arr[chlid+1]) {
chlid += 1;
}
if (arr[root] < arr[chlid]) {
int temp = arr[root];
arr[root] = arr[chlid];
arr[chlid] = temp;
root = chlid;
}else break;
}
}
void HeapSort(int *arr) {
// 创建最大堆
int length = arr[0];
for (int i = length / 2; i > 0; i--) {
max_heaplfy(arr, i, length);
}
for (int i = length; i > 1; i--) {
int temp = arr[i];
arr[i] = arr[1];
arr[1] = temp;
// 将 [i, i - 1]调整成最大堆
max_heaplfy(arr, 1, i - 1);
}
}
归并排序
归并排序是采用分治法的一个典型应用。先递归分解数组，将数组不断地拆分下去，直到数组长度为 1，再将这些数组两两合并，从底层不断地递归回去，所以是两个子序列的合并，称为更大的序列，顾而为归并排序
动画演示
算法思路
- 递归分解，将数组分解成 left 和 right，如果这 2 个数组内部数据是有序的，则合并；如果无序，则对数组进行二分，直到分解出的小组只有一个元素，此时认为该小组内部有序
- 合并两个有序数组，比较两个数组的最前面的树，谁小就先取谁
- 重复步骤 2，直到一个数组为空
- 最后把另一个数组的剩余部分复制过来
时间复杂度：归并排序的效率是比较高的，设数组长为n，将数组分开成小数组一共要logn步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(n)，故一共为O(nlogn)。
代码实现
#define MAXINT 10000
void merge(int *arr, int *res, int low, int mid, int high) {
int start;
int count;
// 将 arr 中数据从小到大并入 res 中
for (start = mid + 1, count = low; low <= mid && start <= high; count++) {
if (arr[low] < arr[start]) {
res[count] = arr[low++];
}else {
res[count] = arr[start++];
}
}
// 将剩余的元素复制到 res 中
if (low <= mid) {
for (int i = 0; i <= mid - low; i++) {
res[count+i] = arr[low+i];
}
}
if (start <= high) {
for (int i = 0; i <= high - start; i++) {
res[count+i] = arr[start+i];
}
}
}
void mSort(int *arr, int *res, int low, int high) {
int mid;
int temp[MAXINT];
if (low == high) {
res[low] = arr[low];
}else {
// 分解数组
mid = (low + high) / 2;
// 左边数组递归分解
mSort(arr, temp, low, mid);
// 右边数组递归分解
mSort(arr, temp, mid+1, high);
// 迭代合并左右数组
merge(temp, res, low, mid, high);
}
}
void mergeSort(int *arr) {
mSort(arr, arr, 1, arr[0]);
}
/* 非递归实现 */
//对SR数组中相邻长度为s的子序列进行两两归并到TR[]数组中;
void MergePass(int SR[],int TR[],int s,int length){
int i = 1;
int j;
//①合并数组
//s=1 循环结束位置:8 (9-2*1+1=8)
//s=2 循环结束位置:6 (9-2*2+1=6)
//s=4 循环结束位置:2 (9-2*4+1=2)
//s=8 循环结束位置:-6(9-2*8+1=-6) s = 8时,不会进入到循环;
while (i<= length-2*s+1) {
//两两归并(合并相邻的2段数据)
merge(SR, TR, i, i+s-1, i+2*s-1);
i = i+2*s;
/*
s = 1,i = 1,Merge(SR,TR,1,1,2);
s = 1,i = 3,Merge(SR,TR,3,3,4);
s = 1,i = 5,Merge(SR,TR,5,5,6);
s = 1,i = 7,Merge(SR,TR,7,7,8);
s = 1,i = 9,退出循环;
*/
/*
s = 2,i = 1,Merge(SR,TR,1,2,4);
s = 2,i = 5,Merge(SR,TR,5,6,8);
s = 2,i = 9,退出循环;
*/
/*
s = 4,i = 1,Merge(SR,TR,1,4,8);
s = 4,i = 9,退出循环;
*/
}
//②如果i<length-s+1,表示有2个长度不等的子序列. 其中一个长度为length,另一个小于length
// 1 < (9-8+1)(2)
//s = 8时, 1 < (9-8+1)
if(i < length-s+1){
//Merge(SR,TR,1,8,9)
merge(SR, TR, i, i+s-1, length);
}else{
//③只剩下一个子序列;
for (j = i; j <=length; j++) {
TR[j] = SR[j];
}
}
}
void MergeSort2(int *L){
int *TR = (int *)malloc(sizeof(int) * L[0]);
int k = 1;
//k的拆分变换是 1,2,4,8;
while (k < L[0]) {
//将SR数组按照s=2的长度进行拆分合并,结果存储到TR数组中;
//注意:此时经过第一轮的归并排序的结果是存储到TR数组了;
MergePass(L, TR, k, L[0]);
k = 2*k;
//将刚刚归并排序后的TR数组,按照s = 2k的长度进行拆分合并. 结果存储到L->r数组中;
//注意:因为上一轮的排序的结果是存储到TR数组,所以这次排序的数据应该是再次对TR数组排序;
MergePass(TR, L, k, L[0]);
k = 2*k;
}
}
快速排序
快速排序是使用分治思想将一个序列分为两个子序列，而划分的依据是从数列中挑选一个合适的元素，该元素称为「基准」pivot。重新排列序列，所有比基准小的元素在基准前面，所有比基准大的元素在基准后面，等到分区结束之后，该基数就处于数列的中间位置。这这之后，重复这个操作，直到整个数列排序完成
动画演示
选取基准方法
- 固定位置：固定取数列的第一个或最后一个元素
- 随机选基准：取待排序数列中任意一个元素
- 三数取中：对待排序序列中low、mid、high三个位置上数据进行排序，取他们中间的那个数据作为枢轴，并用0下标元素存储枢轴
算法思路
- 从数列中挑出一个元素，称为『基准』
- 进行分区操作，即重新排序数列，将小于基准的元素放在基准之前，将大于基准的元素放在基准之后
- 递归地把小于基准值元素的子数列和大于基准值源的子数列排序
时间复杂度：最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)
代码实现
//计算基准, 同时保证小于基准的位于左边，大于基准的位于右边
int Partition(int *arr, int low, int higt) {
int pivotKey = arr[low];
while (low < higt) {
while (low < higt && arr[higt] >= pivotKey) {
higt--;
}
// 交换数字
int temp1 = arr[low];
arr[low] = arr[higt];
arr[higt] = temp1;
while (low < higt && arr[low] <= pivotKey) {
low++;
}
// 交换数字
int temp2 = arr[low];
arr[low] = arr[higt];
arr[higt] = temp2;
}
return low;
};
void QSort(int *arr, int low, int high) {
int pivot;
if (low < high) {
pivot = Partition(arr, low, high);
QSort(arr, low, pivot - 1);
QSort(arr, pivot + 1, high);
}
}
void QuickSort(int *arr) {
QSort(arr, 1, arr[0]);
}
快速排序优化
- 三数取中
- 当待排序序列的长度分割到一定大小后，使用插入排序
- 优化递归：快排函数在函数尾部有两次递归操作，可以进行尾递归优化
总结
常见排序算法效率比较
| 排序方式 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 |
| 插入排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 希尔排序 | $O(nlogn) - O(n^2)$ | $O(n^{2/3})$ | $O(n^2)$ | $O(1)$ | 不稳定 |
| 堆排序 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(1)$ | 不稳定 |
| 归并排序 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(n)$ | 稳定 |
| 快速排序 | $O(nlogn)$ | $O(nlogn)$ | $O(n^2)$ | $O(logn)-O(n)$ | 不稳定 |