Quick sorting may feel very fast when you hear this name, but the worst case of its algorithm time complexity is the same as insertion sorting. The reason why it becomes quick sort is because its average efficiency is faster than heap sorting. Quick sorting is also based on the idea of division and governance and merge sorting. However, quick sorting is from the original site, and there is no need to open up new storage space directly in the original array. The idea of quick sorting is very simple, which is to select a keyword k to divide the original array into two parts g1 and g2. All elements in g1 are smaller or equal than k, and all data in g2 are larger or equal to k. Quickly sort g1 and g2 respectively, and what we finally get is an ordered array. The sort method in the code is the description of the statement just now. The key algorithm is to find the location of k and divide the original array into two parts. The method getPlocation is the core of quick sorting. His implementation principle is a bit like insert sorting but a bit like. Every time, the element at the end position in the map is used as a keyword. By comparing the end element with the end element, the array is divided into two parts in size. i and j are two dividing lines. The numbers between i and j are larger than core. Elements, i and j are like greedy snakes. When the next number of j is larger than core, j+1, the length of i to j increases. If it is smaller than core, i and j go forward. Just put that decimal in front of i. After looping like this, the starting to end-1 is separated by size. Finally, put the core in the middle and return the core position to the dividing line.
The code copy is as follows:
public class QuickSort {
public int getPlocation(int[] map,int start,int end){
int core=map[end];
int i=start-1;
for(int j=start;j<=end-1;j++){
if(map[j]<=core){
i++;
int cache=map[j];
map[j]=map[i];
map[i]=cache;
}
}
i++;
map[end]=map[i];
map[i]=core;
return i;
}
public void sort(int[] map,int start,int end){
if(start<end){
int p=getPlocation(map, start, end);
sort(map, start, p-1);
sort(map,p+1,end);
}
}
public static void main(String[] args) {
int[] map=new int[]{4,1,5,3,7,12,65,7};
QuickSort qs=new QuickSort();
qs.sort(map, 0, map.length-1);
for (int i = 0; i < map.length; i++) {
System.out.println(map[i]);
}
}
}