【排序算法】快速排序升级版--三路快排详解 + 实现（c语言）
🌟🌟作者主页：ephemerals__
🌟🌟所属专栏：算法
目录
前言
一、三路快排的整体思路
二、三路快排的具体实现
1.测试数据、交换函数和三数取中法
2.三路快排函数
三、程序全部代码
总结
前言
之前我们学习了快速排序算法及其实现：
【排序算法】八大排序（下）（c语言实现）（附源码）-CSDN博客
不过它的缺陷也很明显：当数组中存在大量相同元素时，那些与基准值相同的元素的划分方法是未定义的，这将导致运行效率的下降。基于此问题，今天给大家介绍快速排序的升级版--三路快排，它能够很大程度地解决大量数据相同的情况。
一、三路快排的整体思路
所谓三路快排，就是从快速排序的划分上，由原来的两部分变为三部分：左边是比基准值小的数据；中间是与基准值相同的数据；右边是比基准值大的数据。这样划分出来，之后递归细分时，每一次生成的中间部分就不需要再进行划分了，提高了整体的运行效率。
之前我们的快速排序当中，都是默认将数组首元素作为基准值，如果该值是数组的最大值或者最小值，那么划分操作相当于只是将该值进行了排序，时间复杂度就会退化为O(N^2)。所以接下来我们在选取基准值时，将会使用三数取中法，将首元素、末元素与中间元素进行比较，选取一个中间值作为基准值。
划分的具体步骤如下：
1. 创建两“指针” left 和 right ，分别指向待排区间的两端；找到基准值之后与left位置交换，让其位于首元素位置。
2. 创建“指针” cur，指向left的后一个位置。
3. 当cur遇到比基准值小的元素时，其与left位置交换，然后cur和left各向后走一步；
当cur遇到比基准值大的元素时，其与right位置交换，然后right向前走一步；
当cur遇到与基准值相同元素时，cur向后走一步，访问后面的元素。
4. 当cur超过right位置时，划分结束，退出循环。
我们画图模拟一下它的划分过程：
注意划分完成后left和right所处的位置，便于确定下次递归的区间。
二、三路快排的具体实现
接下来，我们开始实现三路快排。首先写好测试数据、交换两元素的函数与三数取中法：
1.测试数据、交换函数和三数取中法
#include <stdio.h>
int main()
{
int arr[] = { 9,4,1,5,5,6,2,2,2,8,4,4,0,3,3,8,7 };//测试数据
int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组大小
//这里排序数据
for (int i = 0; i < sz; i++)//打印数组
{
printf("%d ", arr[i]);
}
return 0;
}//交换两元素
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}//三数取中法，返回中间值的下标
int MidOfThree(int* arr, int a, int b, int c)
{
if (arr[a] > arr[b])
{
if (arr[b] > arr[c])
{
return b;
}
else if (arr[a] > arr[c])
{
return c;
}
else
{
return a;
}
}
else
{
if (arr[a] > arr[c])
{
return a;
}
else if (arr[b] > arr[c])
{
return c;
}
else
{
return b;
}
}
}2.三路快排函数
接下来，我们尝试实现三路快排的划分以及递归：
//三路快排
void QuickSort(int* arr, int left, int right)
{
if (left >= right)//划分的区间达到最小，停止递归
{
return;
}
//记录左右边界与中间元素的下标
int begin = left;
int end = right;
int mid = (begin + end) / 2;
//确定基准值，并将其与首元素交换
Swap(&arr[MidOfThree(arr, begin, mid, end)], &arr[left]);
int key = arr[left];//记录基准值
int cur = left + 1;
//遍历数组，开始划分
while (cur <= right)
{
if (arr[cur] < key)//比基准值小的情况
{
Swap(&arr[cur++], &arr[left++]);
}
else if (arr[cur] > key)//比基准值大的情况
{
Swap(&arr[cur], &arr[right--]);
}
else//与基准值相等的情况
{
cur++;
}
}
//划分完成后，递归遍历左区间和右区间，中间部分不需要再参与排序
//注意此时left和right的位置
QuickSort(arr, begin, left - 1);
QuickSort(arr, right + 1, end);
}测试结果：
可以看到，数组排序成功了。
三、程序全部代码
三路快排的相关程序全部代码如下：
#include <stdio.h>
//交换两元素
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//三数取中法，返回中间值的下标
int MidOfThree(int* arr, int a, int b, int c)
{
if (arr[a] > arr[b])
{
if (arr[b] > arr[c])
{
return b;
}
else if (arr[a] > arr[c])
{
return c;
}
else
{
return a;
}
}
else
{
if (arr[a] > arr[c])
{
return a;
}
else if (arr[b] > arr[c])
{
return c;
}
else
{
return b;
}
}
}
//三路快排
void QuickSort(int* arr, int left, int right)
{
if (left >= right)//划分的区间达到最小，停止递归
{
return;
}
//记录左右边界与中间元素的下标
int begin = left;
int end = right;
int mid = (begin + end) / 2;
//确定基准值，并将其与首元素交换
Swap(&arr[MidOfThree(arr, begin, mid, end)], &arr[left]);
int key = arr[left];//记录基准值
int cur = left + 1;
//遍历数组，开始划分
while (cur <= right)
{
if (arr[cur] < key)//比基准值小的情况
{
Swap(&arr[cur++], &arr[left++]);
}
else if (arr[cur] > key)//比基准值大的情况
{
Swap(&arr[cur], &arr[right--]);
}
else//与基准值相等的情况
{
cur++;
}
}
//划分完成后，递归遍历左区间和右区间，中间部分不需要再参与排序
//注意此时left和right的位置
QuickSort(arr, begin, left - 1);
QuickSort(arr, right + 1, end);
}
int main()
{
int arr[] = { 9,4,1,5,5,6,2,2,2,8,4,4,0,3,3,8,7 };//测试数据
int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组大小
//这里排序数据
QuickSort(arr, 0, sz - 1);
for (int i = 0; i < sz; i++)//打印数组
{
printf("%d ", arr[i]);
}
return 0;
}总结
快速排序是一种高效且常用的排序算法，但是传统的快排并没有对与基准值相同的数据进行明确划分，造成运行效率的降低。因此出现了三路快排，它按照基准值将数组分成了三份：左边是比基准值小的数据；中间是与基准值相同的数据；右边是比基准值大的数据。这样，与基准值相同的数据就不需要再次划分，提高了整体的运行效率。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