当前位置：网站首页>[eight sorting ③] quick sorting (dynamic graph deduction Hoare method, digging method, front and back pointer method)
[eight sorting ③] quick sorting (dynamic graph deduction Hoare method, digging method, front and back pointer method)
2022-07-02 00:44:00 【Living_ Amethyst】
Catalog
One 、 Bubble sort （Bubble Sort）
A common way to divide an interval into left and right halves according to the reference value ：
3、 Front and back pointer method
Non recursive implementation of quick sorting
One 、 Bubble sort （Bubble Sort）
The principle of bubble sorting
From left to right , Compare adjacent elements . Compare one round at a time , You will find the largest or smallest in the sequence . This number will appear from the far right of the sequence .
- Take sorting from small to large as an example ,
- Compare adjacent elements . If the first one is bigger than the second one , Just swap them .
- Do the same for each pair of adjacent elements , From the beginning of the first couple to the end of the last couple . After this step , The last element will be the maximum number .
- Repeat the above steps for all elements , Except for the last one .
- Keep repeating the above steps for fewer and fewer elements each time , Until there's no pair of numbers to compare .
- After the first round of comparison , The largest of all numbers will float to the far right ; After the second round of comparison , The second largest of all numbers will float to the penultimate position …… Just compare it round by round , Finally, sort from small to large .
When is the fastest
When the input data is already in positive order （ It's all in order , Do I need you to bubble sort ？）
When is the slowest
When the input data is in reverse order （ Write a for loop trans Just output the data , Why do you want to bubble sort it ？）
Algorithm stability
Bubble sort is to move small elements forward or to move large elements back . Comparison is the comparison of two adjacent elements , The exchange also happens between these two elements . therefore , If two elements are equal , I don't think you'll be bored to exchange them ; If two equal elements are not adjacent , So even if we exchange the two in front of each other to make the two adjacent , It won't be exchanged at this time , So the order of the same elements hasn't changed , So bubble sort is a stable sort algorithm .
Time complexity ：O(n^2)
Spatial complexity ：O(1)
Code
public static void bubbleSort(int[] array){
for(int i=0; i< array.length-1 ;i++){
for(int j = 0; j < array.length-1-i;j++){
if(array[j] > array[j+1]){
swap(array,j,j+1);
}
}
}
}Optimize ： Avoid meaningless circular judgment in an orderly situation
public static void bubbleSort2(int[] array){
for(int i=0; i< array.length-1 ;i++){
boolean flg = false ;
for(int j = 0; j < array.length-1-i;j++){
if(array[j] > array[j+1]){
swap(array,j,j+1);
flg = true;
}
}
if(!flg){
break;
}
}
}Two 、 Quick sort （Quick Sort）
introduction
Finally, our master is coming , This is listed as 20 Quick sorting, one of the top ten algorithms in the 20th century , We introduced it earlier Shell Sort amount to Directly insert the upgrade of sorting , They all belong to Insert sort class , Heap sort amount to Simply choose the upgrade of sorting , They all belong to Select sort class . and Quick sort In fact, it is the slowest one we thought before Bubble sort upgrade , They all belong to Exchange sort class . That is, it also realizes sorting through continuous comparison and mobile exchange , Just its realization , It increases the time of record comparison and movement , Move records with larger keywords directly from the front to the back , Records with smaller keywords move directly from the back to the front , Thus, the total number of comparisons and mobile exchanges are reduced
Fast sorting algorithm
The basic idea of quick sorting is ： Any... In the element sequence to be sorted A particular element As At baseline , According to the sorting code, the set to be sorted Split into two subsequences , All elements in the left subsequence are less than the base value , All elements in the right subsequence are greater than the base value , Then the leftmost and rightmost subsequences repeat the process , Until all the elements are aligned in their respective positions .
Algorithm description
Fast sorting uses divide and conquer to put a string （list） It's divided into two strings （sub-lists）. The specific algorithm is described as follows ：
- Pick a member of the sequence , be called “ The benchmark ”（pivot）;
- Reorder the sequence , All elements smaller than the base value are placed in front of the base value , All elements that are larger than the base value are placed after the base value （ The same number can go to either side ）. After the partition exits , The benchmark is in the middle of the sequence . This is called a partition （partition） operation ;
- recursively （recursive） Sort the substrings of elements that are less than the base value and elements that are greater than the base value .
// Let's say that... Is sorted in ascending order array Array [left, right) Sort the elements in the interval
void QuickSort(int[] array, int left, int right)
{
if(right - left <= 1)
return;
// Align... According to the reference value array Array of [left, right) The elements in the interval are divided
int div = partion(array, left, right);
// After the division is successful, use div The left and right parts are formed for the boundary [left, div) and [div+1, right)
// Recursive row [left, div)
QuickSort(array, left, div);
// Recursive row [div+1, right)
QuickSort(array, div+1, right);
}The above is a recursive implementation of quick sorting Main frame , Discovery and Binary tree preorder traversal The rules are very much like , When writing a recursive framework, you can think about the pre order traversal rules of binary tree, which can be written quickly , In the following sequence, you only need to analyze how to divide the data in the interval according to the benchmark value .
A common way to divide an interval into left and right halves according to the reference value ：
1、Hoare edition
Hoare Law is the founder of fast platoon Hoare Named , It is also the initial implementation version of fast platoon . Its basic idea is to use Two pointers Respectively point to the... Of the array to be sorted start and ending .
- If we take the header value as our key value , Then we must let the right pointer move first
- If we take the tail value as our key value , Then we must let the left pointer move first
Pictured , We take the header value as key value
How to move and How to find benchmark
- right Pointer until less than key The value of just stopped
- left Pointer until greater than key The value of just stopped
- take left and right Exchange the corresponding values . Repeat the above process until the two meet
- After encounter , take key The value of the subscript is exchanged with the value where it meets
- At this point, the meeting place is the benchmark
Let's use the dynamic diagram to deduce
Code ：
//Hoare Law
public static int partitionHoare(int[] array,int low,int high){
int key = low;
while(low < high){
while (low < high && array[high] >= array[key]){
high--;
}
// here high Subscript is the number you are looking for
while (low < high && array[low] <= array[key]){
low++;
}
// here low Subscript is the number you are looking for
swap(array,low,high); //low and high Subscript element exchange
}
// here low and high Met
swap(array,low,key);
return low;
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
int pivot = partition(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}It should be noted that
2. Excavation method
We need to be in key Dig a hole （ hold 6 Take it out and put it in one tmp variable ）, Form a pit , then R Look to the left 6 Put the small one into the pit , A new pit is formed , then L Look right , Find the ratio 6 Big , Put it into a new pit
We still use dynamic graph to deduce
The advantage of digging is that it is easier for us to understand , According to this idea, we write a fast platoon by digging a pit
// Excavation method
public static int partitionHole(int[] array,int low,int high){
int tmp = array[low];
while(low < high) {
while (low < high && array[high] >= tmp){
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
int pivot = partitionHole(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}3、 Front and back pointer method
edition 1
seeing the name of a thing one thinks of its function , need Two pointers , One in front, one in back , Use them separately cur Indicates the front pointer ,prev Represents the back pointer , At the beginning , Our rules cur stay prev The next position of , Here we still choose the first number as the benchmark
- prev Each time, it needs to point to the last number less than the benchmark value from the left to itself
- If cur The value of is greater than the reference value , At this time, only cur++
- If cur The pointing position is smaller than the reference value
- Then we let prev++
- Judge prev++ Whether it is related to cur Equal position
- If not equal , The exchange cur and prev Value
- until cur > R after , We'll exchange prev and key, In this way, the position of the reference value is determined
Now we are still Dynamic graph deduction
Code
// Front and back pointer method 1
private static int partition(int[] array,int low,int high){
int prev = low;
int cur = low+1;
while (cur <= high){
if(array[cur] < array[low] && array[++prev]!=array[cur]){
swap(array,cur,prev);
}
cur++;
}
swap(array,prev,low);
return low;
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
int pivot = partition(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}
edition 2
This way of writing may be better understood , But the essence is the same
// Front and back pointer method 2
private static int partition2(int[] array,int low,int high){
int d = low+1;
int tmp = array[low];
for(int i = low+1;i <= high; i++){
if(array[i] < tmp){
swap(array,i,d);
d++;
}
}
swap(array,d-1,low);
return d-1;
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
int pivot = partition2(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}Optimization of quicksort
Smaller scale optimization
Every time you recurse , The data is slowly becoming orderly
When the amount of data is small and tends to be orderly , We can directly use insert sorting to optimize
public static int partitionHole(int[] array,int low,int high){
int tmp = array[low];
while(low < high) {
while (low < high && array[high] >= tmp){
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
if(right-left+1 <= 10000){ // The small-scale sorting in a certain interval is directly inserted into the sorting
// Insert sort
insertSortRange(array,left,right);
return;
}
int pivot = partitionHole(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}
public static void insertSortRange(int[] array,int low, int end){
for(int i = low+1 ; i<=end ;i++){
int tmp = array[i];
int j = i-1;
for(; j >= low ; j--){
if(array[j] > tmp){
array[j+1] = array[j];
}else{
break;
}
}
array[j+1] = tmp;
}
}But this optimization has not been fundamentally solved In order Optimization with too deep recursion
If you want to fundamentally solve the problem , Try to make each division more uniform
Take the middle of three
We use it Take the middle of three choose key
- Take the three Numbers ： head , tail , In the middle element Size centered The one of
Then exchange this element with the team head element , As key
Let's take a look at the code
public static int partitionHole(int[] array,int low,int high){
int tmp = array[low];
while(low < high) {
while (low < high && array[high] >= tmp){
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
// Take the three Numbers , Find the first , in , Of the last three numbers Subscript of a medium-sized number
private static int medianOfThreeIndex(int[] array, int left, int right){
int mid = left + ((right-left)>>>1);
//int mid = (right+left)/2 ;
if(array[left] < array[right]){
if(array[mid] < array[left]){
return left;
}else if(array[mid] > array[right]){
return right;
}else{
return mid;
}
}else{
if(array[mid] < array[right]){
return right;
}else if(array[mid] > array[left]){
return left;
}else{
return mid;
}
}
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
//1. The small-scale sorting in a certain interval is directly inserted into the sorting 【 The optimization is the comparison within the interval 】
if(right-left+1 <= 10000){
// Insert sort
insertSortRange(array,left,right);
return;
}
//2. Take the middle of three 【 What is optimized is the segmentation of itself 】
int index = medianOfThreeIndex(array,left,right);
swap(array,left,index);
int pivot = partitionHole(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}Non recursive implementation of quick sorting
We need to use Stack
We used to be after we had determined the benchmark , Do the same operation recursively for the remaining intervals
Now let's create a stack , Put the left of the remaining interval 、 The subscripts at the right position are put into the stack respectively , As shown in the figure, a benchmark has been found 6 The situation of
then Pop up an element at the top of the stack 9 to H, Pop up another stack top element 6 to L, According to the new L and H Find a new benchmark , Repeat the above operation
Code
// Excavation method
public static int partitionHole(int[] array,int low,int high){
int tmp = array[low];
while(low < high) {
while (low < high && array[high] >= tmp){
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
// Quick sort （ Non recursive ）
public static void quickSortNor(int[] array,int left,int right){
Stack<Integer> stack = new Stack<>();
int pivot = partitionHole(array,left,right);
if(pivot > left+1){
// Explain that there are two or more data on the left
stack.push(left);
stack.push(pivot-1);
}
if(pivot < right-1){
stack.push(pivot+1);
stack.push(right);
}
while (!stack.isEmpty()){
right = stack.pop();
left = stack.pop();
pivot = partitionHole(array,left,right);
if(pivot > left+1){
// Explain that there are two or more data on the left
stack.push(left);
stack.push(pivot-1);
}
if(pivot < right-1){
stack.push(pivot+1);
stack.push(right);
}
}
}
Quick sort summary
1. The overall performance and usage scenarios of quick sort are quite good , That's why we call it quick sort
2. Time complexity ：O(N*logN)
3. Spatial complexity ：O(logN)
4. stability ： unstable
边栏推荐
- Friends circle community program source code sharing
- excel数据透视表
- 【底部弹出-选择器】uniapp Picker组件——底部弹起的滚动选择器
- Is the securities account given by qiniu business school safe? Where can I open an account
- Database -- sqlserver details
- I want to ask, which is the better choice for securities companies? I don't understand. Is it safe to open an account online now?
- Using multithreaded callable to query Oracle Database
- SQL数据分析之窗口排序函数rank、dense_rank、raw_number与lag、lead窗口偏移函数【用法整理】
- 测试人进阶技能：单元测试报告应用指南
- Node -- add compressed file
猜你喜欢
EMC circuit protection device for surge and impulse current protection
Weather forecast applet source code weather wechat applet source code
Ldr6035 smart Bluetooth audio can continuously charge and discharge mobile devices
ThreadLocal内存泄漏是什么，怎么解决
Mysql database driver (JDBC Driver) jar package download
SQL数据分析之流程控制语句【if，case...when详解】
Friends circle community program source code sharing
Leetcode question brushing: stack and queue 07 (maximum value of sliding window)
SSO single sign on implementation.
The origin of usb-if Association and various interfaces
随机推荐
【CTF】bjdctf_ 2020_ babystack2
AIX存储管理之卷组属性的查看和修改（二）
Leetcode skimming: binary tree 01 (preorder traversal of binary tree)
The new version of graphic network PDF will be released soon
How can entrepreneurial teams implement agile testing to improve quality and efficiency? Voice network developer entrepreneurship lecture Vol.03
创业团队如何落地敏捷测试，提升质量效能？丨声网开发者创业讲堂 Vol.03
Otaku wallpaper Daquan wechat applet source code - with dynamic wallpaper to support a variety of traffic owners
PHP reads ini or env type configuration
Node——Egg 创建本地文件访问接口
What skills does an excellent software tester need to master?
[template] adaptive Simpson integral
2022 pinduoduo details / pinduoduo product details / pinduoduo SKU details
Comprehensive usage and case questions of sub query of SQL data analysis [patient sorting]
Leetcode skimming: binary tree 02 (middle order traversal of binary tree)
【CTF】bjdctf_2020_babystack2
毕业季 | 华为专家亲授面试秘诀：如何拿到大厂高薪offer？
使用 ES 实现疫情地图或者外卖点餐功能（含代码及数据）
How to improve data quality
Window sorting functions rank and deny for SQL data analysis_ rank、raw_ Number and lag, lead window offset function [usage sorting]
2023款雷克萨斯ES产品公布，这回进步很有感