<> one , brief introduction
Quick sort is （Quick sort） It is an improvement of bubble sorting , It is a very important and widely used high-efficiency sorting algorithm .
<> two , Algorithm idea
Quick sort is to sort through multiple comparisons and exchanges , In one sort, the data to be sorted is divided into two independent parts , Sort the two parts so that all the data in one part is smaller than the other , Then continue to sort the two parts recursively , Finally, all data are orderly .
The general steps are as follows ：
* First, set a boundary value, that is, the reference value, also known as the monitoring post , The data is divided into two parts by this boundary value .
*
Centralize data greater than or equal to the boundary value to the right , Data less than the cut-off value is concentrated to the left . After a sequence , Each data element in the left part is less than the boundary value , All data elements in the right part are greater than or equal to the boundary value , And the data elements on the right are larger than all the data elements on the left .
* then , The data on the left and right can be regarded as two different groups of parts , Repeat the above 1 and 2 step
When the left and right parts are in order , The whole data is sorted .
<> three , Algorithm step diagram
First set three parameters ,first Point to the left end of the interval ,last Point to the right end of the interval ,key Is the current boundary value .
Select one of the data elements to be sorted, usually the first one, as the benchmark value element （key）key=num[0], Set double pointer first Point to the left end of the interval ,last Point to the right end of the interval .
one ,
key First with num[last] Compare , If
num[last]<key, be num[first]=num[last] Compare this to key Put the small number on the left , If num[last]>=key be -
-last, Take it again num[last] And key Compare , until num[last]<key Exchange elements until .
two ,
num[last]<key After exchanging elements , Turn to the left , use num[first] And key Compare , If num[first]<key, be ++first, Then continue the comparison , until num[first]>key, Will num[last]=num[first].
three ,
Repeat the above steps
four ,
End of first sort , obtain [2,11,15,20,9,5] 23 [56,45,35] Then do the same operation on the left and right subsequences .
2 [11,15,20,9,5] 23 [35,45] 56
2 [5,9] 11 [20,15] 23 35 45 56
2 5 9 11 15 20 23 35 45 56
Finish sorting from small to large
<> four , Algorithm performance analysis
Best case
Each data element can be evenly divided into two parts . Get a complete binary tree . If so n Data elements , Then the depth of the number is
The time complexity is O(nlogn)
Worst case scenario
In the worst case , This number has only right subtree or left subtree , The number of comparisons is （n-1）+（n-2) + (n-3) + … +1=n*(n-1)/2
, Therefore, the time complexity is O(n^2), When the data elements to be sorted have been ordered, the time complexity of quick sorting is the highest
The space complexity is O(n）
Quick sort is an unstable sort algorithm , Changes the relative position of data elements , It is also the sorting algorithm with the highest average efficiency in internal sorting .
<> five , code implementation
C
void quick_sort(int *num,int l,int r){ // If less than or equal to 1 Data elements · Directly return to the end of the fast scheduling function r Is the total number of array elements if(l
+1>=r){ return ; } int first=l,last=r-1,key=num[first]; while(first<last){ while
(first<last&&num[last]>=key){ --last; } // If the value is less than key Boundary value exchange num[first]=num[last];
while(first<last&&num[first]<key){ ++first; } // If the value is greater than key Boundary value exchange num[last]=num[
first]; } num[first]=key; // Recursive left and right parts for fast scheduling quick_sort(num,l,first); quick_sort(num,
first+1,r); }
Java
public static int[] quick_sort(int[] num, int l, int r){
//r Is the total number of array elements ,last Subscript equals r-1 int first=l,last=r-1,key=num[first]; while(first<last){
while(first<last&&num[last]>=key){ --last; } // If the value is less than key Boundary value exchange num[first]=num[
last]; while(first<last&&num[first]<key){ ++first; } // If the value is greater than key Boundary value exchange num[last]=
num[first]; } num[first]=key; // Recursive left and right parts for fast scheduling if (first>l) { num=quick_sort(num, l,
first); } if (first+1<r){ num=quick_sort(num,first+1,r); } return num; }
The above is the introduction of quick sort algorithm , If there is a problem , You are welcome to make corrections !
Technology
Daily Recommendation