技术交流QQ群:1027579432，欢迎你的加入！
一.概述
- 快速排序是冒泡排序的改进算法。它也是通过不断比较和移动交换来实现排序的，只不过它的实现增大了记录的比较和移动的距离，将关键字较大的元素从前面直接放到后面，关键字较小的元素直接从后面放到前面，从而减小了比较次数和交换次数。
二.原理
- 通过一趟排序将待排序数据分割成独立的两个子序列，其中左边的子序列均比右边的子序列中的元素小，然后分别对左右两个子序列继续进行排序，达到整个序列有序的目的。下面主要做两件事情，第一：从什么位置划分原始序列，将其变成左右两个子序列，即确定主元pivotkey的位置pivot。第二：分别对左右两个子序列进行递归操作，继续分割使其变得有序(即大于主元的元素都放在主元的右边，小于主元的元素都放在主元的左边)，整个过程如下图所示，其中主元的位置选的是待排序数组中的第一个元素50。
三.快速排序的优化
- 3.1优化主元的选择
- 快速排序算法的快慢取决于主元元素的选择。上面的例子中，选择的是待排序数组中的第一个元素。事实上，固定选择第一个元素作为主元是不合理的，如下图中的例子。选择9为主元后，进行一次交换操作后，整个序列没有发生实质性的操作。最坏情况下，待排序的数组是正序或逆序时，每次划分只得到一个比上次少一个元素的子序列，另一个子序列为空。此时快速排序的时间复杂度就变成了0(n**2)。一般选择主元的方法是：三数取中法。即取三个元素(三个元素分别是待排数组的左端点、中间端点、右端点)先进行从小到大的排序，然后选择中间端点的元素作为主元，如下图中的例子。当待排序数组是非常大时，采用九数取中法，即从数组中分三次采样，每次取三个数，三个数各取出中间的元素，总共得到三个中间元素。接着，从这三个中间元素中再取一个中间数作为主元。
- 3.2优化不必要的交换
- 增加一个哨兵位置，暂存主元的值。然后每次当小于主元的元素出现在右边或大于主元的元素出现在左边时，进行直接替换操作，不进行交换，如下图所示。
四.对小数组的优化
- 当待排序的数组元素个数很少时，采用快速排序有点大材小用。所以，设置一个阈值，用来判断是否采用快速排序。当待排序的数组中元素非常少时，使用直接插入排序算法；超过设定的阈值后，采用快速排序算法，如下面的代码所示：
// 因为快速排序适合由于待排序的序列很大的情况，所以设置一个阈值
void Qsort1(Sqlist *L, int low, int high)
{
int pivot;
if ((high - low) > MAX_LENGTH_INSERT_SORT)
{
pivot = Partition1(L, low, high);
Qsort1(L, low, pivot - 1);
Qsort1(L, pivot + 1, high);
}
else
{
InsertSort(L);
}
} - 上述Qsort1()函数进行快速排序时，在函数尾部有两次递归操作，这两次递归操作对性能有一定的影响，使用尾递归可以减少递归次数，提高性能。因为第二次执行递归操作针对的是右边的子序列，所以Qsort1(L, pivot + 1, high);可以替换为low = pivot+1;同时，增加一个while(low < high)的循环，采用迭代的方式不是递归的方法，缩减了堆栈的深度，从而提高了整体性能，具体见下面的代码:
// 由于Qsort1()函数在其尾部有两次的递归操作，如果待排序的序列划分极不平衡时，递归深度将趋于n，浪费栈空间
// 使用尾递归
void Qsort2(Sqlist *L, int low, int high)
{
int pivot;
if ((high - low) > MAX_LENGTH_INSERT_SORT)
{
while (low < high)
{
pivot = Partition1(L, low, high);
Qsort2(L, low, pivot - 1);
low = pivot + 1; // 尾递归
}
}
else
{
InsertSort(L);
}
}
五.快速排序完整代码
#include <iostream>
#include <malloc.h>
using namespace std;
#define MAXSIZE 10
#define N 9
#define MAX_LENGTH_INSERT_SORT 7 // 快速排序设定的阈值
typedef struct
{
int r[MAXSIZE + 1];
int len;
} Sqlist;
void show(Sqlist L)
{
for (int i = 1; i <= L.len; i++)
cout << L.r[i] << " ";
cout << endl;
}
void Swap(Sqlist *L, int i, int j)
{
int temp = L->r[i];
L->r[i] = L->r[j];
L->r[j] = temp;
}
// 确定主元
int Partition(Sqlist *L, int low, int high)
{
int pivotkey; // 主元
pivotkey = L->r[low];
while (low < high)
{
while (low < high && L->r[high] >= pivotkey) // 比主元大的放在主元的右边，不交换
high--;
Swap(L, low, high); // 比主元小的放在主元的右边，进行交换
while (low < high && L->r[low] <= pivotkey) // 比主元小的放在主元的左边，不交换
low++;
Swap(L, low, high); // 比主元大的放在主元的左边，进行交换
}
return low;
}
// 快速排序
void Qsort(Sqlist *L, int low, int high)
{
int pivot; // 主元位置
if (low < high)
{
pivot = Partition(L, low, high);
Qsort(L, low, pivot - 1);
Qsort(L, pivot + 1, high);
}
}
// 统一函数接口
void QuickSort(Sqlist *L)
{
Qsort(L, 1, L->len);
}
// 快速排序的优化
int Partition1(Sqlist *L, int low, int high)
{
// 确定主元位置---三数取中法
int pivotkey;
int center = low + (high - low) / 2; // 计算中间元素的下标
// 对左 中 右三个数进行排序
if (L->r[low] > L->r[high]) // 如果左边的数大于右边的数，进行交换操作
Swap(L, low, high); // 保证左边的数较小
if (L->r[center] > L->r[high]) // 如果中间的数大于右边的数，进行交换操作
Swap(L, center, high); // 保证中间的值较小
if (L->r[center] > L->r[low]) // 如果中间的数大于左边的数，进行交换操作
Swap(L, center, low); // 保证左边的值较小
pivotkey = L->r[low]; // L->r[low]已经成为整个序列左中右三个关键字的中间值
L->r[0] = pivotkey;
while (low < high)
{
while (low < high && L->r[high] >= pivotkey)
high--;
L->r[low] = L->r[high]; // 使用的是替换不是交换
while (low < high && L->r[low] <= pivotkey)
low++;
L->r[high] = L->r[low]; // 使用的是替换不是交换
}
L->r[low] = L->r[0]; // 将暂存的主元替换回L->r[row]
return low; // 返回主元的位置
}
// 直接插入排序
void InsertSort(Sqlist *L)
{
int i, j;
for (i = 2; i <= L->len; i++)
{ // 插入的元素从下标为2开始
if (L->r[i] < L->r[i - 1])
{ // 插入的元素比之前的元素值小，就进行交换操作
L->r[0] = L->r[i]; // 下标为0的位置存放的是哨兵
for (j = i - 1; L->r[j] > L->r[0]; j--)
L->r[j + 1] = L->r[j]; // 进行移动操作
L->r[j + 1] = L->r[0]; // 插入新的元素到正确的位置
}
}
}
// 因为快速排序适合由于待排序的序列很大的情况，所以设置一个阈值
void Qsort1(Sqlist *L, int low, int high)
{
int pivot;
if ((high - low) > MAX_LENGTH_INSERT_SORT)
{
pivot = Partition1(L, low, high);
Qsort1(L, low, pivot - 1);
Qsort1(L, pivot + 1, high);
}
else
{
InsertSort(L);
}
}
// 由于Qsort1()函数在其尾部有两次的递归操作，如果待排序的序列划分极不平衡时，递归深度将趋于n，浪费栈空间
// 使用尾递归
void Qsort2(Sqlist *L, int low, int high)
{
int pivot;
if ((high - low) > MAX_LENGTH_INSERT_SORT)
{
while (low < high)
{
pivot = Partition1(L, low, high);
Qsort2(L, low, pivot - 1);
low = pivot + 1; // 尾递归
}
}
else
{
InsertSort(L);
}
}
// 统一函数接口:改进后的快速排序
void QuickSort1(Sqlist *L){
Qsort1(L, 1, L->len);
}
// 统一函数接口：改进后的快速排序使用尾递归
void QuickSort2(Sqlist *L){
Qsort2(L, 1, L->len);
}
int main()
{
Sqlist L;
int d[N] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
for (int i = 0; i < N; i++)
L.r[i + 1] = d[i];
L.len = N;
cout << "快速排序前: ";
show(L);
cout << "快速排序后: ";
QuickSort(&L);
show(L);
cout << "改进的快速排序后: ";
QuickSort1(&L);
show(L);
cout << "改进的快速排序(尾递归)后: ";
QuickSort2(&L);
show(L);
return 0;
} #include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// （小数，基准元素，大数）。在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。
// 快速排序思路：
// 1. 选取第一个数为基准
// 2. 将比基准小的数交换到前面，比基准大的数交换到后面
// 3. 对左右区间重复第二步，直到各区间只有一个数
// 递归方法实现
void QuickSort(vector<int>& v, int low, int high){
if(low >= high)
return;
int first = low;
int last = high;
int key = v[first]; // 第一个元素作为主元
while(first < last){
while(first < last && v[last] >= key){
last--;
}
if(first < last){ // 不符合条件时，即后面元素比前面的元素小时，进行交换操作!
v[first++] = v[last];
}
while(first < last && v[first] <= key){
first++;
}
if(first < last){
v[last--] = v[first];
}
}
// 基准位置
v[first] = key;
QuickSort(v, low, first-1); // 前半部分递归
QuickSort(v, first+1, high); // 后半部分递归
}
// 最后一个元素作为主元
template<typename T>
void QuickSortRecursiveCore(T arr[], int start, int end){
if (start >= end)
return;
T mid = arr[end];
int left = start, right = end-1;
while(left < right){
while(arr[left] < mid && left < right){
left++;
}
while(arr[right] >= mid && left < right){
right--;
}
swap(arr[left], arr[right]);
}
if(arr[left] >= arr[end]){
swap(arr[left], arr[end]);
}
else{
left++;
}
QuickSortRecursiveCore(arr, start, left-1);
QuickSortRecursiveCore(arr, left+1, end);
}
template<typename T>
void QuickSortRecursive(T arr[], int len){
QuickSortRecursiveCore(arr, 0, len-1);
} 六、快速排序时间复杂度总结：
- 平均时间复杂度：O(nlogn)
- 最好情况：O(nlogn)
- 最坏情况：O(n**2)
- 空间复杂度：O(nlogn)——O(n)
- 稳定性：不稳定
京公网安备 11010502036488号