当前位置:网站首页>Super wow fast row, you are worth learning!
Super wow fast row, you are worth learning!
2022-07-05 14:48:00 【Old fish 37】
Today we are going to talk about quick sorting , Very wow !
Take a brief look at the quick row ------
Here are three methods of fast platoon , Non optimized and optimized fast platoon
First----hoare edition
That is to say, the first established subscript is key The value of is the comparison value , It is generally believed that the first value on the left is key value , then , From the right , Look for a comparison key Small numbers , When R When you stop ,L Just move , Then find something better than key Big value , Then proceed L、R In exchange for , Eventually they will meet , The value corresponding to the encountered subscript will key Assigned to him , Then divide and rule ,
[left,key-1] key [key+1,right] It's just a recursion
Data structure must learn to draw pictures to think about problems , Make the problem clearer !
Complete code :
//hoare edition
void QuickSort(int* arr, int begin, int end)
{
// Come in and judge
if (begin >= end)
{
return;
}
int left = begin;
int right = end;
int key = left;
while (left < right)
{
// Go first to the right
while (left < right && arr[right] >= arr[key])
{
--right;
}
while (left < right && arr[left] <= arr[key])
{
++left;
}
// In exchange for
Swap(&arr[left], &arr[right]);
}
// Finally met
Swap(&arr[key], &arr[left]);
key = left;// to update key The location of
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);
}
Here's another way , Be optimized by the great gods , It's easy to understand !
2、 Excavation method ------- As the name suggests, there is a pit
Complete code :
// Excavation method
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;// Pit position
while (left < right)// Control range
{
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;
}
// And the last pit we met
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);
}
The third method : Front and back pointer versions
Complete code :
// Front and back pointer versions
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;
}
// There's only one left 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);
}
I believe it's not difficult for you to learn these three methods of fast platoon , But that is not optimized , Next, let's optimize it ! The time complexity of the first three methods is O(N), Not much improvement in efficiency
An optimization method —: Take the three Numbers ( Improve the front and back pointer versions )
The obstacle to efficiency is key, Not every time key It's the smallest , want No key Every time is the biggest , Then efficiency will definitely not go up , If we let key It's in the area middle Then efficiency goes to a higher level , So three numbers are taken in .
// Front and back pointer versions
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end)
{
return;
}
int prev = begin;
int cur = begin + 1;
int key = begin;
// Take the three Numbers
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;
}
// There's only one left prev
Swap(&arr[prev], &arr[begin]);
key = prev;
QuickSort(arr, begin, key - 1);
QuickSort(arr, key + 1, end);
}
Optimization method 2 : Recursion to a small subinterval , Consider using insert sort
Because when the data is in order or close to order , The efficiency of insertion sorting is very impressive , As for why not use hill , Pile up , Because it is faster to use them under big data , But the near ordered time complexity insertion sort is better !
These data can be divided into regions. Finally, the number of recursions close to order accounts for half , So it's very huge .
Area optimization code :
The insertion sort here arr If not begin Words , Then every time it is the front 20 Number to sort , So meaningless ,arr+begin It's in different areas begin----end
This optimization is very cool !
These quick rows are recursive , Recursion is also a disadvantage , So we must also master non recursive methods
Non recursive, we use the stack to complete fast scheduling
The nature of stack is first in and last out , We can use this property perfectly !
Ideas :
It's exactly like the way trees work , Finish sorting the left tree first , Then sort the right tree , Exhausted to the last area , Finally, destroy the stack again to realize non recursive fast sorting
A little more vivid : Of course, using queues is the same , Just make good use of the nature of the queue , Control it
Because this is pure C So first rub a stack , To C++ There's no need for such trouble ,
Non recursive complete code :
// Stack
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)
{
// Check whether it is full
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;
}
// Stack to achieve non recursive fast scheduling
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);
}
partners ! Give it a try !!
If there is a mistake , Please point out !
边栏推荐
- [learning notes] stage test 1
- 详解Vue适时清理keepalive缓存方案
- 用 Go 跑的更快:使用 Golang 为机器学习服务
- CPU设计相关笔记
- Niuke: intercepting missiles
- [learning notes] connectivity and circuit of graph
- 长列表优化虚拟滚动
- 微帧科技荣获全球云计算大会“云鼎奖”!
- 729. 我的日程安排表 I :「模拟」&「线段树(动态开点)」&「分块 + 位运算(分桶)」
- SaaS multi tenant solution for FMCG industry to build digital marketing competitiveness of the whole industry chain
猜你喜欢
CODING DevSecOps 助力金融企业跑出数字加速度
日化用品行业智能供应链协同系统解决方案:数智化SCM供应链,为企业转型“加速度”
Thymeleaf th:with use of local variables
PyTorch二分类时BCELoss,CrossEntropyLoss,Sigmoid等的选择和使用
leetcode:881. 救生艇
ASP. Net large takeout ordering system source code (PC version + mobile version + merchant version)
可视化任务编排&拖拉拽 | Scaleph 基于 Apache SeaTunnel的数据集成
Drive brushless DC motor based on Ti drv10970
Penetration testing methodology
Topology可视化绘图引擎
随机推荐
How to protect user privacy without password authentication?
快消品行业SaaS多租户解决方案,构建全产业链数字化营销竞争力
I collect multiple Oracle tables at the same time. After collecting for a while, I will report that Oracle's OGA memory is exceeded. Have you encountered it?
【NVMe2.0b 14-9】NVMe SR-IOV
【数组和进阶指针经典笔试题12道】这些题,满足你对数组和指针的所有幻想,come on !
Explain Vue's plan to clean up keepalive cache in time
启牛证券账户怎么开通,开户安全吗?
浅谈Dataset和Dataloader在加载数据时如何调用到__getitem__()函数
729. My schedule I: "simulation" & "line segment tree (dynamic open point) &" block + bit operation (bucket Division) "
Thymeleaf 常用函数
黑马程序员-软件测试-10阶段2-linux和数据库-44-57为什么学习数据库,数据库分类关系型数据库的说明Navicat操作数据的说明,Navicat操作数据库连接说明,Navicat的基本使用,
通过npm 或者 yarn安装依赖时 报错 出现乱码解决方式
网上电子元器件采购商城:打破采购环节信息不对称难题,赋能企业高效协同管理
SaaS multi tenant solution for FMCG industry to build digital marketing competitiveness of the whole industry chain
mysql8.0JSON_CONTAINS的使用说明
Intelligent supply chain collaboration system solution for daily chemical products industry: digital intelligent SCM supply chain, which is the "acceleration" of enterprise transformation
The function of qualifier in C language
Online electronic component purchasing Mall: break the problem of information asymmetry in the purchasing process, and enable enterprises to effectively coordinate management
家用电器行业商业供应链协同平台解决方案:供应链系统管理精益化,助推企业智造升级
漫画:优秀的程序员具备哪些属性?