【数据结构】八大排序之快速排序算法
一.快速排序简介及思想
快速排序(Quick Sort)是一种效率较高的交换排序算法.
它的基本思想是:
- 通过一趟排序将待排数据分割成独立的两部分
- 其中一部分数据的关键字均比另一部分数据的关键字小
- 可分别对这两部分数据继续进行排序,以达到整个序列有序的目的.
算法动图演示:
二.快速排序代码实现的三种方式
我们了解了快速排序的基本思想是通过一趟排序将待排数据分割成独立的两部分之后,在代码的实现上,其实就有很多可以自由发挥的空间,如下较为主流的快速排序有三种实现思路,接下来我将一一带大家理解这三个思路并使用它们实现快排算法: 注:本文的快排实现思路均以升序为例!
?左右交换法
左右交换法的思路是:
- 先选定当前待排序列的首元素位置的值为基准值(key).
- 然后设置一个右指针,使其从后向前遍历,找到比基准值(key)小的元素就停下来.
- 再设置一个左指针,使其从前向后遍历,找到比基准值(key)大的元素就停下来.
- 当左右指针都找到相应元素时,交换它们找到的元素.
- 重复步骤2~4,直到左右指针相遇
- 左右指针相遇后,将基准值(key)与相遇位置做交换,此时数组已经被重新一分为二成两个新的待排子序列.
- 分别继续对新的待排子序列继续执行步骤1~6排序,直到所有元素都排列在相应位置上为止.
左右交换法算法演示:
清楚了左右交换法实现快排的思路后,我们编写实现代码就比较容易了,代码如下:
//交换函数
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//快速排序(左右交换法
void QuickSort_swap(int* a, int left, int right)
{
if (left >= right)
return;
int begin = left, 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]);
}
//相遇时交换key和相遇位置的值
Swap(&a[keyi], &a[left]);
keyi = left;//用keyi记录下本轮确定的基准值位置
QuickSort_swap(a, begin, keyi - 1);//递归排序左区间[begin , keyi-1]
QuickSort_swap(a, keyi + 1, end);//递归排序右区间[keyi+1 , end]
}?挖坑填坑法
挖坑填坑法是基于快排的基础思想提出的一种创新实现的思路,它的思路是这样的:
- 先记录下当前待排序列的首元素为基准值(key).
- 此时认为首元素的位置是空缺的,即该位置成为了一个坑.
- 设置一个右指针,使其从后向前遍历,找到比基准值(key)小的元素停下来将其填入刚才的坑位中,此时认为右指针找到的这个元素位置又形成了一个坑.
- 设置一个左指针,使其从前向后遍历,找到比基准值(key)大的元素停下来将其填入刚才的坑位中,此时认为左指针找到的这个元素位置又形成了一个坑.
- 左右指针不断向中间挪动不断填坑又形成新坑,直到两指针相遇
- 最后将基准值(key)填入左右指针相遇位置的坑中,此时数组已经被重新一分为二成两个新的待排子序列.
- 分别继续对新的待排子序列继续执行步骤1~6排序,直到所有元素都排列在相应位置上为止.
挖坑填坑法算法演示:
挖坑填坑法实现快排代码如下:
//快速排序(挖坑填坑法
void QuickSort_hole(int* a, int left, int right)
{
if (left >= right)
return;
int begin = left, end = right;
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;
}
//相遇时把key的值填进相遇的坑里
a[hole] = key;
QuickSort_hole(a, begin, hole - 1);//递归遍历左区间[begin , hole-1]
QuickSort_hole(a, hole + 1, end);//递归遍历右区间[hole+1 , end]
}?前后指针法
前后指针法思路为:
- 先选定当前待排序列的首元素位置的值为基准值(key).
- 设立前指针prev,使其指向序列开头,即基准值位置
- 设立后指针cur,使其指向prev指针的后一个位置
- 判断cur指向的数据是否小于key:如果小于,则prev后移一位,然后将cur指向的内容与prev指向的内容交换, 然后cur指针++;如果不小于,则cur++.
- 循环步骤4,直到cur移动到超出序列范围时,交换prev位置和基准位置的值,此时数组已经被重新一分为二成两个新的待排子序列.
- 分别继续对新的待排子序列继续执行步骤1~5排序,直到所有元素都排列在相应位置上为止.
前后指针法算法演示:
前后指针法实现快排代码如下:
//交换
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//快速排序(前后指针法
void QuickSort_follow(int* a, int left, int right)
{
if (left >= right)
return;
int begin = left, end = right;
int keyi = left;//选定序列首元素为基准值,记录下基准值位置
int prev = left;
int cur = prev + 1;
while (cur <= right) //cur没有越界就继续
{
if (a[cur] < a[keyi] && ++prev != cur) //如果cur指向的值小于key,并且++prev与cur不重叠
{
Swap(&a[cur], &a[prev]); //就交换它们
}
cur++;
}
Swap(&a[prev], &a[keyi]);//交换prev和key的值
keyi = prev;
QuickSort_follow(a, begin, keyi - 1);//递归遍历左区间[begin , keyi-1]
QuickSort_follow(a, keyi + 1, end);//递归遍历右区间[keyi+1 , end]
}三.快速排序的时间复杂度分析
"快速排序的平均时间为
T_{avg}(n)=knlog_2n
,其中n为待排序序列中数据的个数,k为某个常数,经验证明,在所有同数量级的此类(先进的)排序算法中,快速排序的常数因子k最小.因此,就平均时间而言,快速排序是目前被认为最好的一种内部排序方法. 通常,快速排序被认为是,在所有同数量级(O(nlogn))的排序算法中,其平均性能最好.但是,若初始数据序列按关键字有序或基本有序时,快速排序将蜕化为冒泡排序,其时间复杂度为O(n^2)." ——《数据结构》严蔚敏
也就是说,快排的时间复杂度我们可以认为是O(nlogn),但当遇到原数组本身有序的情况下,其时间复杂度就会退化至O(n^2),这个其实很好理解,举个例子就明白了:
当最优情况下,即每趟选择key时都恰好选择到数组的中间值时(第n层可以确定
2^{n-1}
个数字位置),快排的时间复杂度如下图完全(满)二叉树:
该树每层需要遍历一遍数组,时间复杂度为n,而树高为
h=log_2n
,因此最优状态下快排的时间复杂度仅为O(nlogn).
而最坏情况下,即每趟选择key时都恰好选择到数组最大或最小的值时(即每一层都只能确定一个数字位置),快排的时间复杂度如下单支树:
该树每层遍历一遍数组,时间复杂度为n,而树高也为n,因此最坏状态下快排的时间复杂度为O(n^2).
综上,对快排时间复杂度的分析,我们不光理解了为什么快排排先天有序的数组时反而效率最差,同样也为我们后续对快排算法的优化提供了思路.
四.快速排序的优化
?优化选key方式
既然在快排在面对原本就接近有序的数组时排序会因为key值的选取导致效率降低,那么我们不妨优化一下我们快排时选key的方式,下面为大家介绍两种常用的优化选key的方式:
?随机选key法
随机选key的思路为:
- 先使用rand()函数随机选出一个在[left,right]范围内的下标值randi
- 将randi下标的数据和keyi下标的数据互换
随机选key函数的实现:
//随机选key法
void SwapRand_key(int* a,int left, int right)
{
int randi = left + (rand() % (right - left));
Swap(&a[left], &a[randi]);
}结合随机选key法实现快排
我们写好随机选key函数后只需要在正常快排函数中选定keyi后(如下函数的第15行后)调用一下随机选keyi函数就可以将随机选出的key值和原本的key值做交换了.
实现代码如下:
//随机选key法
void SwapRand_key(int* a,int left, int right)
{
int randi = left + (rand() % (right - left));
Swap(&a[left], &a[randi]);
}
//快速排序(前后指针法
void QuickSort_follow(int* a, int left, int right)
{
if (left >= right)
return;
int begin = left, end = right;
int keyi = left; //选定序列首元素为基准值,记录下基准值
SwapRand_key(a,left, right); //随机选出一个数据交换基准值key
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
QuickSort_follow(a, begin, keyi - 1);//递归遍历左区间[begin , keyi-1]
QuickSort_follow(a, keyi + 1, end);//递归遍历右区间[keyi+1 , end]
}?三数取中法
三数取中法的思路是:
- 比较序列首元素,尾元素,中间元素,取三者中的中间值作为midi
- 将midi下标的数据和keyi下标的数据互换
三数取中函数的实现:
//三数取中法
void SwapMid_key(int* a, int left, int right)
{
int midi = (left + right) / 2;
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
midi = midi;
}
else if (a[left] > a[right])
{
midi = left;
}
else
{
midi = right;
}
}
else // a[left] > a[mid]
{
if (a[midi] > a[right])
{
midi = midi;
}
else if (a[left] < a[right])
{
midi = left;
}
else
{
midi = right;
}
}
if (midi != left)
Swap(&a[midi], &a[left]);
}结合三数取中法实现快排
我们写好三数取中函数后只需要在正常快排函数中选定keyi后(如下函数的第45行后)调用一下三数取中函数就可以将三数取中选出的key值和原本的key值做交换了.
实现代码如下:
//三数取中函数
void SwapMid_key(int* a, int left, int right)
{
int midi = (left + right) / 2;
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
midi = midi;
}
else if (a[left] > a[right])
{
midi = left;
}
else
{
midi = right;
}
}
else // a[left] > a[mid]
{
if (a[midi] > a[right])
{
midi = midi;
}
else if (a[left] < a[right])
{
midi = left;
}
else
{
midi = right;
}
}
if (midi != left)
Swap(&a[midi], &a[left]);
}
//快速排序(前后指针法
void QuickSort_follow(int* a, int left, int right)
{
if (left >= right)
return;
int begin = left, end = right;
int keyi = left; //选定序列首元素为基准值,记录下基准值
SwapMid_key(a, left, right); //三数取中法选出基准值后交换基准值
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
QuickSort_follow(a, begin, keyi - 1);//递归遍历左区间[begin , keyi-1]
QuickSort_follow(a, keyi + 1, end);//递归遍历右区间[keyi+1 , end]
}?小区间优化
?小区间优化的原理
快排的递归展开思路类似于二叉树,因此它们拥有同样的弊病,就是越靠近树的底部,空递归的情况就越多,并且空递归的规模量非常大,拿下面这颗树来举例: 我们递归遍历该树,发现空递归(紫色)访问次数竟然和总有效访问次数(绿色)是相同的.而对于快排来说,这样的空递归不仅浪费时间,而且是没有任何实际意义的.
因此我们可以考虑采用一种办法,将快排的递归范围加以限制,比如当我们不断分割快排子区间,当子区间数组元素小于10个数时,我们就不再进行快排递归排序,而使用直接插入排序来对该小区间进行排序,这样就可以有效的消灭超过一半的递归,从而提升快排的效率.
?小区间优化的代码实现
清楚了上面的原理之后,我们实现小区间优化的思路为:
- 判断小区间数组是否小于10个数.
- 如果区间不小于10,则执行快排逻辑.
- 如果区间小于等于10,则执行直接插入排序逻辑.
综上所述,小区间代码实现如下:
//交换函数
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//三数取中法取key函数
void SwapMid_key(int* a, int left, int right)
{
int midi = (left + right) / 2;
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
midi = midi;
}
else if (a[left] > a[right])
{
midi = left;
}
else
{
midi = right;
}
}
else // a[left] > a[mid]
{
if (a[midi] > a[right])
{
midi = midi;
}
else if (a[left] < a[right])
{
midi = left;
}
else
{
midi = right;
}
}
if (midi != left)
Swap(&a[midi], &a[left]);
}
//直接插入排序函数
void InsertSort(int* a, int n)
{
for (int i = 1; i < n; i++)
{
int end = i - 1;
int tmp = a[i];
//将tmp插入到[0,end]这个区间里
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
//小区间优化版快排
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
if ((right - left + 1 ) > 10)
{
int keyi = left;
SwapMid_key(a, left, right);
//双指针前后移动法快排
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[prev], &a[keyi]);
keyi = prev;
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
else
{
InsertSort( a + left , right - left + 1 );
}
}五.借助栈实现非递归快速排序
?为什么要将递归的快速排序算法改为非递归?
递归函数有以下几个缺点:
- 内存消耗大：递归调用会占用大量的内存空间，因为每次调用都需要在内存中保存当前的状态和参数。
- 性能低下：递归调用会增加函数调用的开销，因此在一些情况下会导致程序的性能下降。
- 可读性差：递归函数通常比较复杂，难以理解和调试，降低了代码的可读性。
- 可能导致栈溢出：如果递归调用层次过深，会导致栈溢出的问题，使程序崩溃。
- 难以优化：一些编译器和优化工具难以对递归函数进行有效的优化，导致性能不佳。
?递归函数改非递归的思路
- 直接改为循环.(如:斐波那契数列)
- 利用栈辅助改为循环.(如:二叉树的前序遍历)
?快速排序改非递归的思路
- 将初始数组区间压入栈
- 在栈里取一段区间,单趟排序
- 单趟分割子区间入栈
- 子区间只有一个值或着不存在就不入栈
- 重复步骤2-4,直到栈为空,则排序完成.
?快速排序改非递归的代码实现
因为快排改非递归时要借助栈结构,因此我先将栈相关定义的头文件贴在这里,具体栈的C语言完整实现可以移步我的另一篇博客,在文末有数据结构栈实现的完整代码,大家可以直接粘贴过来使用:
icon-default.png?t=N7T8
http://t.csdnimg.cn/FL0V3(注:如果本身没有自己实现数据结构栈的工程文件的,一定要将该博客末尾的Stack.h文件和Stack.c文件粘贴在排序项目文件里才可以正常使用栈的相关功能,否则C语言是不支持直接使用的!)
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack
{
STDataType*arr;
int top;
int capacity;
}ST;
void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
STDataType STTop(ST* ps);
void STMenu();综上,快排的非递归代码实现如下:
//交换函数
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//三数取中法取key函数
void SwapMid_key(int* a, int left, int right)
{
int midi = (left + right) / 2;
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
midi = midi;
}
else if (a[left] > a[right])
{
midi = left;
}
else
{
midi = right;
}
}
else // a[left] > a[mid]
{
if (a[midi] > a[right])
{
midi = midi;
}
else if (a[left] < a[right])
{
midi = left;
}
else
{
midi = right;
}
}
if (midi != left)
Swap(&a[midi], &a[left]);
}
//快速排序主函数(非递归版
void QuickSortNonR(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 keyi = begin;
SwapMid_key(a, begin, end);
//双指针前后移动法快排
int prev = begin;
int cur = begin + 1;
while (cur <= end)
{
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[cur], &a[prev]);
++cur;
}
Swap(&a[prev], &a[keyi]);
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);
}六.快速排序的三路划分
//主要解决快速排序面对大量重复数据时效率低下的问题
//该部分内容待补
本文参与?腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-01-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录