第 5 节 双路快排

liweiwei1419 ... 2021-12-23 排序算法
  • 排序算法
  • 分而治之
  • 快速排序
About 5 min

参考代码

import java.util.Random;


class Solution {

    private final static Random random = new Random(System.currentTimeMillis());
    
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivotIndex = partition(nums, left, right);
        quickSort(nums, left, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, right);
    }

    private int partition(int[] nums, int left, int right) {
        // [left..right]
        int randomIndex = left + random.nextInt(right - left + 1); 
        swap(nums, left, randomIndex);
        
        int pivot = nums[left];

        int le = left + 1; // le: less equals
        int ge = right; // ge: greater equals
        // all in nums[left + 1..le) <= pivot
        // all in nums(ge..right] >= pivot
        while (true) {
            while (le <= ge && nums[le] < pivot) {
                le++;
            }

            while (le <= ge && nums[ge] > pivot) {
                ge--;
            }

            // le 来到了第一个大于等于 pivot 的位置
            // ge 来到了第一个小于等于 pivot 的位置

            if (le >= ge) {
                break;
            }
            swap(nums, le, ge);
            le++;
            ge--;
        }
        
        swap(nums, left, ge);
        return ge;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

针对特殊测试用例(有很多重复元素的输入数组)有 3 种版本的快排:

  • 版本 1:基本快排:把等于切分元素的所有元素分到了数组的同一侧,可能会造成递归树倾斜;
  • 版本 2:双指针快排:把等于切分元素的所有元素 等概率 地分到了数组的两侧,避免了递归树倾斜,递归树相对平衡;
  • 版本 3:三指针快排:把等于切分元素的所有元素挤到了数组的中间,在有很多元素和切分元素相等的情况下,递归区间大大减少。

这里有一个经验的总结:之所以快排有这些优化,起因都是来自「递归树」的高度。关于「树」的算法的优化,绝大部分都是在和树的「高度」较劲。类似的通过减少树高度、使得树更平衡的数据结构还有「二叉搜索树」优化成「AVL 树」或者「红黑树」、「并查集」的「按秩合并」与「路径压缩」。

  • 写对「快速排序」的技巧:保持「循环不变量」,即定义的变量在循环开始前、循环过程中、循环结束以后,都保持不变的性质,这个性质是人为根据问题特点定义的。
  • 「循环不变量」的内容在《算法导论》这本书里有介绍。我个人觉得非常有用。「循环不变量」是证明算法有效性的基础,更是写对代码的保证,遵守循环不变量,是不是该写等于号,先交换还是先 ++ ,就会特别清楚,绝对不会写错,我在编码的时候,会将遵守的「循环不变量」作为注释写在代码中

快速排序丢失了稳定性,如果需要稳定的快速排序,需要具体定义比较函数,这个过程叫「稳定化」,在这里就不展开了。

使用「快速排序」解决的经典问题(非常重要):

参考资料:https://www.yuque.com/liweiwei1419/algo/lopi3w

交换操作对有一种类型的数组是失效的,那就是有多个重复元素的数组。

  • 在整个数组包含有大量重复元素的情况下,放在中间的那个 j 的位置也会使得递归的过程变得很不平衡,这个时候我们也可以采取一定的优化措施;
  • 我们优化的思路是:使得切分元素 v 平衡地分散到 j 的两边。

img

参考代码

# 解释最后为什么交换 leftge

image-20220207185004865

Last update: May 2, 2022 13:25
Contributors: suanfa8 , liweiwei1419