Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Preface: This article provides detailed answers to some of the doubts about the early learning of the quick sort algorithm, and gives an optimized version of the basic quick sort algorithm

1. Let’s talk about quick sort again

The core of the quick sort algorithm is分治思想,The divide and conquer strategy is divided into the following three steps:

1. Decomposition: Decompose the original problem into several similar, smaller sub-problems
2. Solution: If the subproblem is small, solve it directly; otherwise, solve the subproblem recursively
3. Merge: The solution to the original problem is equal to the merger of the solutions to several sub-problems

Applied to the quick sort algorithm:

1. Decomposition: The quick sort algorithm aims to sort the entire array, but the scale is large, so we need to find a way to reduce the scale; its solution is to "select a base element and divide the array into two parts, the left side is smaller than the base element, and the right side is larger than the base element". Repeat the above process continuously to sort the entire array. After completing this operation on the entire array, perform the above process on the left and right intervals respectively.
2. Recursively sort the two subarrays quickly until the length of each subarray is 0 or 1, at which point the arrays are in order.
3. Since the subarrays are already sorted separately during the recursive process, there is no need for an additional merging step.

2. Code implementation and detailed explanation

The key code of quick sort is如何根据基准元素划分数组区间(parttion)There are many ways to decompose, here we only provide one method挖坑法
Code:

class Solution {
    public int[] sortArray(int[] nums) {
        quick(nums, 0, nums.length - 1);
        return nums;
    }

