【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)

ephemerals__ 2024-09-16 12:35:02 阅读 67

🌟🌟作者主页: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.测试数据、交换函数和三数取中法

<code>#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);

}

测试结果:

可以看到,数组排序成功了。

三、程序全部代码

三路快排的相关程序全部代码如下:

<code>#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;

}

总结

        快速排序是一种高效且常用的排序算法,但是传统的快排并没有对与基准值相同的数据进行明确划分,造成运行效率的降低。因此出现了三路快排,它按照基准值将数组分成了三份:左边是比基准值小的数据;中间是与基准值相同的数据;右边是比基准值大的数据。这样,与基准值相同的数据就不需要再次划分,提高了整体的运行效率。如果你觉得博主讲的还不错,就请留下一个小小的赞在走哦,感谢大家的支持❤❤❤



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。