十大排序 —— 快速排序
- 快速排序
- 一些坑
- 快速排序的性能
- 优点：
- 缺点：
- 性能优化：
我们今天来看看十大排序中很出名的一个算法——快速排序：
快速排序
快速排序（Quick Sort）是一种经典的、高效的排序算法，属于比较排序算法的一种。它的基本思想是通过分治法（Divide and Conquer）将待排序的序列分割成两个子序列，然后递归地对子序列进行排序，最后将子序列的结果合并起来得到最终的排序结果。
快速排序的具体步骤如下：
- 选择基准值（Pivot）：从待排序序列中选择一个元素作为基准值。通常情况下，可以选择序列的第一个元素、最后一个元素或者随机选择一个元素作为基准值。
- 分区（Partition）：将待排序序列按照基准值进行分区，将小于基准值的元素放在基准值的左边，将大于基准值的元素放在基准值的右边，基准值自身则被放在合适的位置。这一步骤可以使用双指针法来实现，也就是从序列两端分别向中间移动指针，将元素进行交换，直到两个指针相遇。
- 递归排序：对分区后得到的左右两个子序列分别进行递归排序。
- 合并结果：将左右两个已经排序好的子序列合并起来，得到最终的排序结果。
快速排序的平均时间复杂度为O(nlogn)，其中n为待排序序列的长度。它是一种原地排序算法，不需要额外的辅助空间，因此空间复杂度为O(logn)。快速排序是一种非稳定排序算法，即相同元素的相对位置在排序后可能会改变。
我们一步一步来看：
我们这里有一个数组：
我们传入一个区间，我这里一般会用begin和end：
这步要注意，要不后面会踩坑，然后我们对传入的参数进行二次命名，命名为left，right:
我们left下标里的数为基准：
我们先从右边走，一开始，a[right] = -1比12小，但是却在12的右边，这个时候right下标停住：
这个时候开始往left往右边走，这个时候有个问题a[left]的值是12，我们的标准值也是12，我们该如何处理？
答案是我们直接放过，标准值我们直接最后处理，放到合适的位置上：
交换：
依次类推：
之后，right和left会走到一起：
这个时候处理标准值：直接交换stander和left：
这个时候，我们看12左边，全是比12小的，12右边全是比12大的：
这个时候，用同样的方法处理左区间和右区间：
```cpp
/**
* 快速排序函数
* @param array 待排序的整型数组指针
* @param begin 数组的起始索引
* @param end 数组的结束索引
*/
void quick_sort_part(int *array, int begin, int end) {
int left = begin; // 初始化左指针
int right = end; // 初始化右指针
// 当左指针小于右指针时继续排序
if (left >= right) {
return;
}
int stander = left; // 选择数组起始位置的元素作为基准值
// 外层循环：直到左右指针相遇
while (left < right) {
// 移动右指针，直到找到一个小于等于基准值的元素或右指针到达左指针
while (right > left && array[stander] <= array[right]) {
right--;
}
// 移动左指针，直到找到一个大于等于基准值的元素或左指针到达右指针
while (left < right && array[stander] >= array[left]) {
left++;
}
// 如果左右指针未相遇，则交换这两个元素的位置
if (left < right) {
swap(array[left], array[right]);
}
}
// 将基准值放到最终位置（左右指针相遇的位置）
swap(array[stander], array[left]);
// 对基准值左边的子数组进行快速排序
quick_sort_part(array, begin, left - 1);
// 对基准值右边的子数组进行快速排序
quick_sort_part(array, left + 1, end);
}
这段注释解释了每个关键步骤的目的和逻辑，有助于理解快速排序算法的实现细节。
一些坑
如果有些同志第一次接触这个算法，可能会写出这样的代码：
//快速排序
void quick_sort_part(int* array, int left, int right)
{
if (left >= right)
{
return;
}
int stander = left;
while (left < right)
{
while (right > left && array[stander] <= array[right])
{
right--;
}
while (left < right && array[stander] >= array[left])
{
left++;
}
if (left < right)
{
swap(array[left], array[right]);
}
}
swap(array[stander], array[left]);
quick_sort_part(array, 0, left - 1);
quick_sort_part(array, left + 1, right);
}
然后发现：
咋排序还只排一半呀？右半为啥不排了？
仔细，想想这份代码我们是直接拿来就对right大张旗鼓修改：
所以执行到quick_sort_part(array, left + 1, right)时，right被污染了，自然不会排了，正确的做法是备份一份，这就是为什么我取了两个不同的别名：right，end：
快速排序的性能
快速排序是一种非常高效的排序算法，在平均和最好的情况下具有O(n log n)的时间复杂度，其中n是数组中的元素数量。这意味着对于大规模数据集，它的性能通常优于O(n^2)的排序算法，如冒泡排序或选择排序。
优点：
- 效率高：在大多数实际情况下，快速排序都非常快，因为它的内部循环可以在大多数架构上高效执行。
- 原地排序：除了递归调用栈外，快速排序不需要额外的存储空间，是一种原地排序算法。
- cache友好：由于其分区操作，快速排序往往能很好地利用CPU缓存，提高执行效率。
缺点：
- 最坏情况性能：在最坏的情况下，即输入数组已经是正序或逆序时，快速排序退化为O(n^2)的时间复杂度。但这种情况可以通过随机选取或“三数取中”等策略来避免。
- 非稳定排序：快速排序不是稳定的排序算法，即相等的元素可能会因为排序而改变它们的原始相对位置。
- 递归开销：快速排序使用递归来排序子数组，当深度很大时，递归调用栈可能会消耗大量内存，特别是对于极大数组。针对此，可以采用尾递归优化或者迭代的方式来减少递归开销。
性能优化：
- 尾递归优化：在某些递归调用中，可以直接修改参数后调用自身，避免栈的额外增长。
- 小数组时切换到插入排序：对于小数组，快速排序的优势不明显，此时可以切换到插入排序，因为插入排序在小数组上的效率更高。
- 三数取中法：选择基准时，从首、中、尾三个元素中选择中位数作为基准，可以有效避免最坏情况的发生。
- 非递归实现：使用栈来模拟递归调用，减少递归深度，防止栈溢出。
这里实现一下三数取中：
#include<algorithm> // 包含 std::swap 函数
// 三数取中法选择基准值索引
int GetIndex(int* a, int left, int right) {
int mid = (left - right) / 2 + right; // 计算中间索引
// 比较三个元素的大小，返回中间值的索引
if (a[mid] < a[left]) {
if (a[right] < a[mid]) {
return mid;
} else if (a[left] < a[right]) {
return left;
} else {
return right;
}
} else {
if (a[left] < a[mid]) {
return mid;
} else if (a[right] < a[left]) {
return right;
} else {
return left;
}
}
}
// 快速排序的分区函数
void quick_sort_part(int *array, int begin, int end) {
int left = begin;
int right = end;
if (left >= right) {
return; // 如果左边界大于等于右边界，直接返回
}
int pivot = GetIndex(array, left, right); // 使用三数取中法选择基准值索引
std::swap(array[pivot], array[left]); // 将基准值与左边界交换，确保基准值在正确的位置
while (left< right) {
while (right > left && array[left] <= array[right]) {
right--; // 从右向左找到第一个小于基准值的元素
}
while (left< right && array[left] >= array[right]) {
left++; // 从左向右找到第一个大于基准值的元素
}
if (left< right) {
std::swap(array[left], array[right]); // 交换这两个元素
}
}
std::swap(array[left], array[begin]); // 将基准值放到正确的位置
quick_sort_part(array, begin, left - 1); // 对左侧子数组递归排序
quick_sort_part(array, left + 1, end); // 对右侧子数组递归排序
}
如果嫌弃空间复杂度太高，我们还可以用迭代的方式实现：
// 分区函数，选取最后一个元素作为基准，将数组分为两部分，返回基准元素的最终位置
int partition(int* array, int left, int right) {
// 选择数组最右侧的元素作为基准值
int pivot = array[right];
// i 初始化为左侧索引减一，用于记录比基准值小的元素的最终位置
int i = left - 1;
// 遍历数组，从左侧开始到基准值的前一个位置
for (int j = left; j < right; ++j) {
// 如果当前元素不大于基准值（包括等于），则交换到左侧区域，并移动i指针
if (array[j] <= pivot) {
++i;
swap(array[i], array[j]); // 交换元素位置
}
}
// 将基准值放到中间，i+1的位置即为基准值的正确位置
swap(array[i + 1], array[right]);
// 返回基准值的索引位置
return i + 1;
}
// 非递归实现快速排序的函数
void quick_sort_iterative(int* array, int size) {
// 如果数组长度小于等于1，无需排序，直接返回
if (size <= 1) {
return;
}
// 使用栈来模拟递归调用的函数栈
stack<int> stack;
// 初始时，将整个数组的左右边界压入栈
stack.push(0);
stack.push(size - 1);
// 当栈非空时，持续进行排序
while (!stack.empty()) {
// 先弹出右边界，再弹出左边界
int end = stack.top(); stack.pop();
int begin = stack.top(); stack.pop();
// 对当前区间进行分区，并获取基准元素的索引
int pivotIndex = partition(array, begin, end);
// 如果基准值左侧还有未排序的元素，则将左侧区间压入栈
if (pivotIndex - 1 > begin) {
stack.push(begin);
stack.push(pivotIndex - 1);
}
// 如果基准值右侧还有未排序的元素，则将右侧区间压入栈
if (pivotIndex + 1 < end) {
stack.push(pivotIndex + 1);
stack.push(end);
}
}
}
int main() {
int array[] = { 12,34,14,7,2,100,4,5,1,1000,888,0,221,2,-1 };
int size = sizeof(array) / sizeof(array[0]);
quick_sort_iterative(array, size);
// Print sorted array
for (int i = 0; i < size; ++i) {
cout << array[i] << " ";
}
cout << endl;
return 0;
}
