[数据结构]排序之 快速排序详解(递归版非递归版)
目录
一、递归版本
1. hoare版本
(一)低配版
(二)高配版
①随机选key
②三数取中法选key(在begin,end,mid三个数中选)
2. 挖坑法
3. 前后指针版本(推荐,细节容易把控)
二、非递归版本
快速排序是Hoare 于 1962 年提出的一种二叉树结构的交换排序方法,其基本思想为: 任取待排序元素序列中 的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右 子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止 。
区间按照基准值划分为左右两半部分的常见方式有:
一、递归版本
1. hoare版本
(一)低配版
什么是key?
key就是选出汗一个关键值key,把它放到正确的位置(最终排好序要去的位置)

第一轮排完之后,比6小的放左边,比6大的放右边
第一轮排序过程:
右边的R在找比key小的数
,
左边的L在找比key大的数
,找到了以后,交换这两个数(把小的往左边换,大的往右边换)
交换完之后R继续往左边走找比key小的数,L继续往右边走找比key大的数,找到之后交换这两个数,R再继续……直到L==R,相遇之后把key对应的数与L或R对应的数交换
注意一点:左边做key要让右边先走,反之亦然。
第一轮结束以后整个区间被分为三段,key的左边、key、key的右边

结束后key左边的值都比key小,右边的都比key大
代码如下:
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void QuickSort(int* a, int left,int right)
{
//递归结束条件
//当递归到begin==0,end==1,keyi==1时,区间通过[begin,kei-1] key [key+1,end]划分后
//分为[0,0] keyi [2,1],此时会出现left>right的情况
if (left >= right)
return;
int begin = left;
int end = right;
int keyi = left;
while (left < right)
{
//右边先走 找小
while (left<right&&a[right] >= a[keyi])//left<right,防止right在左边没有找到一个比key小的,这样的话right会飘出数组导致越界
{
--right;
}
//左边找大
while (left < right&&a[left] <= a[keyi])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
keyi = left;
//[begin,kei-1] key [key+1,end]
//递归
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi+1, end);
}
int main()
{
int a[] = { 6,1,2,7,9,3,4,5,10,8 };
QuickSort(a, 0, 9);
for (int i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
}
快速排序的特性总结:
1.
快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫
快速
排序
2.
时间复杂度:
O(N*logN)
3.
空间复杂度:
O(logN)
4.
稳定性:不稳定

影响快排性能的是key的位置,key的位置越接近中间就越能进行二分就越接近满二叉树
所以越有序反而快排效率越低
如何改进?
(二)高配版
①随机选key
int randi =
left + (rand() % (
right -
left));
Swap(&
a[
left], &
a[randi]);
int keyi =
left;
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
void Swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void QuickSort(int* a, int left,int right)
{
//递归结束条件
//当递归到begin==0,end==1,keyi==1时,区间通过[begin,kei-1] key [key+1,end]划分后
//分为[0,0] keyi [2,1],此时会出现left>right的情况
if (left >= right)
return;
int begin = left;
int end = right;
int randi = left + (rand() % (right - left));
Swap(&a[left], &a[randi]);
int keyi = left;
while (left < right)
{
//右边先走 找小
while (left<right&&a[right] >= a[keyi])//left<right,防止right在左边没有找到一个比key小的,这样的话right会飘出数组导致越界
{
--right;
}
//左边找大
while (left < right&&a[left] <= a[keyi])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
keyi = left;
//[begin,kei-1] key [key+1,end]
//递归
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi+1, end);
}
int main()
{
int a[] = { 6,1,2,7,9,3,4,5,10,8 };
QuickSort(a, 0, 9);
for (int i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
}
②三数取中法选key(在begin,end,mid三个数中选)
在有序或者接近有序的情况下选中间值效果最好
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
int GetMidNumi(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])//此时mid最大
{
return left;
}
else
{
return right;
}
}
else//a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] > a[right])//此时mid最小,此时另外两个小的那个就是中间值
{
return a[right];
}
else
{
return a[left];
}
}
}
void QuickSort(int* a, int left,int right)
{
//递归结束条件
//当递归到begin==0,end==1,keyi==1时,区间通过[begin,kei-1] key [key+1,end]划分后
//分为[0,0] keyi [2,1],此时会出现left>right的情况
if (left >= right)
return;
int begin = left;
int end = right;
//三数选中
int mini = GetMidNumi(a, left, right);
Swap(&a[left], &a[mini]);
int keyi = left;
while (left < right)
{
//右边先走 找小
while (left<right&&a[right] >= a[keyi])//left<right,防止right在左边没有找到一个比key小的,这样的话right会飘出数组导致越界
{
--right;
}
//左边找大
while (left < right&&a[left] <= a[keyi])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
keyi = left;
//[begin,kei-1] key [key+1,end]
//递归
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi+1, end);
}
int main()
{
int a[] = { 6,1,2,7,9,3,4,5,10,8 };
QuickSort(a, 0, 9);
for (int i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
}
为什么相遇的位置一定key小?
左边做key右边先走就能保证相遇位置一定比key小
相遇:
1、R找小,L找大没有找到,L遇到R,此时相遇位置比key小
2、R找小没有找到,直接跟L相遇,此时相遇位置比key小
类似道理,右边做key左边先走,相遇位置比key要大
2. 挖坑法
思路:
1、先将第一个数据存储在key中让第一个数据对应位置为空形成一个坑位
2、右边先走找比key小的位置后把那个比key小的数放到坑位里面去,此时右边形成了新的坑位
3、左边再走找比key大的数,找到后把这个数放到新的坑位里面去,此时又形成了新的坑位
4、以此类推,直到L和R相遇,一定相遇在坑里面,因为他们两一定有一个是坑,此时将key填到坑里面去排完后跟
hoare排完第一轮一般是不一样的
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void QuickSort(int* a, int left, int right)
{
//递归结束条件
//当递归到begin==0,end==1,keyi==1时,区间通过[begin,kei-1] key [key+1,end]划分后
//分为[0,0] keyi [2,1],此时会出现left>right的情况
if (left >= right)
return;
int begin = left;
int end = right;
//首先保存好值
int key = a[left];
//定义一个坑的位置
int hole = left;
while (left < right)
{
//右边先走 找小
while (left < right && a[right] >= key)//left<right,防止right在左边没有找到一个比key小的,这样的话right会飘出数组导致越界
{
--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]
//递归
QuickSort(a, begin, hole - 1);
QuickSort(a, hole + 1, end);
}
int main()
{
int a[] = { 6,1,2,7,9,3,4,5,10,8 };
QuickSort(a, 0, 9);
for (int i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
}
3. 前后指针版本(推荐,细节容易把控)
1、cur找到比key小的值,++prev,cur和prev位置交换,++cur
2、cur找到比key大的值,++cur ( cur一直在找小 )
说明:
1、prev要么紧跟着cur(prev下一个就是cur)
2、prev跟cur中间间隔着比key大的一段区间
把比key大的值往右翻,比key小的值往左翻
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
int GetMidNumi(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])//此时mid最大
{
return left;
}
else
{
return right;
}
}
else//a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] > a[right])//此时mid最小,此时另外两个小的那个就是中间值
{
return a[right];
}
else
{
return a[left];
}
}
}
void QuickSort(int* a, int left, int right)
{
//递归结束条件
//当递归到begin==0,end==1,keyi==1时,区间通过[begin,kei-1] key [key+1,end]划分后
//分为[0,0] keyi [2,1],此时会出现left>right的情况
if (left >= right)
return;
int begin = left;
int end = right;
//三数选中
int mini = GetMidNumi(a, left, right);
Swap(&a[left], &a[mini]);
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur<=right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
++cur;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
//[begin,kei-1] key [key+1,end]
//递归
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
int main()
{
int a[] = { 6,1,2,7,9,3,4,5,10,8 };
QuickSort(a, 0, 9);
for (int i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
}
二、非递归版本
递归改非递归:
1.直接改循环:斐波拉契
2.利用栈辅助改循环
之前递归的本质是区间的变化,那么栈也要存区间

#define _CRT_SECURE_NO_WARNINGS 1
#include "stack.h"
void Swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
int GetMidNumi(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 right;
}
else
{
return left;
}
}
}
void QuickSort(int* a, int left, int right)
{
ST st;
STInit(&st);
STPush(&st, right);
STPush(&st, left);
while (!STEmpty(&st))
{
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
// 三数选中
int mini = GetMidNumi(a, begin, end);
// 修正:将 left 改为 begin
Swap(&a[begin], &a[mini]);
int keyi = begin;
int prev = begin;
int cur = begin + 1;
// 修正:将 right 改为 end
while (cur <= end)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
++cur;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
if (keyi + 1 < end)
{
// 先入后出,先入右区间
STPush(&st, end);
STPush(&st, keyi + 1);
}
if (begin < keyi - 1)
{
// 先入后出,先入右区间
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
STDestroy(&st);
}
int main()
{
int a[] = { 6,1,2,7,9,3,4,5,10,8 };
QuickSort(a, 0, 9);
for (int i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
return 0;
}