A kind of improvement in bubbling sorting is that if the initial record sequence is ordered or basically ordered by keywords, it will degenerate into bubbling sorting. The principle of recursion is used, and its average performance is best among all sorting methods of the same order of magnitude O(n longn). In terms of average time, it is currently considered the best internal sorting method.
The basic idea is: divide the data to be sorted into two independent parts by lying sorting, and all the data in part are smaller than all the data in the other part, and then quickly sort these two parts of the data according to this method. The entire sorting process can be performed recursively to achieve the entire data becoming an ordered sequence.
Three pointers: The first pointer is called a pivotkey pointer (pivot), the second pointer and the third pointer are left pointer and right pointer, respectively, pointing to the leftmost value and the rightmost value. The left pointer and the right pointer approach from both sides to the middle at the same time. During the approximation process, they constantly compare with the pivot, move the element smaller than the pivot to the lower end, and move the element larger than the pivot to the higher end. It will never change after selection, and it will eventually be in the middle, with small in front and large in the back.
Two functions are required:
① Recursive function public static void quickSort(int[]n ,int left,int right)
② Segment function (one quick sort function) public static int partition(int[]n ,int left,int right)
JAVA source code (run successfully):
The code copy is as follows:
package testSortAlgorithm;
public class QuickSort {
public static void main(String[] args) {
int [] array = {49,38,65,97,76,13,27};
quickSort(array, 0, array.length - 1);
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
/*First write the algorithm as the data prototype according to the array, and then write the scalability algorithm. Array {49,38,65,97,76,13,27}
* */
public static void quickSort(int[]n ,int left,int right){
int pivot;
if (left < right) {
// Pivot as the pivot, the smaller element is on the left and the larger element is on the right
pivot = partition(n, left, right);
//Recursively call quick sort on left and right arrays until the order is completely correct
quickSort(n, left, pivot - 1);
quickSort(n, pivot + 1, right);
}
}
public static int partition(int[]n ,int left,int right){
int pivotkey = n[left];
//The pivot will never change after being selected, and it will eventually be in the middle, with small front and large back
while (left < right) {
while (left < right && n[right] >= pivotkey) --right;
//Move the element smaller than the pivot to the low end. At this time, the right position is equivalent to empty, and wait for the number larger than the pivotkey to fill in the low position.
n[left] = n[right];
while (left < right && n[left] <= pivotkey) ++left;
//Move the element larger than the pivot to the high end. At this time, the left position is equivalent to empty, and wait for the number smaller than the pivotkey to fill the high position.
n[right] = n[left];
}
//When left == right, complete a quick sorting trip. At this time, the left bit is equivalent to empty, wait for the pivotkey to be filled
n[left] = pivotkey;
return left;
}
}