1. Quicksort dynamic diagram

  2. Pseudo code for quicksort

Quick_sort (A, n) {quick_sort_c(A, 0, n-1)} Quick_sort_c (A, p,r) {if p >= r then return q = partition(A, p,r) Q-1) quick_sort_c(A, q+1, r)} partition() selects A random element as pivot (generally, the last element in the range p to r can be selected), then partitions A[p…r], The function returns the subscript of pivot.

  1. Quick sort Java code implementation

    public int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length-1, nums.length); return nums; } public void quickSort(int[] nums,int low,int high,int n){ if(low<high) { int p = partition(nums,low,high); quickSort(nums,low,p-1,n); quickSort(nums,p+1,high,n); } } int partition(int[] nums,int low,int high){ int p = nums[low]; while(low<high) { while(low<high && nums[high]>=p)–high; nums[low] = nums[high]; while(low<high && nums[low]<=p) ++low; nums[high] = nums[low]; } nums[low] = p; return low; }

  2. Time complexity analysis of fast sorting

T (1) = C; When n=1, only constant execution time is required, so it is denoted by C. T(n) = 2 times T(n/2) + n; N >1 According to the above recursive formula, the time complexity of quicksort is approximately O (nlogn).

If the data in the array is already ordered, say 1,3,5,6,8. If we choose the last element as pivot each time, the two intervals will not be equal for each partition. We need to partition approximately n times to complete the whole process of fast sorting. On average, we scan about n/2 elements per partition, in which case the time complexity of quicksort degrades from O(nlogn) to O(n2).

  1. Optimization of partition point selection

(1) The method of taking three numbers

Take out a number from the beginning, the end and the middle of the interval, and then compare the size, and take the middle value of these three numbers as the partition point. In this way, at every interval of a fixed length, take the data out for comparison, and the partition algorithm that takes the median value as the partition point is definitely better than simply taking a certain data. However, if the array to be sorted is large, “middle of three” may not be enough, and “middle of five” or “middle of ten” may be used.

(2) Random method

The random method is to randomly select one element at a time from the interval to be sorted as the partition point. This method does not guarantee that the partition points are selected well every time, but from the perspective of probability, it is unlikely that the partition points are selected badly every time, so on average, the partition points selected in this way are relatively good. It is unlikely that the time complexity will degenerate to the worst-case O(n2).