数据结构八大排序
| 目录 | 目录 |
|---|---|
| 顺序表 | 单链表（不带附加头结点） |
| 双链表（带附加头结点） | 栈（顺序表实现） |
| 队列（链式，不带附加头结点） | 二叉树 |
| 二叉树的非递归遍历 | 八大排序 |
前言
生活中有很多排序，比如排队做操，矮的在前，高的在后，再比如玩扑克牌，插入牌的例子。
排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。（注意看加粗部分）
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
生活中常见的排序
- 学校总分排序
- 淘宝购物排序
插入排序
引言：插入排序就跟我们生活中经常玩到的扑克牌一样，下面是理好顺序之后的样子，我们才知道这是同花顺，如果你手里拿到一张新牌 9，你又将如何插入？
基本思想：将一个记录（牌）插入到一个已经排好序的有序序列中，从而得到一个新的，记录数增 1 的有序序列。
1. 直接插入排序
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。
void InsertSort(int* a, int n)
{
// 注意循环次数 n-1 前i-1个数
for (int i = 0; i < n - 1; i++)
{
int end = i; // 前i-1个数已经排好序
int tmp = a[end + 1]; //保存第i个数,gap = 1直接插入排序
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];//小于就交换
--end;//-1 回退
}
else
break;
}
a[end + 1] = tmp; //如果交换了，就将空出来的位置给新插入的数
}
}
直接插入排序总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度为o(n^2)， 最坏时间复杂度o(n^2），最好时间复杂度o(n)
最坏的情况：2+…+n = (n+2)(n-1) / 2，为o(n^2)
最好的情况：有序，直接走一趟过程，为o(n)- 空间复杂度为o(1)，没有借助任何辅助空间
- 为稳定排序算法（相同的值的顺序没有发生变化）
2、希尔排序
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
- 选择一个增量序列t1，t2，…，tgap，其中ti>tj，tgap=1；
- 按增量序列个数gap，对序列进行gap 趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
动图过程如下：
void ShellSort(int* a, int n)
{
//以gap个单位排序
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;//一般取这个比较快，具体读者可以去看参考资料，也可以自己去测速度
//gap = gap / 2;
// 次数也换位n-gap
for (int i = 0; i < n - gap; i++)
{
int end = i; // 前i-1个数已经排好
int tmp = a[end + gap]; //保存第i个数,gap = 1为直接插入排序
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];//小于交换
end -= gap;//-1 回退
}
else
break;
}
a[end + gap] = tmp; //如果交换了，就将空出来的位置给新插入的数
}
}
}
希尔排序总结：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好多书中给出的希尔排序的时间复杂度都不固定（读者可以去翻阅书籍查看）
这里是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照：n^1.25~ 1.6n^1.25来算- 稳定性：不稳定（相同值的顺序在排序前后发生变化）
选择排序
基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
1、直接选择排序
- 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
- 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
- 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int maxi = begin, mini = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] > a[maxi])
maxi = i;//每次锁定最大值的索引，准备进行交换
if (a[i] < a[mini])
mini = i;//每次锁定最小值的索引，准备进行交换
}
Swap(&a[mini], &a[begin]); // 将最小值放前面
if (begin == maxi)//begin有可能等于maxi，需要进行检查
maxi = mini;
Swap(&a[maxi], &a[end]); // 将最大值放后面
++begin;//选出最大值最小值，缩小范围继续排序
--end;
}
}
begin == maxi 如下图，这里代码中检查了的，自己需要注意
直接插入排序总结：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定（相同值的顺序在排序前后发生变化）
2、堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。（这里需要读者知道堆的删除思想，即向下调整法）
//向下调整为大堆
void AdjustDwon(int* a, int n, int root)
{
int child = 2 * root + 1;
while (child < n)
{
//判断右孩子是否存在，并且大于左孩子
if (child + 1 < n && a[child] < a[child + 1])
{
++child;//将孩子比较调整为右孩子
}
// 升序建大堆，找到比父结点大的交换，继续找左右孩子
if (a[child] > a[root])
{
Swap(&a[child], &a[root]);//将父亲与孩子进行交换
root = child;//等于孩子成为新的父亲
child = 2 * root + 1;//找下一个孩子
}
else
{
break;//小于直接终止即可，不必调整
}
}
}
void HeapSort(int* a, int n)
{
//次数，只用找n-1-1 / 2次，左右孩子其中一个大小即可
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDwon(a, n, i);//先调整为大堆
}
int end = n - 1; //向下调整 将第一个结点与最后一个结点置换
//在进行向下调整，排序
while (end > 0)
{
Swap(&a[0], &a[end]);//将最大值放置末尾
AdjustDwon(a, end, 0);//继续调整为大堆，依次循环之后，就变为有序的了
--end;//-1
}
}
直接选择排序的特性总结：
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)，树的高度logN，循环次数N
- 空间复杂度：O(1)
- 稳定性：不稳定（相同值的顺序在排序前后发生变化）
交换排序
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
1、冒泡排序
基本思想：
- 两两元素之间进行比较，如果第一个比第二个大，就交换它们两个
- 对比相邻之间的两个数，一直到最后一对，最大值即在最后面
- 比较次数 -1，在重复上述步骤，即可达到排序的效果
void BubbleSort(int* a, int n)
{
for (int i = n; i > 0; --i)// 循环次数控制
{
int exchange = 0; // 判断是否有序
for (int j = 1; j < i; j++)
{
if (a[j - 1] > a[j]) // 进行比较
{
Swap(&a[j - 1], &a[j]);// 大于即交换
exchange = 1;// 判断是否已经进行比较
}
}
// 如果一趟下来为进行交换，则本身就有序，此时最优
if (exchange == 0)
break;
}
}
冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
注意：exchange的存在是判断走一趟这些元素直接是否进行了比较，如果没有进行比较，则本身就有序，不必在进行循环，此时时间复杂度最优，为o(n)。
2、快速排序
基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
void QuickSort(int* a, int left, int right)
{
if (left < right)
{
int keyi = PartSort3(a, left, right);// 对左右进行划分
QuickSort(a, left, keyi - 1); //左子序列
QuickSort(a, keyi + 1, right); // 右子序列
}
}
提示：上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
1、hoare版本
基本思想：hoare方法是让往右边（right）走找大的，往左边（left）走找小的，然后找到了就交换这两个值，然后交换left位置与keyi位置的值，最后返回索引 “left”，依次递归下去即可完成排序。
int PartSort1(int* a, int left, int right)
{
//有序的话，时间复杂度是o(n^2)，效率比较低，所以需要进行三数取中
int mid = GetMidIndex(a, left, right);
Swap(&a[left], &a[mid]);//将中位数放到left位置上
int keyi = left;//基准值需要是中位数，或者排序速度很慢
while (left < right)
{
//往左走找小的
while (left < right && a[right] >= a[keyi])
--right;
//往右走找大的
while (left < right && a[left] <= a[keyi])
++left;
//找到交换
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]); // 相遇还要交换一次
return left;
}
- 在hoare版本中我们进行了三数取中，为什么会有三数取中（取中间数）？
三数取中是为了提示排序的速度，如果一个序列是有序的，比如1 2 3 4 5 6
1、如果不进行三数取中，那么第一趟基准值为 1，拿hoare版本举例，此时我们往右找大，往左找小，先从右边走，往左找小，但是没有比1更小的，那么6要走n次，5要走n-1次，依次就是 n^2，此时时间复杂度为 o(n^2)，效率非常慢。
2、如果进行三数取中，基准值为 3 ，此时往右找大的，往左找小的，往右走需要走4次，往左走要走2次，此时找到的left的值就是取的中间数 3的索引，此时返回，然后继续递归，也就回到了二叉树的前序遍历，时间复杂度为o(n*logn)，相对于不进行三数取中，效率比较高
2、挖坑法
基本思想：先进行三数取中，找出中间值作为key值，坑位hole为key值的索引，然后在进行排序，先往左找小，找找到将该值给坑位索引处的值**（a[hole] = a[right]），该值的索引也赋值给坑位hole（hole = right），然后往右找大**，找到将该值给坑位索引处的值**（a[hole] = a[left]），索引也给坑位hole（hole = left），最后key值赋给坑位处的值（a[hole] = key）**，在返回hole即可，然后依次递归下去，直到有序
int PartSort2(int* a, int left, int right)
{
int mid = GetMidIndex(a, left, right);
Swap(&a[left], &a[mid]); // 三数取中进行交换
int key = a[left]; //key值
int hole = left; //坑位
while (left < right)
{
while (left < right && a[right] >= key)
{
--right;
}
a[hole] = a[right]; //将值换到坑位处
hole = right; //坑位索引替换
while (left < right && a[left] <= key)
{
++left;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole; //取的坑位返回
}
可以看出，挖坑法跟hoare法思想是差不多的，都是找一个值作为基准值，然后往左找小，往右找大，最后达到有序。
3、前后指针法
基本思想：初始化时，prev指针指向序列开头，cur指针指向prev指针的后一个位置，cur往左走找小于key的值，找到停止，prev在往左走一步，然后交换cur处和prev处的值，循环结束，在交换prev处和key处的值，返回prev，最后继续进行递归左右序列，即可达到有序。
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
int keyi = left;//序列开头作为key的值
int prev = left;//开始指向序列开头
int cur = prev + 1; // 开始指向prev后一个位置
while (cur <= right)//满足循环条件才继续执行
{
// 往左走找小于keyi的值，并且prev+1 要小于 cur
if (a[cur] < a[keyi] && ++prev <= cur)
{
Swap(&a[cur], &a[prev]);//交换
}
++cur;//继续往前走
}
Swap(&a[keyi], &a[prev]);//交换prev处和key处的值
return prev;
}
前后指针法理解起来比hoar版本，挖坑法难理解点，但最终也能达到排序，大致上是差不多的，读者根据自己喜欢用那种，最好全部掌握。
非递归的框架（栈实现）
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
Stack s;
StackInit(&s);
StackPush(&s, right);// 右先压栈，左在压栈
StackPush(&s, left);
while (!StackEmpty(&s))
{
int begin = StackTop(&s);
StackPop(&s);
int end = StackTop(&s);
StackPop(&s);
int keyi = PartSort1(a, begin, end);//先取得key值
if (keyi + 1 < end)
{
//右边序列进行排序
StackPush(&s, end);
StackPush(&s, keyi + 1);
}
if (keyi - 1 > begin)
{
//左边序列进行排序
StackPush(&s, keyi - 1);
StackPush(&s, begin);
}
}
StackDestroy(&s);// 记得销毁栈
}
总结：
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
归并排序
基本思想：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序核心步骤：
将整段序列分成一段一段小的序列，在进行排序，与快排的不同点是归并是从内到外排序，快排是从外到内，所以归并排序后面的非递归方式不能使用栈去进行排序（非常麻烦），相对用循环来说更简单。
递归：
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)
return; //区间变为 11就停止递归
int mid = left + (right - left) / 2; // 中间区间
_MergeSort(a, left, mid, tmp); // 前区间，递归分成多个小区间
_MergeSort(a, mid + 1, right, tmp); // 后区间
// 区间索引范围
int begin1 = left, end1 = mid; // 前区间索引
int begin2 = mid + 1, end2 = right; // 后区间索引
int index = left; //索引用来排序
while (begin1 <= end1 && begin2 <= end2)
{
//小的装入tmp数组中
if (a[begin1] <= a[begin2])
{
tmp[index] = a[begin1];//新数组tmp装排好序的值
index++;
begin1++;
}
else
{
tmp[index] = a[begin2];
index++;
begin2++;
}
}
//如果前区间未遍历完，则还要继续插入
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
//如果后区间未遍历完，也要继续插入
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
//第一次调用函数的区间是 0 -- n-1 不是 0 -- n 注意
for (int i = left; i <= right; ++i)
{
a[i] = tmp[i]; //拷贝给原数组
}
}
//递归进去
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);//开辟一块内存
assert(tmp != NULL);//检查是否开辟成功
_MergeSort(a, 0, n - 1, tmp);
free(tmp);//记得释放
}
非递归：
//这里与上面是一样的，只是没有进入递归进入内层
void _MergeSortNonR(int* a, int left, int right, int* tmp)
{
if (left >= right)
return;
int mid = left + (right - left) / 2;
// 区间索引范围
int begin1 = left, end1 = mid; // 前区间索引
int begin2 = mid + 1, end2 = right; // 后区间索引
int index = left; //索引用来排序
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[index] = a[begin1];//新数组tmp装排好序的值
index++;
begin1++;
}
else
{
tmp[index] = a[begin2];
index++;
begin2++;
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
//第一次调用函数的区间是 0 -- n-1 不是 0 -- n 注意
for (int i = left; i <= right; ++i)
{
a[i] = tmp[i]; //拷贝给原数组
}
}
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n); //临时数组
assert(tmp != NULL);//检查是否开辟失败
int gap = 1; //区间范围控制
while (gap < n)
{
for (int i = 0; i < n; i += gap)
{
//左右范围控制
int left = i, right = 2 * gap + i - 1;
// 注意，需要检查right的范围
if (right >= n)
right = n - 1;//范围最多到 n - 1
_MergeSort(a, left, right, tmp);
}
gap *= 2;
}
free(tmp); //释放开辟的动态空间
}
归并排序的特性总结：
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN) ， 二叉树的性质
- 空间复杂度：O(N)
- 稳定性：稳定
计数排序
基本思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
基本思想很简单，但是我们这里需要做一些处理，具体看图
// 计数排序
void CountSort(int* a, int n)
{
int min = a[0];
int max = a[0];
for (int i = 1; i < n; ++i)
{
if (a[i] < min)
min = a[i]; // 统计最小值到最大值的范围,开辟range个空间，避免浪费
if (a[i] > max)
max = a[i];
}
int range = max - min + 1; //开辟的空间个数
//int* count = malloc(sizeof(int) * range);
int* count = calloc(range, sizeof(int)); //最好用calloc，自动初始化为0
assert(count != NULL);
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;// 统计元素出现的次数
}
int i = 0;
// 将出现的元素依次装入数组中
for (int j = 0; j < range; j++)
{
while (count[j]--)
{
a[i++] = j + min;
}
}
free(count); //记得释放开辟的空间
}
排序算法复杂度及稳定性分析
时间复杂度需要说明的地方都解释了的，可以参考下面的图片自己在总结一遍，收获更大（切记：禁止记忆时间复杂度和空间复杂度）
