c语言-快速排序
安权_code 2024-09-13 15:35:01 阅读 67
目录
一、实现快速排序三种方法
1、hoare法
2、挖坑法
3、双指针法
4、快速排序的优化
5、测试对比
结语：
前言：
快速排序作为多种排序方法中效率最高的一种，其底层原理被广泛运用，他的核心思想与二叉树结构中的递归逻辑相似，首先标记一个元素作为基准点，然后利用该基准点把数组分成左右两个区间，并且使小于该基准点的元素放在左区间，大于该基准点的元素放在右区间，如此反复递归，直到数组为一个有序数组。
实现快速排序的原理有三种方法：hoare方法，挖坑方法，双指针方法。
一、实现快速排序三种方法
1、hoare法
比如将一个数组的起始位置记成left，最后一个元素位置记成right，那么标记left的位置的元素，把该元素看成基准点（key）。
.这时候right要不断的向左移动，若right所在位置的元素是小于key位置的元素，那么right停止移动。left要不断的向右移动，若left所在位置的元素是大于key位置的元素，那么left停止移动。总结就是：left找大，right找小。（注意：若将left设置为key，则先移动right然后才能移动left）
当left和right都停下来后，把他们的元素进行交换，交换过后继续移动。
如此反复操作，最后left会走到right的位置，这时候left和right是处于同一位置的，把该位置的元素和key位置的元素进行交换，更新key的位置。
可以观察到，此时数组有了一个特点：以key为中心点，左边区间的元素都是小于基准点key元素的，右边区间的元素都是大于key元素的。
但是此时数组并不是一个有序的数组，所以要通过多重递归，因此将左边区间又看成一个小数组，右边区间也看成一个小数组。此时左边区间的left就是下标为0的位置，左边区间的right是key-1的位置。右边区间的left是key+1的位置，right是整个大数组的末尾处，既大数组的right。通过递归不断让每个小数组变得有序，最后整个数组也就有序了。
递归逻辑图如下：
hoare版本快速排序代码实现：
<code>
#include<stdio.h>
void swap(int* p1, int* p2)//交换函数
{
int temp = *p1;
*p1 = *p2;
*p2 = temp;
}
int PatrSort1(int* a, int left, int right)//hoare法
{
int key = left;//定义基准点key
while (left < right)//当left<right说明还没相遇，继续数组内元素的交换
{
while (left < right && a[right] >= a[key])//right找小
{
right--;
}
while (left < right && a[left] <= a[key])//left找大
{
left++;
}
swap(&a[right], &a[left]);//交换left和right位置的元素
}
swap(&a[key], &a[left]);//跳出循环说明他们相遇了，将他们位置的元素与key位置的元素交换
key = left;//更新key的位置
return left;//返回key元素当前的下标
}
void Qsort(int* a, int begin, int end)//快速排序（递归法），这里的begin=left，end=right
{
if (begin >= end)//
{
return;
}
int key = PatrSort1(a, begin, end);//每次递归都会找到一个属于该数组的key
Qsort(a, begin, key - 1);//递归左右区间
Qsort(a, key + 1, end);
}
void PrintArr(int* a, int n)//打印数组
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void Test_Qsort()//快排（递归）测试
{
int arr[] = { 5,10,6,1,2,4,3,9 };
int sz = sizeof(arr) / sizeof(int);
PrintArr(arr, sz);
Qsort(arr, 0, sz - 1);
printf("hoare法：");
PrintArr(arr, sz);
}
int main()
{
Test_Qsort();
return 0;
}
运行结果：
2、挖坑法
思路：和hoare法一样先定义一个基准点，只不过把这个基准点叫做“坑”，“坑”里的元素是要被抹除的（也就是“坑”里不能有元素），因此先用一个变量key来保存“坑”里的元素。right向左移动找到小于该基准点（“坑”）的元素就把这个元素填到“坑”里，这时候“坑”里有了元素，可以表示“坑”被填满了，但是right位置的就变成了新的“坑”，因为right位置的元素被用来“填坑”了。
下一次就是left找大的元素给到right位置的”坑“，然后left的位置就成了新坑，如此反复，直到left和righ相遇，待到他们相遇的位置必然是一个”坑“，这时候把key存储的元素放到这个”坑“里，此时会发现数组也以5（key）为中心点分成了两个区间，而且左区间的元素都是小于key的，右区间的元素都是大于key的。
挖坑法代码实现快速排序：
<code>#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void swap(int* p1, int* p2)//交换函数
{
int temp = *p1;
*p1 = *p2;
*p2 = temp;
}
int PatrSort2(int* a, int left, int right)//挖坑法
{
int key = a[left];//把基准点元素的值保存起来
int hole = left;//设置hole更加形象表示坑
while (left < right)//相遇前进行相互“填坑”
{
while (left < right && a[right] >= key)//right找小
{
right--;
}
a[left] = a[right];//填坑
hole = right;//right处变成新坑
while (left < right && a[left] <= key)//left找大
{
left++;
}
a[right] = a[left];//填坑
hole = left;//left处变成新坑
}
a[hole] = key;//最后left处是一个坑，把key存的元素给到此处，此处作为基准点
return hole;//返回基准点的下标
}
void Qsort(int* a, int begin, int end)//快速排序（递归法）
{
if (begin >= end)//
{
return;
}
int key = PatrSort2(a, begin, end);//每次递归都会找到一个属于该数组的key
Qsort(a, begin, key - 1);//递归左右区间
Qsort(a, key + 1, end);
}
void PrintArr(int* a, int n)//打印数组
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void Test_Qsort()//快排（递归）
{
int arr[] = { 5,10,6,1,2,4,3,9 };
int sz = sizeof(arr) / sizeof(int);
PrintArr(arr, sz);
Qsort(arr, 0, sz - 1);
printf("挖坑法：");
PrintArr(arr, sz);
}
int main()
{
Test_Qsort();
return 0;
}
运行结果：
从结果可以看到，不管是挖坑法还是hoare法都可以实现排序，因为他们本身的逻辑是一样的。
3、双指针法
顾名思义就是依靠两个类似指针的变量去变量数组并且完成排序，首先定义一个变量prev和一个变量cur，分别在数组的第一个元素位置和第二个元素位置，cur在prev的后边（既cur在第二个元素位置），并且把prev的位置设置成key基准点。当cur遇到比key小的元素则prev往后走一步，然后prev的元素与cur的元素进行交换，交换过后cur继续走。当cur遇到比key大的元素则prev不动，cur继续走。
最后当cur走到数组外面表示遍历结束，这时候prev所在位置的元素与key元素交换，并且作为新的基准点。
此时数组也被分成了两个区间，并且左边区间的元素小于key，右边区间的元素大于key。
双指针法实现快速排序代码如下：
<code>
#include<stdio.h>
void swap(int* p1, int* p2)//交换函数
{
int temp = *p1;
*p1 = *p2;
*p2 = temp;
}
int PatrSort3(int* a, int left, int right)//双指针法
{
int key = left;//定义基准点
int prev = left;//定义两个变量
int cur = left + 1;
while (cur <= right)//当cur还在数组内时
{
if (a[cur] <= a[key] && prev != cur)//若cur元素小于keyi元素
{
prev++;//prev向后走一步
swap(&a[cur], &a[prev]);//交换cur和prev位置的元素
}
cur++;//cur一直往后走
}
swap(&a[prev], &a[key]);//最后交换prev和key的元素
key = prev;//更新key的位置
return key;//返回key的下标
}
void Qsort(int* a, int begin, int end)//快速排序（递归法）
{
if (begin >= end)//
{
return;
}
int key = PatrSort3(a, begin, end);//每次递归都会找到一个属于该数组的key
Qsort(a, begin, key - 1);//递归左右区间
Qsort(a, key + 1, end);
}
void PrintArr(int* a, int n)//打印数组
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void Test_Qsort()//快排（递归）
{
int arr[] = { 5,10,6,1,2,4,3,9 };
int sz = sizeof(arr) / sizeof(int);
PrintArr(arr, sz);
Qsort(arr, 0, sz - 1);
printf("双指针法：");
PrintArr(arr, sz);
}
int main()
{
Test_Qsort();
return 0;
}
运行结果：
从结果来看，三个方法都可以实现快速排序。 三种方法的效率其实也不相上下，但是目前快速排序有一个问题：如果快速排序每次选key时都能选到中位数则快速排序的效率就很好，时间复杂度为：O（N*logN），但是快速排序在面对有序数组的排序下效率会很慢，因为第一位数不是中位数，其时间复杂度为O（N^2）。
4、快速排序的优化
针对以上的问题，如果每次选key的时候都能选到数组偏中位数的值，那么就解决了该问题，因此当我们有了一个数组的left和right，那么可以假设一个中间值：mid=（left+right）/2，通过对比他们三者之间的关系从而得到三者的中间值。
三数取中代码如下：
<code>int GetMid(int* a, int left, int right)//针对有序数组排序的三数取中
{
int mid = (left + right) / 2;//先定义一个mid中间值
//对比他们三者之间的关系，选出三者之间的中间值
if (a[left] < a[mid])
{
if (a[right] < a[left])
return left;
else if (a[mid] > a[right])
return right;
else
return mid;
}
else
{
if (a[mid] > a[right])
return mid;
else if (a[right] > a[left])
return left;
else
return right;
}
}
5、测试对比
通过测试对比优化前的快速排序的效率和优化后快速排序的效率，测试代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int GetMid(int* a, int left, int right)//针对有序数组排序的三数取中
{
int mid = (left + right) / 2;//先定义一个mid中间值
//对比他们三者之间的关系，选出三者之间的中间值
if (a[left] < a[mid])
{
if (a[right] < a[left])
return left;
else if (a[mid] > a[right])
return right;
else
return mid;
}
else
{
if (a[mid] > a[right])
return mid;
else if (a[right] > a[left])
return left;
else
return right;
}
}
void swap(int* p1, int* p2)//交换函数
{
int temp = *p1;
*p1 = *p2;
*p2 = temp;
}
int PatrSort3(int* a, int left, int right)//双指针法
{
int key = left;//定义基准点
int temp = GetMid(a, left, right);
swap(&a[temp], &a[key]);//使keyi处的元素是三数取中的结果
int prev = left;//定义两个变量
int cur = left + 1;
while (cur <= right)//当cur还在数组内时
{
if (a[cur] <= a[key] && prev != cur)//若cur元素小于keyi元素
{
prev++;//prev向后走一步
swap(&a[cur], &a[prev]);//交换cur和prev位置的元素
}
cur++;//cur一直往后走
}
swap(&a[prev], &a[key]);//最后交换prev和key的元素
key = prev;//更新key的位置
return key;//返回key的下标
}
void Qsort(int* a, int begin, int end)//快速排序（递归法）
{
if (begin >= end)//
{
return;
}
int key = PatrSort3(a, begin, end);//每次递归都会找到一个属于该数组的key
Qsort(a, begin, key - 1);//递归左右区间
Qsort(a, key + 1, end);
}
void Contrast_test()//对比测试
{
//手动构建数组
int n = 100000;
srand(time(0));
int* n1 = (int*)malloc(sizeof(int) * n);
int* n2 = (int*)malloc(sizeof(int) * n);
int* n3 = (int*)malloc(sizeof(int) * n);
int* n4 = (int*)malloc(sizeof(int) * n);
int* n5 = (int*)malloc(sizeof(int) * n);
int* n6 = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
{
n1[i] = rand() % 10000;
n2[i] = n1[i];
n3[i] = n1[i];
n4[i] = n1[i];
n5[i] = n1[i];
n6[i] = n1[i];
}
//先让数组排成有序
//clock函数返回的是系统启动到调用该函数的时间，单位是毫秒，并存到变量中
int start1 = clock();
Qsort(n1, 0, n - 1);
int end1 = clock();
//在进行对有序数组的排序
int start2 = clock();
Qsort(n1, 0, n - 1);
int end2 = clock();
printf("key为中间值，对有序数组的排序:\n");
printf("Test_PatrSort3:%d\n", end1 - start1);
printf("Test_PatrSort3:%d\n", end2 - start2);
free(n1);
free(n2);
free(n3);
free(n4);
free(n5);
free(n6);
}
int main()
{
Contrast_test();
return 0;
}
运行结果（优化前）：
运行结果（优化后）：
通过结果可以发现，优化之后的快速排序在面对有序的数组效率依然很高。
结语：
以上就是关于快速排序的介绍，最后希望本文可以给你带来更多的收获，如果本文对你起到了帮助，希望可以动动小指头帮忙点赞👍+关注😎+收藏👌！如果有遗漏或者有误的地方欢迎大家在评论区补充~！！谢谢大家！！(～￣▽￣)～
上一篇： JS常用的5个时间插件
下一篇： InaccessibleObjectException: Unable to make field protected java.lang.reflect.InvocationHandler java
本文标签
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。