排序学习整理（2）

上集回顾

排序学习整理（1）-CSDN博客

2.3 交换排序

交换排序的基本思想是：根据序列中两个记录键值的比较结果，交换这两个记录在序列中的位置。

特点：

通过比较和交换操作，将键值较大的记录逐步移动到序列的尾部，而键值较小的记录逐步移动到序列的前部。
重复此过程，直到整个序列变得有序。

2.3.1 冒泡排序

冒泡排序（Bubble Sort）是一种简单的交换排序算法，其核心思想是通过重复的比较和交换操作，将序列中的最大值或最小值逐步“冒泡”到序列的尾部或头部。

基本思想

从序列的起始位置开始，依次比较相邻的两个元素：

如果它们的顺序不正确（如升序时前一个大于后一个），则交换它们的位置。

一轮比较后，当前未排序部分的最大值会被“冒泡”到末尾。

对剩下的未排序部分重复上述过程，直到整个序列有序。

算法步骤

初始化一个外层循环，用来控制需要比较的轮数。
在每轮循环中，从序列的开头开始，逐一比较相邻的两个元素，完成交换。
每轮排序结束后，未排序部分的长度减1。
重复上述操作，直到不需要再比较。

代码实现

void BubbleSort(int* arr, int n) {for (int i = 0; i < n - 1; i++) {  // 控制排序轮数int swapped = 0;  // 标记本轮是否发生交换for (int j = 0; j < n - 1 - i; j++) {  // 控制每轮比较次数if (arr[j] > arr[j + 1]) {  // 如果顺序不正确int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = 1;  // 标记发生了交换}}if (!swapped) {  // 如果本轮没有交换，说明已经有序break;}}
}

特性总结

算法复杂度

时间复杂度：
- 最好情况（序列已排序）：O(n)
- 最坏情况（序列逆序）：O(n^2)
- 平均情况：O(n^2)
空间复杂度：只需要常数级额外空间，空间复杂度为 O(1)。
稳定性：冒泡排序是稳定的排序算法，因为在比较相等元素时，它不会改变它们的相对位置。

优缺点和适用场景就不介绍了，冒泡的效率太过于低下，基本只用于教学了

2.3.2 快速排序

基本思想是：从待排序序列中随机选取一个元素作为基准值，依据该基准值将序列划分为两个子序列，其中左子序列的所有元素都小于基准值，右子序列的所有元素都大于基准值。然后对左右子序列分别重复这一过程，直到所有元素都排列到正确的位置上为止。

快速排序实现的主框架

//快速排序
void QuickSort(int* a, int left, int right){if (left >= right) {return;}//_QuickSort⽤于按照基准值将区间[left,right)中的元素进⾏划分int meet = _QuickSort(a, left, right);QuickSort(a, left, meet - 1);QuickSort(a, meet + 1, right);
}

主要有以下几种实现方法：

2.3.2.1 hoare版本

Hoare版本的快速排序是由算法提出者Tony Hoare在1962年设计的一种经典快速排序实现。该版本利用分区的思想，将数组分成两部分，使得一部分元素小于基准值，另一部分元素大于基准值。随后对两部分递归地应用快速排序，直到数组有序。

基本思想

核心操作是“分区”，使用左右指针分别从两端向中间扫描，找到需要交换的元素位置，最终将数组划分为左右两部分。

Hoare版本的快速排序通过分区的思想，将数组分成两部分：
左子数组中的元素均小于等于基准值。
右子数组中的元素均大于等于基准值。采用递归或迭代方式，对子数组继续进行快速排序，直到子数组长度为1或0，排序完成。

算法步骤

选择基准值：通常选择当前子数组的第一个元素作为基准值。
分区：
- 设置左右两个指针，分别指向当前子数组的两端。
- 右指针向左移动，找到第一个小于等于基准值的元素。
- 左指针向右移动，找到第一个大于等于基准值的元素。
- 如果左右指针未交错，交换两指针指向的元素，继续移动指针。
- 当左右指针交错时，分区完成，并返回分界点。
递归排序：
- 将数组按照分界点划分为左右两部分。
- 分别对左右部分递归执行上述过程，直到子数组长度为1或0。

问题1：为什么跳出循环后right位置的值⼀定不大于key？

当 left > right 时，右指针（right）已经移动到了左指针（left）的左侧。由于在分区过程中，左指针从左到右扫描的所有数据均不大于基准值（key），因此，跳出循环时，右指针（right）所指向的数据一定不大于基准值（key）。

问题2：为什么left 和 right指定的数据和key值相等时也要交换？

相等的值参与交换确实有一些额外消耗，但在实际中，数组可能存在大量重复元素，如果相等的值不参与交换，可能导致分区无法有效进行，从而影响排序的正确性和效率。

代码实现

// 交换函数
void Swap(int* p1, int* p2) {int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
// 快速排序
void QuickSort(int* a, int left, int right) {if (left >= right) { // 递归边界条件：区间只有一个元素或无元素return;}int begin = left, end = right; // 记录当前区间int keyi = left; // 基准值初始为第一个元素的下标while (left < right) {// 从右向左寻找比基准值小的元素while (a[right] >= a[keyi] && left < right) {right--;}// 从左向右寻找比基准值大的元素while (a[left] <= a[keyi] && left < right) {left++;}// 交换左右指针指向的值Swap(&a[left], &a[right]);}// 基准值归位Swap(&a[left], &a[keyi]);keyi = left; // 更新基准值位置// 对左右两部分递归排序QuickSort(a, begin, keyi - 1); // 左部分QuickSort(a, keyi + 1, end);   // 右部分
}

特性总结

算法复杂度

时间复杂度：

最好情况：O(n log⁡n)，每次分区都能平均划分为两半。

最坏情况：O(n^2)，当基准值总是选择到最小或最大值时，分区极不均衡。

平均情况：O(n log⁡n)，这是快速排序的典型表现。

空间复杂度：

O(log⁡n)：递归调用栈的深度。

优缺点

优点：

时间复杂度低：平均性能优于大多数排序算法，适合大规模数据。
原地排序：不需要额外的内存（仅递归栈空间）。
实现简单：通过分区逻辑实现高效的递归。

缺点：

不稳定：相同元素的相对顺序可能改变。
最坏情况效率低：对于完全有序或接近有序的数据，性能可能退化为O(n^2)。
递归调用栈问题：当数据规模过大时，递归调用深度可能导致栈溢出。

适用场景

大规模数据排序：快速排序在大数据场景下表现良好。
对稳定性无要求的场景：例如数字或字符排序。
通用排序需求：适合随机分布的无序数据集。

很明显的缺点不少，接下来介绍针对不同情况优化的另外三种快排

2.3.2.2 挖坑法

挖坑法（也称为坑填法或坑填交换法）是一种在排序算法中常用的技巧，特别是在快速排序和堆排序等算法的实现中。常用于处理两个元素交换问题，并且通常配合双指针或者分区操作来完成排序。

挖坑法在大量重复元素的情况下能减少交换次数，因此在这些场景下的优化效果明显。

基本思想

在元素交换过程中使用一个临时“坑”来存储一个元素的值，避免出现直接交换时元素覆盖的情况。这使得元素能够顺利地放到正确的位置，并且交换过程更加高效。

在快速排序的分区操作中，使用两个指针分别从两端扫描，遇到需要交换的元素时，利用“坑”存储其中一个元素，等另一个元素找到合适位置后再进行交换。最终基准值会被放置到“坑”中，实现正确的分区。

算法步骤

选择基准值：选择一个元素作为基准值（通常是第一个元素，或随机选择一个）。
左右指针扫描：

右指针从右侧开始，向左扫描，找到一个小于等于基准值的元素。

左指针从左侧开始，向右扫描，找到一个大于等于基准值的元素。

交换元素：

如果左指针和右指针没有交错，就交换这两个元素。

交换时，使用一个临时“坑”来存放其中一个元素的值，避免覆盖问题。

继续扫描：重复步骤2和步骤3，直到左右指针交错。
放置基准值：当左右指针交错时，将基准值放入当前“坑”位置，即完成分区。
递归排序：对左右两部分继续递归执行快速排序。

代码实现

void QuickSort(int* a, int left, int right) {if (left >= right) {return; // 当区间为空或只有一个元素时，递归结束}int begin = left;int end = right;int keyi = a[left]; // 基准值while (left < right) {// 从右向左寻找比基准值小的数while (a[right] >= keyi && left < right) {right--;}if (left < right) {a[left] = a[right]; // 填坑}// 从左向右寻找比基准值大的数while (a[left] <= keyi && left < right) {left++;}if (left < right) {a[right] = a[left]; // 填坑}}// 最后将基准值填入当前坑位a[left] = keyi;// 对左右区间递归排序QuickSort(a, begin, left - 1); // 左区间QuickSort(a, left + 1, end);   // 右区间
}

复杂度优缺点什么的和hoare版差不多，就介绍下与hoare法相对的优化情况吧

减少了交换次数：Hoare法在某些情况下需要交换多个位置，尤其是当扫描到不满足条件的元素时。挖坑法则通过填坑和直接交换，使得不需要频繁交换，进一步提升了效率。

保持数据的稳定性：挖坑法对于数据的处理方式相对较为稳定，避免了一些冗余的交换，且能够使得算法执行过程中更有序。

提高了数据的分区效果：挖坑法有助于实现更平衡的分区，尤其是在遇到重复元素或者大范围的相同值时，能够更均匀地进行分割。由于它通过“填坑”的方式保持了分区的连续性，因此在数据比较“均匀”的情况下能够带来较好的分割效果。

2.3.2.3 前后指针法

前后指针法（Two-pointer technique）是一种常用的技术，通常用于排序算法中的分区操作，特别是在快速排序的分区阶段。它通过设置两个指针从数组的两端向中间扫描，逐步找到需要交换的位置，从而实现分区操作。

前后指针法对于提高交换效率和减少不必要的交换有很大帮助，尤其是在数据量大且分布不均匀时

基本思想

使用两个指针，一个从数组的左端开始（前指针），另一个从数组的右端开始（后指针）。
前指针向右扫描，直到找到一个大于等于基准值的元素；后指针向左扫描，直到找到一个小于等于基准值的元素。
当前指针小于后指针时，交换这两个元素。交换后，继续移动两个指针，直到指针交错或相遇。
当指针交错时，结束扫描，将基准值放到指针交错的位置，完成分区。

算法步骤

选择基准值：选择一个基准值，通常选择数组的第一个元素或者最后一个元素。
初始化指针：设置两个指针，前指针（left）指向数组的起始位置，后指针（right）指向数组的结束位置。
扫描交换：
- 前指针：从左向右扫描，找到第一个大于等于基准值的元素。
- 后指针：从右向左扫描，找到第一个小于等于基准值的元素。
- 如果前指针小于后指针，则交换这两个元素，继续扫描。
基准值放置：当指针交错或相遇时，将基准值放入指针交错的位置，实现分区。
递归排序：对左侧和右侧子数组进行递归排序。

代码实现

Swap函数和上面的一样，就不再水一次了

void QuickSort(int* a, int left, int right) {// 如果区间无效或只剩一个元素，直接返回if (left >= right) {return;}// 设置初始基准值的位置（选取左边的元素作为基准值）int prev = left;  // prev 用于标记小于基准值的区域的末尾位置int cur = prev + 1;  // cur 用于遍历数组int pivotIndex = left;  // 基准值的位置（初始化为左边界）// 遍历整个区间，进行分区while (cur <= right) {// 如果当前元素小于基准值并且 prev 位置还没有与 cur 交换if (a[cur] < a[pivotIndex] && ++prev != cur) {// 如果符合条件，则交换 a[prev] 和 a[cur]Swap(&a[prev], &a[cur]);}++cur;  // 继续向右移动 cur 指针}// 最后将基准值与 prev 位置的元素交换，将基准值放到正确的位置Swap(&a[prev], &a[pivotIndex]);pivotIndex = prev;  // 更新基准值位置// 递归处理左右两个子区间QuickSort(a, left, pivotIndex - 1);  // 处理左区间QuickSort(a, pivotIndex + 1, right);  // 处理右区间
}

算法复杂度和优缺点一样继续与hoare同，优化在于

减少了交换次数：在Hoare法中，当左右指针扫描时，可能会在每次比较时都进行交换。而前后指针法则是只在需要时才交换，并且扫描过程是从两端开始的，能够更高效地找到合适的交换元素。

提高了分区效率：前后指针法可以确保左右指针每次都能找到需要交换的元素，因此比传统的Hoare法可能更快地将数据分割为两部分。这种方法避免了多个不必要的交换，提高了分区的速度。

优化情况：当数据的顺序比较混乱，或者大部分元素都较接近基准值时，前后指针法能够更有效地进行数据分割，减少了不必要的比较和交换操作。

2.3.2.4 非递归版本

饺子醋来咯，尝试尽量讲清楚

首先，这个版本需要栈来实现，学了栈再来，先上官方一点的介绍

传统的快速排序算法通常使用递归来实现分区和排序操作，但在某些情况下（例如，当递归深度过大时，可能导致栈溢出），可以使用非递归版的快速排序来避免递归带来的开销。非递归版快速排序使用显式的栈来模拟递归的调用，借助栈保存子数组的边界，逐步进行分区和排序。

非递归版则主要解决了递归带来的栈溢出问题，适合处理大规模数据或栈空间受限的情况，但对于排序速度并没有显著提高。

基本思想

非递归版快速排序的基本思想是：

使用栈代替递归的调用栈，通过显式地维护子数组的起始和结束位置。
每次分区操作后，将新的左右子数组的边界压入栈中，继续分区，直到栈为空。
由于栈模拟了递归过程，因此在内存方面比传统递归方法更加高效。

算法步骤

初始化栈：初始化一个栈，用来存储子数组的左右边界。
压入初始边界：将整个数组的左右边界压入栈中（即初始的低位和高位）。
分区操作：
- 从栈中弹出一个子数组的边界（即子数组的左端点和右端点）。
- 对该子数组进行分区操作，将其分为两个部分，基准值将放在正确位置。
压入子数组的边界：根据分区结果，将两个子数组的边界压入栈中，继续分区。
循环直到栈为空：重复上述步骤，直到栈为空，即所有子数组都被处理完。

其实就记住这个操作就好了，取栈顶区间，单趟排序，右左子区间入栈，不断重复及完成了整个函数。

代码实现

void QuickSortNonR(int* a, int left, int right) {ST st;STInit(&st);  // 初始化栈STPush(&st, right);  // 将右边界入栈STPush(&st, left);  // 将左边界入栈// 循环栈中的区间进行排序while (!STEmpty(&st)) {int begin = STTop(&st);  // 获取当前区间的左边界STPop(&st);  // 弹出左边界int end = STTop(&st);  // 获取当前区间的右边界STPop(&st);  // 弹出右边界int keyi = begin;  // 选择基准元素的初始位置int cur = begin + 1;  // 当前元素指针int prev = begin;  // 上一个小于基准元素的位置// 对区间内的元素进行排序while (cur <= end) {if (a[cur] < a[keyi] && ++prev != cur)  // 如果当前元素小于基准元素，则交换Swap(&a[prev], &a[cur]);++cur;}// 将基准元素放到正确的位置Swap(&a[keyi], &a[prev]);keyi = prev;  // 更新基准元素位置// 如果基准元素右边还有元素，继续排序右边区间if (keyi + 1 < end) {STPush(&st, end);STPush(&st, keyi + 1);}// 如果基准元素左边还有元素，继续排序左边区间if (keyi - 1 > begin) {STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);  // 销毁栈
}

栈实现的代码拿的是自己上次的栈的实现（基础）-CSDN博客

特性总结

算法复杂度

时间复杂度不变，空间复杂度正常也是 O(log⁡n)，但在最坏情况（有序或接近有序）会到O(n)

优缺点

优点：

避免栈溢出：非递归版的快速排序通过显式的栈来模拟递归，避免了因递归深度过大而导致栈溢出的风险。
节省栈空间：在递归方法中，栈的空间随着递归深度的增加而增加，而非递归版的快速排序通过显式栈管理，节省了递归栈空间。

缺点：

代码复杂度增加：非递归版的快速排序实现需要额外的栈结构来模拟递归，增加了代码的复杂性。
空间开销：尽管非递归版避免了递归栈的开销，但仍然需要额外的栈空间来存储子数组的边界，尤其对于大数组时，空间开销可能较大。

适用场景

递归深度较大时：当数据集非常大或递归深度较深时，非递归版快速排序通过避免栈溢出，使得排序过程更稳定。
内存限制：如果系统的栈空间有限，递归深度可能会导致栈溢出，此时非递归版更为适用。
需要改进性能的应用场景：对于一些对性能要求较高的应用，避免递归栈开销可能会带来一定的性能提升。

2.3.2.5 优化方法

2.3.2.5.1 三数取中

这个方法针对前面4种都不利的有序数组，从这个角度出发，我们有了三数取中的优化方式：

即选出mid=(left+right)/2

a[left]、a[right]、a[mid]这三个数中，值为中位数的那个数，然后将它于a[keyi]交换。

下面代码基于前后指针法

// 三数取中法
int GetMidi(int* a, int begin, int end) {// 计算中间元素的索引int mid = begin + ((end - begin) >> 1);// 判断mid元素是否在begin和end之间（即a[mid] 是位于 [a[begin], a[end]] 之间）if ((a[mid] >= a[begin] && a[mid] <= a[end]) || (a[mid] >= a[end] && a[mid] <= a[begin])) {return mid;  // 如果mid符合条件，返回mid的索引}// 如果a[begin]比a[mid]大，且a[begin]比a[end]小，或者a[begin]比a[mid]小，且a[begin]比a[end]大if ((a[begin] <= a[mid] && a[begin] >= a[end]) ||(a[begin] >= a[mid] && a[begin] <= a[end])) {return begin;  // 返回begin的索引}// 默认返回end的索引return end;
}// 快速排序主函数
int QuickSort(int* a, int begin, int end) {// 三数取中法优化：选择begin, mid, end三个元素的中位数作为基准元素int ki = GetMidi(a, begin, end); // 获取中位数元素的索引Swap(&a[begin], &a[ki]);  // 将中位数元素与begin位置的元素交换int keyi = begin;  // keyi是基准元素的初始位置int prev = begin;  // prev是扫描过程中已排序元素的最右边的位置int next = begin + 1;  // next是当前扫描到的元素位置// 前后指针法进行分区操作while (next <= end) {// 如果当前元素小于基准元素，交换到prev位置，并更新prev的位置if (a[next] < a[keyi] && ++prev != next) {Swap(&a[prev], &a[next]);}next++;  // 移动next指针，扫描下一个元素}// 将基准元素放到正确的位置（即prev位置），并返回基准元素的位置Swap(&a[keyi], &a[prev]);return prev;  // 返回基准元素的最终位置
}

注释这么详细就不用额外介绍了吧（

来下一个优化

2.3.2.5.2 小区间优化

当区间很小时，直接采用插入排序，就不用继续递归了。

void QuickSort(int* a, int left, int right)
{// 如果区间内的元素只有一个或没有，直接返回，因为已经是最小子问题（即已经排好序）if (left >= right)return;// 对于小区间（小于10个元素），使用插入排序，可以减少递归深度，提高效率if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);  // 对[a+left, right]区间的元素进行插入排序}else{int begin = left, end = right;int midi = GetMidi(a, left, right);  // 获取三数取中的基准索引Swap(&a[left], &a[midi]);  // 将基准元素交换到left位置// 定义keyi为基准元素的索引，进行分区操作int keyi = left;// 进行前后指针法分区while (left < right){// 从右边开始，找一个小于基准的元素while (left < right && a[right] >= a[keyi]){--right;  // right指针向左移动}// 从左边开始，找一个大于基准的元素while (left < right && a[left] <= a[keyi]){++left;  // left指针向右移动}// 找到符合条件的元素后交换Swap(&a[left], &a[right]);}// 将基准元素放到正确的位置（即left位置），完成分区Swap(&a[left], &a[keyi]);keyi = left;// 递归调用对左右子数组进行排序QuickSort1(a, begin, keyi - 1);  // 对左子数组进行排序QuickSort1(a, keyi + 1, end);    // 对右子数组进行排序}
}

下一篇就讲归并排序和非比较排序吧，估计不长了