当前位置:网站首页>Why is quicksort so fast?
Why is quicksort so fast?
2020-11-06 21:04:06 【Yard farmland】
Quick sort
First, choose a benchmark pivot, And then go through the array ,
- The less than pivot All moved to pivot Left side ,
- The greater than pivot All moved to pivot To the right of .
thus , This pivot That's where it's located , That is to say, it's arranged 1 Elements .
Then on pivot On the left The order of the number of ,
Yes pivot On the right The order of the number of ,
It's done. .
How about the left and right ?
answer : Same method .
So the express line is also used Divide and conquer method Thought .
「 branch 」
Select a pivot, The problem is divided into
- pivot On the left
- pivot On the right
These two questions .
「 cure 」
It's the method described at the beginning , Until within each interval There is no element or only one element left You can go back to .
「 close 」
Put together, naturally it is .
But how to choose this pivot?
Take the middle one ?
Take the first one ?
Take the last one ?
for instance :{5, 2, 1, 0, 3}.
Take the last one , Namely 3.
And then we need to get rid of 3 The other number is divided into 「 Than 3 Big 」 and 「 Than 3 Small 」 The two part , This process is called partition( Divide ).
We still use 「 Baffle method 」 Thought , You don't have to actually have two arrays to store these two parts , It's using two baffles , I've divided the intervals .
We use it 「 Two pointers 」( It's the baffle ) Divide the array into 「 Three intervals 」, that
- The range on the left is used to put less than pivot The elements of ;
- The range on the right is used to put greater than pivot The elements of ;
- In the middle is the unsorted interval .
So when initializing , We need to make sure 「 Unordered range 」 Be able to contain except 3 All the elements beyond , therefore
- Unordered range = [i, j]
So the left and right sections become :
- [0, i): Compare 3 Small number ;
- (j, array.length -2]: Compare 3 Large number
Be careful ️ i, j It's not included in the left and right ranges .
So our goal is check Every number in an unsorted interval , And put it in the right range , To narrow the unsorted range , Until there are no unordered elements .
From left to right check:
Step1.
5 > 3, therefore 5 Put it in the right range , therefore 5 and j Point to the 0 In exchange :
such 5 Just line up , The pointer j --, So our unsorted interval is one less number ;
Step2.
0 < 3, So it should be on the left , direct i++;
Step3.
2 < 3, Empathy ,i++;
Step4.
1 < 3, Empathy ,i++;
So when the two hands are out of place , We end the cycle .
But it's one step short ,3 Not in the right place . So insert it between two intervals , That is, with the pointer i In exchange .
Sister Qi declared that : We are not encouraged to put pivot On the far left .
Basically all the books are on the right , Since the left and right sides are the same , We will follow the default of everyone 、 Come to a consensus , There's no need to “ new in order to be different ”.
For example, the four stars in go , But what pays attention to chess is to set your own star position first , Instead of reaching out to the opponent's side .
Then when we put pivot After changing back to the right position , Whole partition It's over .
And then it's recursive , Just sort the left and right sides .
Finally, there are two questions I would like to discuss with you :
- Back to the beginning choice pivot The problem of , Take the last one every time , How about this ?
answer : Not good .
Because we want to split the array More even , Uniform time complexity is lower ; But if it's an ordered array , So the last one is always the most uneven one .
So it should be Random take pivot, In this way, we can avoid the situation that the array itself always gets the maximum value .
- pivot Where to put it
After random selection , We still have to take this pivot To the far right of the entire array , So our unsorted interval is Successive , Otherwise, every time I walk to pivot There's also the thought of skipping it , I'm so tired .
class Solution {
public void quickSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
quickSort(array, 0, array.length - 1);
}
private void quickSort(int[] array, int left, int right) {
// base case
if (left >= right) {
return;
}
// partition
Random random = new Random(); // java.util The random number generator in
int pivotIndex = left + random.nextInt(right - left + 1);
swap(array, pivotIndex, right);
int i = left;
int j = right-1;
while (i <= j) {
if (array[i] <= array[right]) {
i++;
} else {
swap(array, i, j);
j--;
}
}
swap(array, i, right);
//「 branch 」
quickSort(array, left, i-1);
quickSort(array, i+1, right);
}
private void swap(int[] array, int x, int y) {
int tmp = array[x];
array[x] = array[y];
array[y] = tmp;
}
}
The space-time complexity here has a lot to do with whether the points are uniform or not , So let's look at the situation :
1. Divide equally
Time complexity
If you can divide it almost evenly every time , that
- This is the main time of each cycle while In circulation , That is to say O(right - left);
- If it's even, it's logn layer ;
- So the total time is O(nlogn).
Spatial complexity
- The height of the recursive tree is logn,
- The space complexity of each floor is O(1),
- So the total spatial complexity is O(logn).
2. Most uneven
If you can get the maximum every time / minimum value , So the recursive tree looks like this :
Time complexity
As shown in the figure above :O(n^2)
Spatial complexity
The height of this recursive tree becomes O(n).
3. summary
Actually , Most of the time it will be close to uniform The situation of , So the uniform case is a average case.
Why does it seem like the best is actually an average situation ?
Because even if you don't get to the middle point , For example, it is divided into 10% and 90% The numbers on both sides , In fact, the time of each floor is still O(n), It's just The number of layers has changed to 9 At the bottom of the log, The total time is still O(nlogn).
So the average time complexity of the fast queue is O(nlogn).
stability
Then you should be able to see it , stay swap When , Has broken the relative order between the elements , So fast platoon is not stable .
We also answer the question at the beginning , Namely
-
Why for primitive type Use fast platoon ,
- Because it's the fastest ;
-
Why for object Use merge ,
- Because it's stable and fast .
That's all the content of the quick queue , It's also a very common test ! In the next article, I'll talk about a few topics extended from quick scheduling , Guess what it is ?
If you like this article , Remember to leave me a like message ~ Your support and recognition , It's the biggest driving force of my creation , See you in the next article !
This is Qi , New York program , Lifelong learners , Every night 9 spot , Let's meet you in the cloud study room !
See my... For more dry articles Github: https://github.com/xiaoqi6666/NYCSDE
版权声明
本文为[Yard farmland]所创,转载请带上原文链接,感谢
边栏推荐
- C++ 数字、string和char*的转换
- C++学习——centos7上部署C++开发环境
- C++学习——一步步学会写Makefile
- C++学习——临时对象的产生与优化
- C++学习——对象的引用的用法
- C++编程经验(6):使用C++风格的类型转换
- Won the CKA + CKS certificate with the highest gold content in kubernetes in 31 days!
- C + + number, string and char * conversion
- C + + Learning -- capacity() and resize() in C + +
- C + + Learning -- about code performance optimization
猜你喜欢
-
C + + programming experience (6): using C + + style type conversion
-
Latest party and government work report ppt - Park ppt
-
在线身份证号码提取生日工具
-
Online ID number extraction birthday tool
-
️野指针?悬空指针?️ 一文带你搞懂!
-
Field pointer? Dangling pointer? This article will help you understand!
-
HCNA Routing&Switching之GVRP
-
GVRP of hcna Routing & Switching
-
Seq2Seq实现闲聊机器人
-
【闲聊机器人】seq2seq模型的原理
随机推荐
- LeetCode 91. 解码方法
- Seq2seq implements chat robot
- [chat robot] principle of seq2seq model
- Leetcode 91. Decoding method
- HCNA Routing&Switching之GVRP
- GVRP of hcna Routing & Switching
- HDU7016 Random Walk 2
- [Code+#1]Yazid 的新生舞会
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- HDU7016 Random Walk 2
- [code + 1] Yazid's freshman ball
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- Qt Creator 自动补齐变慢的解决
- HALCON 20.11:如何处理标定助手品质问题
- HALCON 20.11:标定助手使用注意事项
- Solution of QT creator's automatic replenishment slowing down
- Halcon 20.11: how to deal with the quality problem of calibration assistant
- Halcon 20.11: precautions for use of calibration assistant
- “十大科学技术问题”揭晓!|青年科学家50²论坛
- "Top ten scientific and technological issues" announced| Young scientists 50 ² forum
- 求反转链表
- Reverse linked list
- js的数据类型
- JS data type
- 记一次文件读写遇到的bug
- Remember the bug encountered in reading and writing a file
- 单例模式
- Singleton mode
- 在这个 N 多编程语言争霸的世界,C++ 究竟还有没有未来?
- In this world of N programming languages, is there a future for C + +?
- es6模板字符
- js Promise
- js 数组方法 回顾
- ES6 template characters
- js Promise
- JS array method review
- 【Golang】️走进 Go 语言️ 第一课 Hello World
- [golang] go into go language lesson 1 Hello World