Quick sorting can be said to be a must know often meet test questions, but also has a variety of implementation methods. In this article, I used random three-way quicksort.

Random quicksort is used instead of ordinary quicksort. Because the former can reduce the probability of sequence order, so that the average speed of random quicksort is faster than quicksort. For specific performance differences between the two, see this article:

Blog.csdn.net/haelang/art…

Talk ID cheap, show the code. There are 20+ lines of code, and each line is commented. The method of swapping array elements and printing elements is not pasted, because the code is too long for you to see.

PS: There is an execution flow chart below the code, which is easier to understand with the code.

Public static void main(String[] args) {// test data int[] arr = new int[]{5, 3, 6, 4}; // Execute quickSort(arr, 0, arr. Length-1); // Prints an array elementprintArray(arr);                           
 }  
 
private static void quickSort(int[] arr, int l, int r) {               
     if// Swap (arr, l + (int) (math.random () * (r-l + 1)), r); Int [] part = partition(arr, l, r); QuickSort (arr, L, Part [0] -1); // quickSort(arr, Part [1] + 1, r); Private static int[] partition(int[] arr, int l, int r) {private static int[] partition(int[] arr, int l, int r) { Int more = r; // Initialize the current index of the region greater than the partition value. // The current subscript is less than or greater than the subscript of the partition value regionwhile(l < more) {// The current value is smaller than the score value. The current value and the first value to the right of the partition value area are swapped. The partition value area moves 1 subscript to the right, and the current subscript +1if(arr[l] < arr[r]) { swap(arr, l++, ++less); // If the current value is greater than the partition value, the current value is swapped with the first value to the left of the region greater than the partition value, and the region greater than the partition value is moved left by 1 subscript}else if(arr[l] > arr[r]) { swap(arr, l, --more); // The current value equals the partition value, the current subscript +1}else{// current subscript +1 l++; }} // Swap the partition value with the element that is closest to the partition value in the greater partition value region. Swap (arr, more, r); // Returns the range equal to the partition valuereturn new int[]{less + 1, more};                                                                                       
} 
Copy the code

I’m going to draw a flow chart to help you understand this, but the test data is the same as the code.

Assume that after 13 lines of code execution, the test data is in the same order as {5,3,6,4}.

Next, in the partition() method, the array elements look like this.

Well, that’s all for this article. See you in the next article. Cover your face and run

PS: This article was originally published in the wechat public account “not only Java”, the background reply “Java”, send you 13 Classic Java e-books. The public account focuses on sharing Java dry goods, reading notes, growth thinking