1. 简介
神说, 要有光. 于是就有了光. 神说要有快排, 于是就有了快排.
快速排序Quick Sort的发明者 托尼 霍尔 是1980年的图灵奖得主. 快速排序就是他发明的. 当时发明的背景是: 由于霍尔要高效地对俄语词汇进行排序以优化翻译程序, 而当时的排序算法(如冒泡, 插入排序)效率较低, 平均时间复杂度为 O(n2). 霍尔受分治法 (Divide and Conquer)思想启发, 提出了基于 "分区" (Partition) 的递归排序方法. (这段AI获取)
2. 核心思想
分区 (Partition): 指的是选一个基准值 Pivot, 将比基准值小的放在它的左侧, 比它大的放在右侧. 然后, 分别在左边区域 (比基准值小的区域) 和右边区域 (比基准值大的区域) 做相同的操作即再在左右两边选基准值, 再划分为两个区域, 一直到划分的区域即子序列长度为1, 即只有一个元素为止.这个就是快速排序的核心思想.
3.算法实现方式
分区法据我了解到有三种: (因为很早前写的,细节解释可能有误, 注意甄别)
3.1 第一种是 Naive Partition (朴素分区法)
这种方法我用 C++ 实现过, 不过我是看到某个Python的实现, 我根据它的实现, 用 C++ 翻译而已. 就是我们选一个基准值, 然后遍历元素, 比它小的我们额外存放到一个临时空间中, 比它大的也一样. 然后再将临时空间中的比基准值小的搬回原来的存储空间中, 再放基准值, 然后把比基准值大的放到基准值的右边. 再分别递归处理基准值左边和右边的区域. 如果某一轮没有找到比基准值小或大的值, 则左边或右边不再递归处理.
3.2 第二种是 Lomuto Partition (洛穆托分区法)
它维护两个指针 (下标), i 和 j . 依次从最左边的元素遍历到最末元素的前一个 (倒数第二个) , 并且选择最末元素为基准值. i 初始值指向 -1, j 指向第一个元素, 如果当前 j 指向的元素比基准值小, 则增加 i 的值, 并交换 i 和 j 指向的元素, 也就是将比基准值小的元素往后摆放. 如果 j 指向的元素比基准值大, 则不动它. i 增加只在发生交换时增加, j 是每次无论交换与否都要增加.最终 i + 1 的位置就是返回的基准值的位置, 再递归处理 i + 1左边和右边.
3.3 第三种是 Hoare Partition (霍尔分区法)
这也是快排原始版本, 由霍尔本人发明, 好像也是最快的实现方式. 它也维护两个下标 low 和 high, 只是从元素序列的两边分别遍历, 一个往后, 一个往前. 并且一般选第一个元素为基准值. 往后移的下标 low 找到比基准值大于等于的值, 往前移的 high 下标找比基准值小于等于的值, 找到则停止, 此时如果 low 和 high 还没相遇, 则交换它俩. 即将大的往后放, 小的往前放. 若相遇则返回 high下标. 这个 high 下标的位置就是基准值的位置. 然后递归处理基准值左边和右边.
(如果文字抽象或这里没写正确, 可以看实现代码在纸上推演, 推两轮自然明白, 我这里就不画图了, 画图有点耗时间)
4. 代码实现
4.1 第一种朴素分区法
注释也比较详细, 思想就是刚刚介绍的, std::array 模版类是 C++ 中的一种数组/容器, std::vector可能更适合长度经常变化的数组, std::array 数组长度固定, 效率比 std::vector 高, 而 std::array 又封装了一些额外的功能 (什么边界检查,还有一些方法) 比原始数组好用. ( C++的几种数组效率可以用百万级的元素或千万级的元素来测试) . 这个版本虽不能完全算原创, 但也是半原创, 就是根据某个Python实现, 用 C++ 独立完成.
/*快速排序 朴素分区法 ?? C++版 08042024 by alan*/
#include <iostream>
#include <array>
const int SIZE = 10;
/*快速排序函数,start为排序起始下标,len为要排序的范围*/
bool quickSort(std::array<int, SIZE>& ar, int start, int len);
int main(void)
{
std::array<int, SIZE> numbers = { 0, 422, 12, 4, 111, 3, 5, 22, 200, 123 };
std::array<int, SIZE>::iterator ir; /*array模版类迭代器*/
std::cout << "The oringal array: "; /*原始数组*/
for (ir = numbers.begin(); ir != numbers.end(); ir++)
std::cout << *ir << " ";
quickSort(numbers, 0, numbers.size());
std::cout << "\nAfter quick sorted: "; /*排序后数组*/
for (int x : numbers)
std::cout << x << " ";
return 0;
}
/*快速排序函数,start为排序起始下标,len为要排序的范围*/
bool quickSort(std::array<int, SIZE>& ar, int start, int len)
{
if (len == 1) //基线条件:如果长度为1不再递归排序
return 1;
std::array<int, SIZE> small; /*临时元素存放区*/
std::array<int, SIZE> larger;/*small为比基准因子小的元素*/
int i, j, k; /*larger为比基准因子大的元素*/
/*将原数组中比基准因子小和大的先搬出来*/
for (i = start + 1, j = 0, k = 0; i - start < len; i++)
if (ar[i] <= ar[start])
small[j++] = ar[i];
else
larger[k++] = ar[i];
/*基准因子arr[start]最终排在由比它小的元素组成的子*/
/*数组之后并且在比它大的元素组成的子数组之前的位置上*/
ar[start + j] = ar[start];
/*如果有比基准因子小的元素则搬回原数组,并对子*/
/*数组(由比基准因子小的组成)执行相同操作(递归)*/
if (j > 0) {
int m = 0;
for (i = start; i - start < j; i++)
ar[i] = small[m++];
quickSort(ar, start, j);//只对长度为j的部分排序
} //即只对原数组比基准因子
//小的那部分执行相同操作
/*若有比基准因子大的元素则执行相同操作*/
if (k > 0) {
int n = 0;
for (i = start + j + 1; (i - (start + j + 1)) < k; i++)
ar[i] = larger[n++];
quickSort(ar, start+j+1, k);
}
return 1; /*排序完成返回*/
}我用 Dev C++ 编译这个代码遇到下面错误, 这里是要在dev c++中添加 C++ 11 支持才行, std::array是 C++ 11 才引入的. 如果你用 VS 应该不用.
#ifndef _CXX0X_WARNING_H
#define _CXX0X_WARNING_H 1
#if __cplusplus < 201103L
#error This file requires compiler and library support for the \
ISO C++ 2011 standard. This support is currently experimental, and must be \
enabled with the -std=c++11 or -std=gnu++11 compiler options.
#endif
#endif
4.1.1 运行结果:
4.2 第二种和第三种 Lomuto 分区法和 Hoare 分区法
/* Quick Sort 快速排序 本程序使用Lomuto/Hoare两种分区法实现 */
#include <stdio.h>
#define MAX 10
void quicksort(long arr[], int low, int high); /* 快速排序主函数 */
int hoare_parti(long arr[], int low, int high); /* 霍尔分区法 */
int lomuto_parti(long arr[], int low, int high); /* 洛穆托分区法 */
void swap(long *pl, long *ph);
void printarr(long arr[], int len);
int main(void)
{
long array[MAX] = {
50, 80, 10, 70, 100,
30, 90, 40, 60, 20
};
printarr(array, MAX);
printf("\n");
quicksort(array, 0, MAX - 1);
printarr(array, MAX);
printf("\n");
return 0;
}
void quicksort(long arr[], int low, int high)
{
if (low < high) { /* 递归基线条件: low与high还没相遇才继续 */
int pindex = lomuto_parti(arr, low, high); /* 这里可选Hoare分区法或洛穆托分区法 */
quicksort(arr, low, pindex - 1); /* 递归处理左右两边的序列 */
quicksort(arr, pindex + 1, high);
}
}
/* Hoare分区法 */
int hoare_parti(long arr[], int low, int high)
{
long pivot = arr[low]; /* 选第一个为基准值 */
while (1) {
while (arr[low] < pivot) { low++; } /* 直到找到比基准值大的停下 */
while (arr[high] > pivot) { high--; } /* 直到找到比基准值小的停下 */
if (low >= high) { return high; } /* low和high没相遇继续否则返回基准值位置 */
swap(&arr[low], &arr[high]); /* 交换比基准值大的到后面反之放前面 */
}
}
/* Lomuto分区法 */
int lomuto_parti(long arr[], int low, int high)
{
int i, j;
long pivot = arr[high]; /* 选最后一个元素为基准值 */
i = low - 1;
for (j = low; j < high; j++) { /* i开始指向比基准值小的后一个 */
if (arr[j] <= pivot) { /* j从第一个开始, 若小于等于基准值 */
i++;
swap(&arr[i], &arr[j]); /* 则交换即将小的往前放,大的往后放 */
}
}
swap(&arr[i + 1], &arr[high]); /* 将基准值放到适当位置 */
return (i + 1); /* 返回基准值位置 */
}
void printarr(long arr[], int len)
{
int i;
for (i = 0; i < len; i++) {
printf("%ld ", arr[i]);
}
}
void swap(long *pl, long *ph)
{
long temp = *pl;
*pl = *ph;
*ph = temp;
}
上面两种分区法都测试通过了. 不过如果Dev C++编译选项还有 C++ 11的话, 会有警告, 应该关闭.因为这是 C. (C 和 C++ 有时候一样, 但有些特性还是不太一样, C++ 复杂一些,据大老C++之父本贾尼的说法是 C 的语法检查太松散. 所以C++检查也更严格)
4.2.1 运行结果:
注意: 以上的三种实现方式代码如果有错误注意甄别, 我并未仔细测试, 通过即停.
5. 结语
快速排序Quick Sort 还有多种优化方式, 感兴趣的读者可以研究一下. 例如基准值的选择就有多种不同的算法, 比如选第一个和中间, 还有最后一个元素三个取其一等等. 优化空间很大. 如果这篇文章缺少图示, 就自己在纸上根据代码推演, 推两盘就立刻明白是如何实现排序的了.
关于快速排序详细的时间复杂度分析请搜相关文章了解，不同分区方式它的时间复杂度有些区别，当然朴素分区因为要递归创建临时数组并且要搬运，所以是最慢的。而洛穆托和霍尔分区法因为是在原始数组上处理不用创建临时空间和搬运要快点，霍尔分区法因为是从两头往中间同时双向遍历所以最快，比洛穆托的要快。
这里我也人云亦云的给岀快排平均时间复杂度函数是 n * log n，其中 n 是元素个数。这个函数是对数，随着处理元素数量的增加，函数值增量趋势没有n * n 大，也就是说比什么冒泡，插入排序的n * n 要快，花费的时间更少，就是说快排的n*log n让计算机干的活儿的量比n * n的算法要少。至于如何得岀n * log n是前面也说了去搜相关文章，网上很多，都是分析要干多少活儿得岀的数学函数。
我实在无法理解为什么要把time complexity直译成时间复杂度这个抽象词汇，这个直接翻译为性能不行吗，反正只是衡量算法性能的一个数学函数。也许计算机科学家和数学家翻译有讲究吧。
喜欢就点赞收藏, 点赞收藏是我创作的动力.