【数据结构】快速排序
·
目录
一、排序思想
任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右两子序列重复该过程，直到所有元素都排列在相应位置上为止。
二、代码实现
下列所有代码示例均是排成升序。
注：
快排在对存在大量相同的数据排序时，效率很低，这种情况三路划分可以解决，感兴趣的朋友可以自行了解，这里不作介绍。
（一）hoare版
1、原版——固定选key
缺点：
固定位置选key，在数据有序或几乎有序时容易栈溢出。
注：
选最左边元素为key，最右边先开始选数
选最右边元素为key，最左边先开始选数
#include<stdio.h>
void Print(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//haore
void QuickSort1(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int begin = left;
int end = right;
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 key+1 end
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi+1, end);
}
int main()
{
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
QuickSort1(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
Print(arr, 10);
return 0;
}2、随机选key、三数取中选key
思想较之于原版并没有本质变化，只是优化了选key的方式。
#include<stdio.h>
#include<stdlib.h>
//打印
void Print(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//三数取中
int Midnum(int* a,int left, int right)
{
int mid = (left + right) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
else
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
}
//快排(升序)——hoare(优化选key)
void QuickSort(int* a,int left,int right)
{
if (left >= right)
{
return;
}
int begin = left;
int end = right;
//随机选key
/*int ran = left + rand() % (right - left);
Swap(&a[left], &a[ran]);
int keyi = left;*/
//三数取中选key
int mid = Midnum(a,left, right);
Swap(&a[left], &a[mid]);
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]);
}
//将key移至中间
Swap(&a[left], &a[keyi]);
//更新keyi
keyi = left;
//递归 [begin,keyi-1] keyi [keyi+1,end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
int main()
{
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
QuickSort(arr, 0, sizeof(arr) / sizeof(arr[0])-1);
Print(arr, 10);
return 0;
}（二）挖坑法
思想：
将选定的key存起来，原本key的位置就空出来成为一个坑位，然后将找到的符合要求的元素填入坑内，该元素原本所在的位置成为新的坑位，循环往复。
其实就是一个不断填坑造坑的过程。
#include<stdio.h>
//打印
void Print(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//三数取中
int GetMidnum(int* a, int left, int right)
{
int mid = (right - left) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
else//a[left]<a[mid]
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
}
//快排(升序)——挖坑法
void QuickSort3(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int begin = left, end = right;
int mid = GetMidnum(a, left, right);
Swap(&a[left], &a[mid]);
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,hole-1] hole [hole+1,end]
QuickSort3(a, begin, hole - 1);
QuickSort3(a, hole+1, end);
}
int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
QuickSort3(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
Print(arr, sizeof(arr) / sizeof(arr[0]));
return 0;
}（三）前后指针法
思想：
1、cur找到比key小的值，++prev，cur和prev位置的值交换，++cur
2、cur找到比key大的值，++cur循环往复
其实就是将比key大的值向右扔，将比key小的值向左扔。
注：
1、prev要么紧跟着cur
2、prev要么跟cur中间间隔着比key大的一段值区间
#include<stdio.h>
//打印
void Print(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//三数取中
int GetMidnum(int* a, int left, int right)
{
int mid = (right - left) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
else//a[left]<a[mid]
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
}
//快排——前后指针法
void QuickSort4(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int mid = GetMidnum(a, left, right);
Swap(&a[left], &a[mid]);
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && cur != ++prev)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
//a[prev]永远都比a[keyi]小
Swap(&a[prev], &a[keyi]);
//更新keyi
keyi = prev;
//[left,keyi-1] keyi [keyi+1,right]
QuickSort4(a, left, keyi - 1);
QuickSort4(a, keyi+1, right);
}
int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0,11,13,14};
QuickSort4(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
Print(arr, sizeof(arr) / sizeof(arr[0]));
return 0;
}（四）小区间优化
①主要针对递归层数太多的情况。
②小区间优化需要用到直接插入排序，不了解的朋友可以先移步直接插入排序
#include<stdio.h>
#include"InsertSort.h"
//打印
void Print(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//三数取中
int GetMidnum(int* a, int left, int right)
{
int mid = (right - left) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
else//a[left]<a[mid]
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
}
//快排——前后指针法
int _QuickSort5(int* a, int left, int right)
{
int mid = GetMidnum(a, left, right);
Swap(&a[left], &a[mid]);
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && cur != ++prev)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
//a[prev]永远都比a[keyi]小
Swap(&a[prev], &a[keyi]);
//更新keyi
keyi = prev;
return keyi;
}
void QuickSort5(int* a, int left, int right)
{
if (left >= right)
{
return;
}
if (right - left + 1 > 10)
{
int keyi = _QuickSort5(a, left, right);
//[left,keyi-1] keyi [keyi+1,right]
QuickSort5(a, left, keyi - 1);
QuickSort5(a, keyi + 1, right);
}
//小区间优化
else
{
IsertSort(a+left, right - left + 1);
}
}
int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0,11,2,4,45,33 };
QuickSort5(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
Print(arr, sizeof(arr) / sizeof(arr[0]));
return 0;
}（五）非递归写法
此处是用栈来辅助改成循环，需要用到栈。
思想：
①将初始区间入栈
②从栈中取一段区间进行单趟快排并分割
③将分割出的子区间入栈（区间内元素数量>=2）
#include<stdio.h>
#include"Stack.h"
//打印
void Print(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//三数取中
int GetMidnum(int* a, int left, int right)
{
int mid = (right - left) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
else//a[left]<a[mid]
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
}
//快排——前后指针法
int _QuickSort6(int* a, int left, int right)
{
int mid = GetMidnum(a, left, right);
Swap(&a[left], &a[mid]);
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && cur != ++prev)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
//a[prev]永远都比a[keyi]小
Swap(&a[prev], &a[keyi]);
//更新keyi
keyi = prev;
return keyi;
}
//快排——非递归形式
void QuickSort6(int* a, int left, int right)
{
ST st;
StackInit(&st);
//将初始区间入栈
StackPush(&st, right);
StackPush(&st, left);
while (!Empty(&st))
{
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
//分割母区间
int keyi = _QuickSort6(a, begin, end);
//[begin,keyi-1] keyi [keyi+1,end]
//将子区间入栈(元素>=2)
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi+1);
}
if (begin < keyi - 1)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
StackDestroy(&st);
}
int main()
{
int arr[] = { 9,7,8,5,4,6,3,1,2,0 };
QuickSort6(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
Print(arr, sizeof(arr) / sizeof(arr[0]));
return 0;
}感谢阅读，本文如有疏漏不当之处，烦请各位指正。
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
29
0- 0
已为社区贡献1条内容
所有评论(0)