数据结构学习笔记——排序
排序
1. 排序相关概念
稳定性：关键字相同的数据记录，排序后相对顺序仍保持不变
例如，两个25，在排序完后，有*的25仍在后方，说明该排序算法是稳定的
内部排序：数据元素全部放在内存中的排序
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排序
2. 常见排序算法及实现
2.1 插入排序
直接插入排序
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列
简单来说，待排序数据如下
排序轮次如下
每一轮排好一个数，下一轮新拿出来的数，插入到原来已排好的序列中，直到所有数都排好
直插特性总结：
- 元素集合越接近有序，算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 算法稳定
代码示例：
// 插入排序
void InsertSort(int* a, int n) {
for (int i = 1; i < n; i++) {
int temp = a[i];
int j = i;
while (j > 0)
{
if (a[j - 1] > temp) {
a[j] = a[j - 1];
}
else { break; }
j--;
}
a[j] = temp;
}
}
希尔排序（缩小增量排序）
希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，gap取更小的值（一般是gap/2），重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。
可以这么理解：
- 预排序，使数组接近有序
- 执行插入排序
看如下例子
待排序序列
取gap的值，一般是n/2，所以这里取3
排序后结果如第二行所示
一般来说gap /= 2后为1，但这里先取gap = 2以便理解
然后最后一趟gap = 1
希尔特性总结：
- 希尔排序是对直接插入排序的优化
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定
- 稳定性：不稳定
代码示例：
// 希尔排序
// 注意，如果每组各自排的话，会有四重循环（最外层gap变化，第二层不同组各自处理，最后两层为插入自带）
// 此处仅3层循环，使多组排序同时进行
void ShellSort(int* a, int n) {
int gap = n / 2;
while (gap)
{
for (int i = gap; i < n; i++) {
int temp = a[i];
int j = i;
while (j >= gap)
{
if (a[j - gap] > temp) {
a[j] = a[j - gap];
}
else { break; }
j -= gap;
}
a[j] = temp;
}
gap /= 2;
}
}
2.2 选择排序
选择排序
基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
看一下示例就好理解了
初始序列
选择特性总结：
- 直接选择效率一般，实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
示例代码
// 选择排序
// 此为优化过的选择，每一轮分别找到一个最大值和最小值，放于开头和末尾
void SelectSort(int* a, int n) {
int bg = 0, ed = n - 1;
while (bg < ed)
{
int min_idx = bg, max_idx = ed;
for (int i = bg; i <= ed; i++) {
if (a[i] > a[max_idx]) {
max_idx = i;
}
if (a[i] < a[min_idx]) {
min_idx = i;
}
}
int temp = a[bg];
a[bg] = a[min_idx];
a[min_idx] = temp;
temp = a[ed];
// 如果发生如下情况，此时bg的值经过交换已经到了min_idx中，需要调整max_idx的值
if (bg == max_idx){ max_idx = min_idx; }
a[ed] = a[max_idx];
a[max_idx] = temp;
bg++, ed--;
}
}
堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆
// 初始序列：21,25,49, 25*,16,08
那么初始集合如下
调整为最大堆（或根据需求调整为最小堆）
排序过程
堆排序特性总结：
- 使用堆来选数，效率高很多
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
示例代码
// 堆排序
void AdjustDwon(int* a, int n, int root) {
int parent = root;
int child = parent * 2 + 1;
while (child < n) {
if (child + 1 < n && a[child + 1] > a[child]) {
++child;
}
if (a[child] > a[parent]) {
int temp = a[child];
a[child] = a[parent];
a[parent] = temp;
parent = child;
child = parent * 2 + 1;
}
else { break; }
}
}
void HeapSort(int* a, int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
AdjustDwon(a, n, i);
}
for (int i = n - 1; i >= 0; i--) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
AdjustDwon(a, i, 0);
}
}
2.3 交换排序
冒泡排序
根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，逐个向后走（或者向前），把较大的放后面（或者放前面）
冒泡特性总结：
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
示例代码
// 冒泡排序
void BubbleSort(int* a, int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
快速排序(很重要！！！)
快排在面试中经常可能会让你手撕，而且变化也不少！务必熟悉熟悉再熟悉
1. 快排基本知识
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
if(right - left <= 1)
return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
int div = partion(array, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
// 递归排[left, div)
QuickSort(array, left, div);
// 递归排[div+1, right)
QuickSort(array, div+1, right);
}
上述为快速排序递归实现的主框架，与二叉树前序遍历规则非常像，在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可
将区间按照基准值划分为左右两半部分的常见方式有：
-
hoare版本
示例代码：
// 快速排序hoare版本 int PartSort1(int* a, int left, int right) { int key = left; while (right - left > 1) { while (right - left > 1 && a[right - 1] >= a[key]) { right--; } while (right - left > 1 && a[left] <= a[key]) { left++; } int temp = a[left]; a[left] = a[right - 1]; a[right - 1] = temp; } int temp = a[key]; a[key] = a[left]; a[left] = temp; return left; }霍尔版本效率不差，但是容易引发几个疑问：
- 为什么能保证相遇时的值一定比基准值小呢？
- 为什么要先让右边出发，再让左边出发呢？
- 如果右边或者左边一直到遇到另一方都没找到合适的值怎么办？
这些疑问经过推演是可以解决的，但这使得霍尔版本有了一定的理解门槛，于是就有了如下的挖坑法
-
挖坑法
挖坑法的效率和霍尔版本是一样的，但相对来说更容易理解
示例代码
// 快速排序挖坑法 int PartSort2(int* a, int left, int right) { int key = a[left], flag = 1; while (right - left > 1) { if (flag) { if (a[right - 1] >= key) { right--; } else { a[left] = a[right - 1]; flag = 0; } } else { if (a[left] <= key) { left++; } else { a[right - 1] = a[left]; flag = 1; } } } a[left] = key; return left; } -
前后指针版
这是与前两者不太一样的方法，还蛮新颖的，学校都没教
示例代码
// 快速排序前后指针法 int PartSort3(int* a, int left, int right) { int pre = left, cur = left + 1, key = left; while (cur < right) { if (a[cur] < a[key]) { pre++; int temp = a[pre]; a[pre] = a[cur]; a[cur] = temp; } cur++; } int temp = a[key]; a[key] = a[pre]; a[pre] = temp; return pre; }
2. 快排优化
快排相对来说效率还是不错的，因为在理想状态下，每次找到的基准值都恰好是中位数，分开来的左右序列长度是差不多的，看起来就和二叉树一样，如此效率就几乎能和堆排序媲美
但是，一旦遇到不理想的情况，效率就差很多了
试想，如果每次取到的基准值都是最小/最大的，那么下一组的序列长度和原来相比只小了一个单位，那么参考上图，树的高度可以达到n，复杂度将变为O(n^2)
更重要的是，作为递归调用的函数，对空间的消耗是很高的，而快排通常运用的场景绝对都是大体量的数据，这样一来，就很容易发生诸如栈溢出的情况，这是我们所不希望看到的
那么想要优化快排，以下是比较常见的方法
-
三数取中法选key
我们当然希望避免选到的key过大或者过小，毕竟这样总会使效率有所下降，其中之一的办法，就是取3个数，第一个，最后一个，以及中间一个，取这三个数的中间值作为key值，至少能某种程度上减小上述情况发生的概率
当然为了较少地改动之前已写过的代码，选到的key值可以和第一个值做个交换，然后再执行之前的代码即可
-
递归到小的子区间时，可以考虑使用插入排序
在数据量较小时，再使用快排，和其他排序算法（比如插入排序）相比，就没什么优势了，使用非递归的其他算法可以减少一些栈帧的开销
-
使用非递归方法
单独列一个，看下方
3. 非递归实现快排
我们知道，函数调用时所需要的空间是由栈分配的（至少在大多数编程语言中如此）在递归的函数中，每递归一次，就会多创建一个栈帧，占用栈的一部分空间
那么我们可以考虑用数据结构——栈（注意这和上面的栈不是同一个概念！！！）来模拟实现递归的调用过程，比方说在栈中存放每组的开头和结尾，直到栈空之前循环执行，这同样能完成任务，但好处在于：
- 不会再过多的创建栈帧，降低栈溢出的风险（这里指的是调用栈或执行栈，与数据结构的栈不同！）
- 使用的数据结构——栈，占用的空间是动态申请的，而动态申请的空间是由堆分配的，不会占用栈的空间
- 堆的空间是比栈的空间大得多的，所以总体来说，空间调用的安全性更高了
参考代码如下
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right) {
stack<int>stk;
stk.push(left);
stk.push(right);
while (!stk.empty())
{
right = stk.top();
stk.pop();
left = stk.top();
stk.pop();
if (right - left <= 1) { continue; }
int temp = PartSort1(a, left, right);
stk.push(left);
stk.push(temp);
stk.push(temp + 1);
stk.push(right);
}
}
当然既然想到了用数据结构的栈来实现非递归，就不可避免的想到能不能用队列
这当然是可以的，不过，不同组的执行顺序会有所不同，我们可以看下对比图
-
用栈实现非递归
-
用队列实现非递归
之前说过，快速排序递归实现的主框架，与二叉树前序遍历规则非常像，用栈实现的非递归也是如此，而相应的，用队列实现非递归则和层序遍历很相似，事实上，我们实现层序遍历就是利用了队列
再广义一点的说，其实树的前中后序遍历，其实都是深度优先遍历，而层序遍历，则是广度优先遍历
可以尝试下树的前中后序能否用非递归来写
快排特性总结：
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
2.4 归并排序
基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
核心步骤
归并排序相应的，类似树的后序遍历
参考代码
// 归并排序递归实现
void _MergeSort(int* a, int* temp, int bg, int ed) {
if (bg == ed) { return; }
int mid = (bg + ed) / 2;
_MergeSort(a, temp, bg, mid);
_MergeSort(a, temp, mid + 1, ed);
int i = bg;
int bg1 = bg, ed1 = mid, bg2 = mid + 1, ed2 = ed;
while (bg1 <= ed1 && bg2 <= ed2)
{
if (a[bg1] < a[bg2]) {
temp[i++] = a[bg1++];
}
else {
temp[i++] = a[bg2++];
}
}
while (bg1 <= ed1)
{
temp[i++] = a[bg1++];
}
while (bg2 <= ed2)
{
temp[i++] = a[bg2++];
}
for (int j = bg; j <= ed; j++) {
a[j] = temp[j];
}
}
void MergeSort(int* a, int n) {
int* temp = new int[n];
_MergeSort(a, temp, 0, n - 1);
delete[]temp;
temp = NULL;
}
非递归实现归并
根据之前非递归实现快排的经验，我们可能会先想到使用栈，但实际上，由于归并和后序的相似性，对栈的空间占用就会很高（尝试自己推演看）实际上，使用循环迭代的方式也可以实现
使用一个迭代变量gap，表示两组归并的长度，每一轮gap*2
在每一轮中，从左往右循环归并不同组
需要注意一下的就是越界问题
示例代码
void MergeSortNonR(int* a, int n) {
int* temp = new int[n];
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap) {
int bg1 = i, ed1 = i + gap - 1;
int bg2 = i + gap, ed2 = i + 2 * gap - 1;
if (bg2 >= n) { break; }
if (ed2 >= n) { ed2 = n - 1; }
int j = i;
while (bg1 <= ed1 && bg2 <= ed2)
{
if (a[bg1] < a[bg2]) {
temp[j++] = a[bg1++];
}
else {
temp[j++] = a[bg2++];
}
}
while (bg1 <= ed1)
{
temp[j++] = a[bg1++];
}
while (bg2 <= ed2)
{
temp[j++] = a[bg2++];
}
for (int k = i; k <= ed2; k++) {
a[k] = temp[k];
}
}
gap *= 2;
}
delete[]temp;
temp = NULL;
}
归并排序特性总结
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题（既可以做内排序，也可以做外排序）
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
2.5 非比较排序
常见的非比较排序有：基数排序、计数排序、桶排序，其中计数排序比较有实践意义，这里先介绍计数排序
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
计数排序特性总结
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限（一般是整数）
- 时间复杂度：O(MAX(N,范围))
- 空间复杂度：O(范围)
- 稳定性：稳定
基数排序和桶排序，看如下介绍
基数排序
基数排序是一种线性时间复杂度的排序算法，它通过依次对每一位进行排序来处理整数或字符串。这个“位”可以是指数字中的个位、十位、百位等，或者是字符串中的字符位置。基数排序通常使用计数排序或桶排序作为子程序来对每一位进行排序。它可以按照从最低有效位到最高有效位或者从最高有效位到最低有效位的方式进行排序。
优点：对于固定长度的关键字序列，基数排序可以在 O(nk) 时间内完成排序，其中 n 是关键字的数量，k 是关键字的最大长度。
缺点：基数排序依赖于数据类型，适用于整数或字符串等离散且有固定长度的数据结构。
桶排序
桶排序是将数组分到有限数量的桶里，每个桶再单独排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序）。桶排序假设输入是由一个随机过程生成的，并且均匀分布在区间 [0, 1) 上。当输入数据能够均匀分配到各个桶中时，桶排序的效果最佳。
优点：如果输入数据能均匀地分布到各个桶中，那么桶排序的时间复杂度可以达到 O(n + k)，这里 n 是元素数量，k 是桶的数量。
缺点：桶排序的性能很大程度上取决于输入数据的分布情况。如果数据不是均匀分布的，某些桶可能会包含过多的元素，导致效率降低。