当前位置:网站首页>超级哇塞的快排,你值得学会!
超级哇塞的快排,你值得学会!
2022-07-05 14:30:00 【老鱼37】
今天我们要讲的是快速排序,非常的哇塞!
简单了解一下快排------
下面介绍快排的三个方法,未优化和优化后的快排
First----hoare版本
也就是说先确立的一个下标为key的值为对比值,普遍可以认为左边第一个值就key值,然后,从右边发出,寻找比key值小的数字,当R停下时,L才动,然后找到比key大的值,然后进行L、R的交换,最终他们一定会相遇,相遇的下标对应的值就将key赋值给他,然后再分而治之,
[left,key-1] key [key+1,right] 就是一样一个递归
数据结构一定要学会画图来思考问题,让问题更加地清晰明了!
完整代码:
//hoare版本
void QuickSort(int* arr, int begin, int end)
{
//进来判断一下
if (begin >= end)
{
return;
}
int left = begin;
int right = end;
int key = left;
while (left < right)
{
//先走右边
while (left < right && arr[right] >= arr[key])
{
--right;
}
while (left < right && arr[left] <= arr[key])
{
++left;
}
//交换
Swap(&arr[left], &arr[right]);
}
//最后相遇了
Swap(&arr[key], &arr[left]);
key = left;//更新key的位置
QuickSort(arr, begin, key - 1);
QuickSort(arr, key + 1, end);
}
void PrintSort(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[] = { 3,1,2,4,9,5,6};
int len = sizeof(arr) / sizeof(arr[0]);
QuickSort(arr,0, len-1);
PrintSort(arr, len);
}
下面介绍另外一种方法,被大神们优化一下, 比较好理解!
2、挖坑法-------顾名思义就是有一个坑
完整代码:
//挖坑法
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end)
{
return;
}
int left = begin;
int right = end;
int key = arr[left];
int piti =left;//坑位
while (left < right)//控制范围
{
while (left < right && arr[right] >= key)
{
--right;
}
arr[piti] = arr[right];
piti = right;
while (left < right && arr[left] <= key)
{
++left;
}
arr[piti] = arr[left];
piti = left;
}
//还有最后相遇的一个坑位
arr[piti] = key;
QuickSort(arr, begin, piti - 1);
QuickSort(arr, piti + 1, end);
}
void PrintSort(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[] = { 3,1,2,4,9,5,6};
int len = sizeof(arr) / sizeof(arr[0]);
QuickSort(arr,0, len-1);
PrintSort(arr, len);
}
第三种方法:前后指针版本
完整代码:
//前后指针版本
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end)
{
return;
}
int prev = begin;
int cur = begin + 1;
int key = begin;
while (cur <= end)
{
if (arr[cur] < arr[key] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
++cur;
}
//最后只剩下一个prev
Swap(&arr[prev], &arr[begin]);
key = prev;
QuickSort(arr, begin, key - 1);
QuickSort(arr, key + 1, end);
}
void PrintSort(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[] = { 3,1,2,4,9,5,6};
int len = sizeof(arr) / sizeof(arr[0]);
QuickSort(arr,0, len-1);
PrintSort(arr, len);
}
相信你学会这三种快排的方法不算难事,但是那都是没进行过优化的,接下来让我们来优化一下吧!前面三种方法的时间复杂度都是O(N),在效率上并没有提升太多
优化方法—:三数取中(在前后指针版本上面改善)
影响效率的障碍就是key,要不每次key都是最小,要 不key每次都是最大,那么效率肯定就上不去,如果我们让key是区域内的middle 那么效率更上一层了,所以三数取中。
//前后指针版本
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end)
{
return;
}
int prev = begin;
int cur = begin + 1;
int key = begin;
//三数取中
int mid = GetMidIndex(arr, begin, end);
Swap(&arr[key], &arr[mid]);
while (cur <= end)
{
if (arr[cur] < arr[key] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
++cur;
}
//最后只剩下一个prev
Swap(&arr[prev], &arr[begin]);
key = prev;
QuickSort(arr, begin, key - 1);
QuickSort(arr, key + 1, end);
}
优化方法二:递归到小的子区间时,可以考虑使用插入排序
因为在数据有序或者接近有序的时候,插入排序的效率非常可观,至于为什么不用希尔,堆,是因为在大数据下用他们比较快,但是接近有序的时间复杂度插入排序更胜一筹!
这些数据划分区域就知道最后接近有序的递归次数就占了一半,所以说非常的庞大。
区域优化代码:
这里的插入排序的arr如果不加begin的话,那么每次都是最前面的20个数进行排序,那么无意义,arr+begin就是不同区域内的begin----end
这个优化就非常的爽了!
这些快排都是运用了递归的方式,递归也是一定的劣势,所以我们也必须要掌握非递归的方式
非递归我们运用的是栈完成快排
栈的性质是先进后出,我们可以完美地运用这个性质!
思路:
这完全就像是树的工作方式,先完成左树的排序,然后再进行右树的排序,穷尽到最后一个区域,最后再销毁一下栈就可以实现非递归的快排了
更形象一点:当然用队列也是一样的,运用好队列的性质就行好,控制好
因为这是纯C所以要先手搓一个栈,到C++就不用这么麻烦了,
非递归完整代码:
//栈
typedef struct Stack
{
int* arr;
int top;
int capacity;
}Stack;
void InitStack(Stack* ps)
{
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
void StackPush(Stack* ps,int x)
{
//检测是否满了
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
int tmp = (int *)realloc(ps->arr,sizeof(int )*newcapacity);
ps->arr = tmp;
ps->capacity = newcapacity;
}
ps->arr[ps->top] = x;
ps->top++;
}
void StackPop(Stack* ps)
{
ps->top--;
}
void DestoryStack(Stack* ps)
{
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
int StackTop(Stack* ps)
{
return ps->arr[ps->top-1];
}
bool StackEmpty(Stack* ps)
{
return ps->top==0;
}
//栈来实现非递归的快排
void QuickSort(int* arr, int begin, int end)
{
Stack st;
InitStack(&st);
StackPush(&st, end);
StackPush(&st, begin);
while (!StackEmpty(&st))
{
int left = StackTop(&st);
StackPop(&st);
int right = StackTop(&st);
StackPop(&st);
int keyi = QuickSort2(arr, left, right);
if (left < keyi - 1)
{
StackPush(&st, keyi - 1);
StackPush(&st, left);
}
if (keyi + 1 < right)
{
StackPush(&st, right);
StackPush(&st, keyi + 1);
}
}
DestoryStack(&st);
}
void PrintSort(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[] = { 3,1,2,4,9,5,6};
int len = sizeof(arr) / sizeof(arr[0]);
QuickSort(arr,0,len-1);
PrintSort(arr, len);
}
伙伴们!快来试一下吧!!
如有错误,请指出!
边栏推荐
- 【leetcode周赛总结】LeetCode第 81 场双周赛(6.25)
- leetcode:881. 救生艇
- Is it OK to open the securities account on the excavation finance? Is it safe?
- R language ggplot2 visual density map: Visual density map by group and custom configuration geom_ The alpha parameter in the density function sets the image transparency (to prevent multiple density c
- 分享 12 个最常用的正则表达式,能解决你大部分问题
- ASP.NET大型外卖订餐系统源码 (PC版+手机版+商户版)
- dynamic programming
- R language uses the polR function of mass package to build an ordered multi classification logistic regression model, and uses the coef function to obtain the log odds ratio corresponding to each vari
- World Environment Day | Chow Tai Fook serves wholeheartedly to promote carbon reduction and environmental protection
- 【学习笔记】阶段测试1
猜你喜欢
周大福践行「百周年承诺」,真诚服务推动绿色环保
Principle and performance analysis of lepton lossless compression
乌卡时代下,企业供应链管理体系的应对策略
Shen Ziyu, nouveau Président de Meizu: M. Huang Zhang, fondateur de Meizu, agira comme conseiller stratégique pour les produits scientifiques et technologiques de Meizu
Countermeasures of enterprise supply chain management system in UCA Era
魅族新任董事長沈子瑜:創始人黃章先生將作為魅族科技產品戰略顧問
How to choose the appropriate certificate brand when applying for code signing certificate?
Which Internet companies are worth going to in Shenzhen for software testers [Special Edition for software testers]
Loop invariant
网上电子元器件采购商城:打破采购环节信息不对称难题,赋能企业高效协同管理
随机推荐
Why do mechanical engineers I know complain about low wages?
mysql8.0JSON_ Instructions for using contains
Loop invariant
Sorter evolution of ticdc 6.0 principle
Topology visual drawing engine
展现强大。这样手机就不会难前进
Shen Ziyu, nouveau Président de Meizu: M. Huang Zhang, fondateur de Meizu, agira comme conseiller stratégique pour les produits scientifiques et technologiques de Meizu
Judge whether the variable is an array
Qingda KeYue rushes to the science and Innovation Board: the annual revenue is 200million, and it is proposed to raise 750million
Discussion on memset assignment
be careful! Software supply chain security challenges continue to escalate
Share 20 strange JS expressions and see how many correct answers you can get
How to make a second clip of our media video without infringement
R语言ggplot2可视化:可视化折线图、使用theme函数中的legend.position参数自定义图例的位置
循环不变式
用“新”字来吸引好奇的人群
Thymeleaf 常用函数
总量分析 核算方法和势方法 - 分摊分析
ASP. Net large takeout ordering system source code (PC version + mobile version + merchant version)
Postman简介、安装、入门使用方法详细攻略!