    private void quick(int[] arr, int start, int end) {
        if(start >= end) return;// 递归结束条件
        int pivot = parttion(arr, start, end);
		
		// 递归解决子问题
        quick(arr, start, pivot - 1);
        quick(arr, pivot + 1, end);
    }

	
	// 挖坑法进行分解
    private int parttion(int[] arr, int left, int right) {
        int key = arr[left];
        while(left < right) {
            while(left < right && arr[right] >= key) right--;
            arr[left] = arr[right];
            while(left < right && arr[left] <= key) ++left;
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

Detailed answer:
1. Whystart>=endIs the recursion end condition?

Continue to decompose sub-problems. The size of the final sub-problem is 1, that is, there is only one element. At this time, there is no need to continue decomposing. The start and end pointers point to this element at the same time.

2. Why should right go first? Instead of left?

Who goes first depends on基准元素的位置In the above code, the key is the leftmost element. If you moveleft, left first encounters an element larger than the base element, and then executesarr[right] = arr[left], because there is no savearr[right], this element will be lost
If you go right first, right will first encounter an element smaller than the base element. At this time, executearr[left]=arr[right], because left has not moved at this time, it is still pivot, but the pivot has been saved by us using key

3. Why is arr[right]>=key?> not working?

Greater than or equal to is mainly for processing重复元素问题
For example, there is an array[6,6,6,6,6]If it is >, the right pointer will not move, and the left pointer will not move, and the loop will end in an infinite loop.

4. Why is it called the pit digging method?

When the r pointer encounters the firstarr[r] = arr[l], at this time, the l position is blank, forming a pit

---

3. Optimization of quick sort

There are two main optimization directions:

1. The selection of the pivot value can prove that when the pivot value is randomly selected, the time complexity of quick sort approachesO(N*logN), that is, the best time complexity
2. Processing of repeated elements: If there are a large number of repeated elements in the interval, the above version of the quick sort algorithm will repeat the same elements multiple times; in order to reduce redundant operations, use数组分三块At the same time, if we encounter special test cases (sequential array or reverse array), the time complexity will degenerate toO(N^2)

First, according to a question (sort by color) Understand what is数组分三块
analyze

Code:

class Solution {
    public void sortColors(int[] nums) {
        // 分治 --
        // 1.定义三指针
        int i = 0;// 遍历整个数组
        int l = -1, r = nums.length;

        while(i < r) {
            if(nums[i] == 0) swap(nums,++l,i++);
            else if(nums[i] == 1) i++;
            else swap(nums,--r,i);
        }
        return;
    }

    private void swap(int[] nums,int x,int y) {
        int tmp = nums[x]; nums[x] = nums[y]; nums[y] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• Noticel,r的起始位置, the first and last elements belong to未处理状态, so `l,r cannot point to these two elements and must be outside the interval
• The so-called array is divided into three blocks, that is, using三个指针去分别维护四个区间, one of the intervals is未处理区间, as the cur pointer continues to move, all intervals are processed, and finally there are only three intervals

Apply the above ideas to快速排序的parttion中, the final result is divided into three intervals

Code:

class Solution {
    // 快速排序优化版
    // 分解--解决--合并
    public int[] sortArray(int[] nums) {
        qsort(nums, 0, nums.length - 1);
        return nums;
    }

    private void qsort(int[] nums, int start, int end) {
        if(start >= end) return;// 递归结束条件
        // 分解
        int pivot = nums[start];
        int l = start - 1, r = end + 1, i = start;
        while(i < r) {
            int cur = nums[i];
            if(cur < pivot) swap(nums, ++l, i++);
            else if(cur == pivot) ++i;
            else swap(nums, --r, i);
        }

        // [start, l]  [l+1, r-1]  [r, end]
        // 递归解决
        qsort(nums, start, l);
        qsort(nums, r, end);
    }

    private void swap(int[] nums,int i, int j) {
        int tmp = nums[i];  nums[i] = nums[j]; nums[j] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2. Randomly select benchmark values
Randomly select the benchmark value using random numbers

        int pivot = nums[start + new Random().nextInt(end - start + 1)];
        //               起始位置      随机产生的偏移量

1
2
3

The complete improved code:

class Solution {
    // 快速排序优化版
    // 分解--解决--合并
    public int[] sortArray(int[] nums) {
        qsort(nums, 0, nums.length - 1);
        return nums;
    }

    private void qsort(int[] nums, int start, int end) {
        if(start >= end) return;// 递归结束条件
        // 分解
        int pivot = nums[start + new Random().nextInt(end - start + 1)];
        int l = start - 1, r = end + 1, i = start;
        while(i < r) {
            int cur = nums[i];
            if(cur < pivot) swap(nums, ++l, i++);
            else if(cur == pivot) ++i;
            else swap(nums, --r, i);
        }

        // [start, l]  [l+1, r-1]  [r, end]
        // 递归解决
        qsort(nums, start, l);
        qsort(nums, r, end);
    }

    private void swap(int[] nums,int i, int j) {
        int tmp = nums[i]; 
        nums[i] = nums[j]; 
        nums[j] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

• Significantly improved efficiency

4. Fast Selection Algorithm

The quick selection algorithm is基于快速排序优化版本A time complexity ofO(N)The selection algorithm is used in the following scenarios:第K大/前K大Selection issues such as

01. The Kth largest element in an array
Link: https://leetcode.cn/problems/kth-largest-element-in-an-array/
analyze

• The brute force solution is to usesortSort and return the Kth largest one.
• time complexity:O(N*logN)
• Space complexity:O(logN)Recursive call stack

Next, we use the fast selection algorithm to implementO(N)The time complexity of
Code:

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums, 0, nums.length - 1, k);
    }

    private int qsort(int[] nums, int start, int end, int k) {
        if(start >= end) return nums[start];
        int pivot = nums[start + new Random().nextInt(end - start + 1)];
		
		// 数组分三块  <pivot  ==pivot  >pivot
        int l = start - 1, r = end + 1, i = start;
        while(i < r) {
            if(nums[i] < pivot) swap(nums, ++l, i++);
            else if(nums[i] == pivot) ++i;
            else swap(nums, --r, i);
        }

        // [start, l]  [l+1, r - 1]  [r, end]
        int c = end - r + 1, b = r - 1 - (l + 1) + 1, a = l - start + 1;
        // 分情况讨论  进行选择
        if(c >= k) return qsort(nums, r, end, k);
        else if(b + c >= k) return pivot;
        else return qsort(nums, start, l, k - b - c);// 找较小区间的第(k-b-c)大
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

• The idea of ​​the quick selection algorithm is very similar to that of quick sort. The difference is that the quick selection algorithm only recurses on a part of the interval of each partition result, instead of recursing on the entire interval like quick sort, so the time complexity of the quick selection algorithm is reduced toO(N)