您现在的位置是：首页 >技术交流 >数据结构_第十三关（2）：快速排序网站首页技术交流
数据结构_第十三关（2）：快速排序
简介数据结构_第十三关（2）：快速排序
目录
1.快速排序
基本思想：
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止
原理：
如上述图所示，此时就完成了一次单趟排序
单趟排序的作用：
- 使得key到了准确的位置
- 使得key左边的数都小于key，key右边的数都大于key
剩下的问题：让左区间有序、有区间有序，整体就ok了
然后再对其递归排序数组key的左边和右边，最终就可排好序
注意的点：
- 左边和右边都可以做key，但是
- 左边做key，右边要先走
- 右边做key，左边要先走
- 这是为了保证相遇的位置，一定比key要小（左边做key的情况下）
代码如下（递归实现）：
这个代码写起来会有很多坑，如下，单趟排序：
正确代码：
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int left = begin, right = end;
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[left], &a[keyi]);
keyi = left;
// [begin, keyi-1] keyi [keyi+1, end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi+1, end);
}性能比较
和上之前的简单排序算法的效率比较如下：
1万随机数据量下测得
10万随机数据量下测得
去掉选择排序和冒泡排序， 100万随机数据量下测得
去掉直接插入排序 ， 1000万随机数据量下测得
可以看出在数据量达到1000万级别时，快速排序似乎不占优势
因为key的取值，我们可以给快排进行优化，如第二部分。
快速排序的特性总结
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
在快速排序的时间复杂度计算中，最坏情况为：
没次key都是最大或者最小的，
实际情况：有序
此时，时间复杂度为O（N^2）
快排的中心思想就是：
- 不管你怎么选key，在第一趟排序之后，key的位置是正确的，
- 并且，key左边的数小于key，key右边的数大于key
因为key的选择可以不同，所以快排就有了一下的改进：
2.快速排序的优化
1）三数取中优化：
（主要对时间进行优化）
原理：
选择最左边，最中间，最右边的三个数作比较，选出最小的数作为key
代码如下：
//快排改进：key选值的三数取中
int GetMidIndex(int* a, int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
{
return mid;
}
else if (a[begin] > a[end])
{
return begin;
}
else
{
return end;
}
}
else // a[begin] > a[mid]
{
if (a[mid] > a[end])
{
return mid;
}
else if (a[begin] < a[end])
{
return begin;
}
else
{
return end;
}
}
}
void MidQuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
int key = left;
while (left < right)
{
// 右边先走，找小
while (left < right && a[right] >= a[key])
{
--right;
}
// 左边再走，找大
while (left < right && a[left] <= a[key])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[key]);
key = left;
// [begin, keyi-1] key [keyi+1, end]
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}加入三数取中之后，快排的时间复杂度就可以认为是：O（N*logN）；
性能比较：
之前1000万随机数据量下测得的数据：
加入三数取中后，1000万随机数据量下测得的数据：
可以看到，此时快排的效率有了明显的提高
2）小区间优化：
（主要对空间进行优化）
c++官方库，QST库都的快排都在用小区间优化
原理：
到最后10个数的时候，用递归的话，可以看到还需要4层深度的递归
对最后一小段区域的排序，我们用直接插入排序就行
代码如下：
//小区间优化（优化空间）
void SpaceQuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
if ((end - begin + 1) < 10)
{
// 小区间用直接插入替代，减少递归调用次数
InsertSort(a + begin, end - begin + 1);
}
else
{
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
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[left], &a[keyi]);
keyi = left;
// [begin, keyi-1] keyi [keyi+1, end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
}因为空间对效率的提示并不大，这里就不进行测试了，感兴趣的可以自己测一测
3. 挖坑法（快排的另一种思路）：
原理：
代码如下（递归实现）：
// 快速排序，挖坑法
void HoleQuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
//小区间优化
if ((end - begin + 1) < 10)
{
// 小区间用直接插入替代，减少递归调用次数
InsertSort(a + begin, end - begin + 1);
}
else
{
//三数选中间优化
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
int key = a[left];
int hole = left;
while (left < right)
{
// 右边找小，填到左边坑里面
while (left < right && a[right] >= key)
{
--right;
}
a[hole] = a[right];
hole = right;
// 左边找大，填到右边坑里面
while (left < right && a[left] <= key)
{
++left;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
// [begin, key-1] key [key+1, end]
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
}4. 快慢指针法（快排的第三种思路）：
原理：
代码如下（递归实现）：
//快慢指针法
void PointQuickSort(int* a, int begin, int end)
{
if (begin > end)
{
return;
}
//小区间优化
if ((end - begin + 1) < 10)
{
// 小区间用直接插入替代，减少递归调用次数
InsertSort(a + begin, end - begin + 1);
}
else
{
//三数选中间优化
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int prev = begin, cur = begin + 1;
int key = prev;
while (cur <= end)
{
while (cur <= end)
{
if (a[cur] >= a[key] && ++prev != cur)//++prev和cur的下标如果相等，就不要进行交换
{
Swap(&a[++prev], &a[cur]); //一定是先++prev，在用prev
}
cur++;
}
}
Swap(&a[prev], &a[key]);
PointQuickSort(a, begin, key);
PointQuickSort(a, key + 1, end);
}
}5.快速排序（非递归版代码）
非递归实现的方式有两种，一种是用栈实现，一种是用队列实现
用栈实现又叫做深度优先、用队列实现又叫做广度优先
原理如下：
基于栈的深度优先：
可以看出来，利用栈进行快排，是先左边的区间，后右边的区间，是往深的走，所以叫做深度优先
基于队列的广度优先：
基于队列的快排，是一层层的走的，和之前二叉树的层次遍历原理是相同的，因为是一层一层的走，所以叫做广度优先
代码如下（这里采用基于栈的深度优先）：
//快速排序（非递归）
//利用堆实现的叫做深度优先
void QuickSortNonR(int* a, int begin, int end)
{
ST st;
StackInit(&st);
StackPush(&st, begin);
StackPush(&st, end);
while (!StackEmpty(&st))
{
int right = StackTop(&st);
StackPop(&st);
int left = StackTop(&st);
StackPop(&st);
//进行一次快排
int prev = left, cur = left + 1;
int key = left;
while (cur <= right)
{
//++prev和cur的下标如果相等，就可以不用进行交换
if (a[cur] < a[key] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[key]);
key = prev;
// [left, key-1] keyi [key+1, right]
if (key + 1 < right)
{
StackPush(&st, key + 1);
StackPush(&st, right);
}
if (left < key - 1)
{
StackPush(&st, left);
StackPush(&st, key - 1);
}
}
StackDestroy(&st);
}6.源代码（VS2022下编写）
#include "Stack.h" //引入了之前写的栈结构
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//声明：
//快速排序
void QuickSort(int* a, int begin, int end);
//三数取中
void MidQuickSort(int* a, int begin, int end);
//小空间优化
void SpaceQuickSort(int* a, int begin, int end);
//挖坑法
void HoleQuickSort(int* a, int begin, int end);
//快慢指针法
void PointQuickSort(int* a, int begin, int end);
//非递归法
void QuickSortNonR(int* a, int begin, int end);
//实现
//快速排序
void QuickSort(int* a, int begin, int end)
{
//end -= 1;
if (begin >= end)
{
return;
}
int left = begin, right = end;
int key = left;
while (left < right)
{
// 右边先走，找小
while (left < right && a[right] >= a[key])
{
--right;
}
// 左边再走，找大
while (left < right && a[left] <= a[key])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[key]);
key = left;
// [begin, keyi-1] key [keyi+1, end]
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
//快排改进：key选值的三数取中（优化时间）
int GetMidIndex(int* a, int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
{
return mid;
}
else if (a[begin] > a[end])
{
return begin;
}
else
{
return end;
}
}
else // a[begin] > a[mid]
{
if (a[mid] > a[end])
{
return mid;
}
else if (a[begin] < a[end])
{
return begin;
}
else
{
return end;
}
}
}
void MidQuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
int key = left;
while (left < right)
{
// 右边先走，找小
while (left < right && a[right] >= a[key])
{
--right;
}
// 左边再走，找大
while (left < right && a[left] <= a[key])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[key]);
key = left;
// [begin, key-1] key [key+1, end]
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
//小区间优化（优化空间）
void SpaceQuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
if ((end - begin + 1) < 10)
{
// 小区间用直接插入替代，减少递归调用次数
InsertSort(a + begin, end - begin + 1);
}
else
{
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
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[left], &a[keyi]);
keyi = left;
// [begin, keyi-1] keyi [keyi+1, end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
}
// 快速排序，挖坑法
void HoleQuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
//小区间优化
if ((end - begin + 1) < 10)
{
// 小区间用直接插入替代，减少递归调用次数
InsertSort(a + begin, end - begin + 1);
}
else
{
//三数选中间优化
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
int key = a[left];
int hole = left;
while (left < right)
{
// 右边找小，填到左边坑里面
while (left < right && a[right] >= key)
{
--right;
}
a[hole] = a[right];
hole = right;
// 左边找大，填到右边坑里面
while (left < right && a[left] <= key)
{
++left;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
// [begin, key-1] key [key+1, end]
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
}
//快慢指针法
void PointQuickSort(int* a, int begin, int end)
{
if (begin > end)
{
return;
}
//小区间优化
if ((end - begin + 1) < 10)
{
// 小区间用直接插入替代，减少递归调用次数
InsertSort(a + begin, end - begin + 1);
}
else
{
//三数选中间优化
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int prev = begin, cur = begin + 1;
int key = prev;
while (cur <= end)
{
if (a[cur] < a[key] && ++prev != cur)//++prev和cur的下标如果相等，就不要进行交换
{
Swap(&a[prev], &a[cur]); //一定是先++prev，在用prev
}
cur++;
}
Swap(&a[prev], &a[key]);
PointQuickSort(a, begin, key);
PointQuickSort(a, key + 1, end);
}
}
//快速排序（非递归）
//利用堆实现的叫做深度优先
void QuickSortNonR(int* a, int begin, int end)
{
ST st;
StackInit(&st);
StackPush(&st, begin);
StackPush(&st, end);
while (!StackEmpty(&st))
{
int right = StackTop(&st);
StackPop(&st);
int left = StackTop(&st);
StackPop(&st);
//进行一次快排
int prev = left, cur = left + 1;
int key = left;
while (cur <= right)
{
if (a[cur] < a[key] && ++prev != cur)//++prev和cur的下标如果相等，就不要进行交换
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[key]);
key = prev;
// [left, key-1] keyi [key+1, right]
if (key + 1 < right)
{
StackPush(&st, key + 1);
StackPush(&st, right);
}
if (left < key - 1)
{
StackPush(&st, left);
StackPush(&st, key - 1);
}
}
StackDestroy(&st);
}
//主函数测试
void printArray(int* a, int n)
{
for (int i = 0;i < n;i++)
{
printf("%d ", a[i]);
}
printf("
");
}
void TestInsertSort()
{
int a[] = { 6,1,2,7,9,3,4,5,10,8 };
//InsertSort(a, sizeof(a) / sizeof(int));
//printArray(a, sizeof(a) / sizeof(int));
//shellSort(a, sizeof(a) / sizeof(int));
//printArray(a, sizeof(a) / sizeof(int));
//HeapSort(a, sizeof(a) / sizeof(int));
//printArray(a, sizeof(a) / sizeof(int));
//BubbleSort(a, sizeof(a) / sizeof(int));
//printArray(a, sizeof(a) / sizeof(int));
//快排传的是：数组地址、开始下标、数组结尾下标
HoleQuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
printArray(a, sizeof(a) / sizeof(int));
QuickSortNonR(a, 0, sizeof(a) / sizeof(int)-1);
printArray(a, sizeof(a) / sizeof(int));
}
void functionText()
{
srand(time(0));
const int N = 1000000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand() + i;
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a7[i];
}
//int begin1 = clock();
//InsertSort(a1, N);
//int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
//int begin3 = clock();
//SelectSort(a3, N);
//int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
/*int begin7 = clock();
BubbleSort(a7, N);
int end7 = clock();*/
int begin5 = clock();
MidQuickSort(a5, 0, N - 1);
int end5 = clock();
//
//int begin6 = clock();
//MergeSort(a6, N);
//int end6 = clock();
printf("数据量为%d，以下时间单位为毫秒（ms）
",N);
//printf("InsertSort: %d
", end1 - begin1);
printf("ShellSort: %d
", end2 - begin2);
//printf("SelectSort: %d
", end3 - begin3);
printf("HeapSort: %d
", end4 - begin4);
//printf("BubbleSort: %d
", end7 - begin7);
printf("QuickSort: %d
",end5 - begin5);
//printf("MergeSort:%d
", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
int main()
{
//TestInsertSort();
//性能测试：
functionText();
return 0;
}
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 分享几个国内免费的ChatGPT镜像网址(亲测有效)
分享几个国内免费的ChatGPT镜像网址(亲测有效)