非递归版本
快速排序是一种常用的排序算法，基于递归的实现方式是最常见的。然而，使用递归实现快速排序可能会导致栈溢出的问题，尤其在输入规模较大时。为了解决这个问题，可以使用栈来实现快速排序的非递归版本。
在非递归版本的快速排序中，栈被用来模拟递归调用的过程。具体而言，该算法使用一个栈来存储待排序子数组的起始和结束索引。通过迭代的方式将原本递归调用的过程转化为循环，避免了递归函数调用的开销。
算法的基本思想是：：利用栈存储待排序子数组的起始和结束索引，在循环中每次从栈里面拿出一段区间单趟分割处理左右子区间入栈，将子数组划分为更小的子数组直到排序完成。
实现思路如下：
1.定义一个栈，用于记录每个待排序子数组的起始和终止索引。
2.将初始的起始索引和终止索引入栈，表示要对整个数组进行排序。
3.进入循环，直到栈为空
- 出栈得到当前子数组的起始和结束索引。
- 以子数组的第一个元素作为基准，对子数组进行划分，将小于基准的元素放在基准的左
侧，大于基准的元素放在基准的右侧。
- 如果基准元素的左侧仍有未排序的元素，将其起始索引和终止索引入栈；
-如果基准元素的右侧仍有未排序的元素，将其起始索引和终止索引入栈。
- 如果划分后得到的左右子数组的长度大于1，则将它们的起始和结束索引依次入栈。
4.当栈为空时，排序完成。
- 为了更仔细的体会，我自己手动模拟一下部分数据,
// 非递归版本的快速排序 void Quick_SortNoR(int* a, int left, int right) { ST s1; // 定义一个存储左右边界的栈 s1 STinit(&s1); // 初始化栈 s1 // 将初始左右边界入栈 STPush(&s1, right); STPush(&s1, left); while (!STEmpty(&s1)) { int begin = StackTop(&s1); // 取出栈顶的左边界 StackPop(&s1); // 弹出栈顶元素 int end = StackTop(&s1); // 取出栈顶的右边界 StackPop(&s1); // 弹出栈顶元素 int keyi = Part_Sort3(a, begin, end); // 对当前区间进行三数取中分区，并返回基准值的位置 keyi // [begin, keyi-1] keyi [keyi+1, end] if (keyi + 1 < end) { STPush(&s1, end); // 将当前基准值右边的边界入栈 STPush(&s1, keyi + 1); // 将当前基准值右边的边界入栈，准备分区 } if (keyi - 1 > begin) { STPush(&s1, keyi - 1); // 将当前基准值左边的边界入栈，准备分区 STPush(&s1, begin); // 将当前基准值左边的边界入栈 } } STDestroy(&s1); // 销毁栈 s1 }
这样，使用栈的非递归方式可以实现快速排序的算法思想，避免了递归带来的函数调用开销，同时保持了快速排序的效率。
快速排序优化
1. 三数取中法选key
当数组接近有序，快速排序会变的变成非常糟糕，时间复杂度是O(N^2)。
每次选择的基准元素可能会导致分割得到的左右子序列的大小差异很大，从而使得快速排序的效率下降。
具体来说，当数组接近有序时，快速排序的分割操作可能会将一个较小的元素放在一个较大的元素的右边，或者将一个较大的元素放在一个较小的元素的左边。这样一来，在每一次划分操作后，都会有一个较小的子序列和一个较大的子序列。如果这种情况持续发生，那么快速排序就会退化成类似于冒泡排序的过程，每次只能将一个元素放到它最终的位置上，排序的效率会大大降低。
为了解决这个问题，可以采用一些优化策略，如随机选择基准元素、三数取中法选择基准元素等，以尽量避免最坏情况的发生。我们这里就说下三数取中优化.
- 在三数取中法中，我们需要选择三个数来确定基准元素。通常情况下，我们选择子序列的
第一个元素、中间元素和最后一个元素作为候选的三个数。
具体步骤如下：
- 找到子序列的中间位置，即 (起始索引 + 结束索引) / 2。
- 比较子序列的第一个元素、中间元素和最后一个元素的大小。
- 选择这三个元素中的中间大小的元素作为基准元素。
- 返回下标
- 代码实现
// 三数取中法选择基准元素的索引 int GetMidIndex(int* a, int left, int right) { // 计算中间位置的索引 int mid = (left + right) / 2; if (a[left] < a[mid]) { // a[left] < a[mid] < a[right] if (a[mid] < a[right]) return mid; // a[left] < a[right] < a[mid] else if (a[right] > a[left]) return right; else return left; } else // a[left] > a[mid] { // a[left] > a[mid] > a[right] if (a[mid] > a[right]) return mid; // a[left] > a[right] > a[mid] else if (a[left] > a[right]) return right; else return left; } }
有的同学又有疑问，我加了三数取中，前面的代码是不是都要改。
其实并不需要，在GetMidIndex(a, left, right) 函数会返回一个基准值的索引，表示选择了基准值的位置。
在调用下交换函数swap(&a[left], &a[midIndex]) 将选择的基准值与数组的最左边元素 a[left] 进行交换。这样做是为了符合快速排序算法中的约定，即将基准值放在数组的最左边位置。
各版本的加上三数取中优化的代码
- Hoare版本
// Hoare版本 int Part_Sort1(int* a, int left, int right) { int midIndex = GetMidIndex(a, left, right); // 获取基准值的索引 swap(&a[left], &a[midIndex]); // 将基准值移到数组最左边 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[right]); // 将基准值放到正确的位置上 return right; // 返回基准值的索引 }
- 挖坑法
// 挖坑法 int Part_Sort2(int* a, int left, int right) { int midIndex = GetMidIndex(a, left, right); // 获取基准值的索引 swap(&a[left], &a[midIndex]); // 将基准值移到数组最左边 int key = a[left]; // 基准值 int tmp = left; // 坑的位置 while (left < right) { // 右边找小于基准值的元素 while (left < right && a[right] >= key) { right--; } a[tmp] = a[right]; // 将找到的元素放入坑中 tmp = right; // 左边找大于基准值的元素 while (left < right && a[left] <= key) { left++; } a[tmp] = a[left]; // 将找到的元素放入坑中 tmp = left; } a[tmp] = key; // 将基准值放入坑中 return tmp; // 返回基准值的索引 }
- 前后指针版本
// 前后指针版本 int Part_Sort3(int* a, int left, int right) { int midIndex = GetMidIndex(a, left, right); // 获取基准值的索引 swap(&a[left], &a[midIndex]); // 将基准值移到数组最左边 int keyi = left; // 基准值的索引 int prev = left; // 前指针 int cur = left + 1; // 后指针 while (cur <= right) { // 如果当前元素小于基准值，将其与前指针指向的元素交换，并移动前指针 if (a[cur] < a[keyi] && ++prev != cur) { swap(&a[prev], &a[cur]); } //这样写每次相同的元素都要交换 /* if (a[cur] < a[keyi]) { ++prev; swap(&a[prev], &a[cur]); }*/ ++cur; } swap(&a[prev], &a[keyi]); // 将基准值放到正确的位置上 return prev; // 返回基准值的索引 }
- 三路划分版本
void Quicl_Sors_Dfp(int* a, int left, int right) { if (left >= right) return; int midIndex = GetMidIndex(a, left, right); // 获取基准值的索引 swap(&a[left], &a[midIndex]); // 将基准值移到数组最左边 int key = a[left]; int begin = left; int cur = left + 1; int end = right; while (cur < end) { //a[c] < key，交换c和b位置的值，++b，++c if (a[cur] < key) { swap(&a[cur], &a[begin]); ++cur; ++begin; } //a[c] > key，交换c和e位置的值，--e else if (a[cur] > key) { swap(&a[cur], &a[end]); --end; } //a[c] == key，++c else { ++cur; } } //小 【b - e 相同】 大 //[left begin-1] [begin end] [end+1 right] Quicl_Sors_Dfp(a, left, begin - 1); Quicl_Sors_Dfp(a, end + 1, right); }
2. 递归到小的子区间时，可以考虑使用插入排序
在快速排序算法中，当子区间的大小足够小时，可以考虑使用插入排序来代替递归调用。这是因为插入排序在处理小规模数据时具有较好的性能。
当子区间的大小较小时，递归调用的开销可能会比排序本身的开销更大，因为递归调用需要额外的函数调用和栈空间的使用。而插入排序是一种简单且高效的排序算法，对于小规模的数据集，它的性能优于快速排序。
在实践中，可以通过设置一个阈值来决定是否使用插入排序。当子区间的大小小于阈值时，使用插入排序；否则，继续使用快速排序进行递归划分。
使用插入排序的优点是它对于部分有序的数据集具有较好的性能，因为插入排序每次将一个元素插入到已排序的序列中，对于有序度较高的数据集，插入排序的比较和移动操作会较少。
总而言之，使用插入排序来替代递归调用的快速排序可以在处理小规模数据时提高性能，并减少递归调用的开销。这是一种常见的优化策略，可以根据实际情况进行调整和实现。
在使用递归调用的快速排序算法中，对于10000个数的排序，当阈值为10时，我们可以估计一下在使用插入排序的情况下可以节约多少栈空间的使用。
假设每个子区间的大小平均为10（小于阈值），那么在使用插入排序的情况下，总共会有10000个数 / 10 = 1000个子区间。大约节省了77.5%的. 所以小区间优化还是很有必要的.
- 代码实现 插入排序我也不写了，具体实现请看该文章
// 快速排序 // 时间复杂度: O(logN*N) // 空间复杂度：O(logN) void Quick_Sort(int* a, int left, int right) { if (left >= right) return; int keyi = Part_Sort3(a, left, right); // 获取基准值的索引 // [begin, keyi-1] keyi [keyi+1, end] // 对基准值左边的子数组进行快速排序 // Quick_Sort(a, left, keyi - 1); // 对基准值右边的子数组进行快速排序 // Quick_Sort(a, keyi + 1, right); //快排:: 小区间优化 因为插入排序在小数组上的性能往往比快速排序更好。 if (keyi - left > 10) { // 对基准值左边的子数组进行快速排序 Quick_Sort(a, left, keyi - 1); } else { InsertSort(a + left, keyi - 1 - left + 1); } if (right - keyi > 10) { // 对基准值右边的子数组进行快速排序 Quick_Sort(a, keyi + 1, right); } else { InsertSort(a + keyi + 1, right - keyi + 1 - 1); } }
快速排序的特性总结：
快速排序是一种高效的排序算法，其核心思想是通过分治的策略将一个大问题分解为若干个小问题，并通过递归等方式解决这些小问题。
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
3.空间复杂度：O(logN)
4.稳定性：不稳定
稳定性是什么：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
在快速排序中：元素的交换是通过比较和交换来实现的，不保证相等元素的相对顺序不变。当基准元素与其他元素进行比较并交换位置时，相同元素的相对顺序可能会改变。
