【面试手撕算法】快速排序算法

快速排序算法详解：

一：理论基础

快速排序（Quicksort）是一种常用的排序算法，它是一种分治算法，通过将问题分解成更小的子问题来解决整个问题。快速排序的基本思想是选择一个基准元素，然后将数组中小于基准元素的元素移到基准元素的左边，大于基准元素的元素移到右边，然后递归地对左右两个子数组进行排序。

二：快速排序的基本思想：

通过一趟排序将待排序列分隔成独立的两部分，其中一部分记录的元素均比另一部分的元素小，则可分别对这两部分子序列继续进行排序，以达到整个序列有序。

三：算法步骤

以下是快速排序的基本步骤：

1. 选择基准元素：从数组中选择一个元素作为基准（通常选择第一个元素、最后一个元素或者随机选择）。

2. 划分：将数组中小于基准元素的元素移到基准元素的左边，大于基准元素的元素移到右边。通常使用两个指针来实现这一步骤，一个从数组的左端开始，一个从右端开始，然后它们向中间移动，直到它们相遇。

3. 递归排序：递归地对划分后的左右两个子数组进行排序。

4. 合并：无需合并，因为排序是原地进行的。

5. 递归终止条件：当子数组的大小为0或1时，递归停止。

四：算法图解

五：手撕算法

分区方法采用：单边循环快排（lomuto 洛穆托分区方案）

知识拓展：洛穆托分区方案

洛穆托分区方案（Lomuto Partition Scheme）是快速排序算法中的一种常见的分区方法之一，由尼古拉斯·洛穆托（Nicolas Lomuto）于1991年提出。它相对简单，易于理解和实现。

该分区方案的基本思想是选择数组中的最后一个元素作为基准（pivot），然后将数组分成两部分：左边部分包含所有小于基准的元素，右边部分包含所有大于等于基准的元素。分区完成后，基准元素位于最终排序位置上。

以下是洛穆托分区方案的基本步骤：

1. 选择基准元素：将数组中最后一个元素作为基准。

2. 遍历数组：从数组的起始位置到倒数第二个元素，使用一个指针（通常称为i）遍历数组。

3. 比较并交换：对于遍历过程中的每个元素，如果元素的值小于基准元素的值，则将其与另一个指针（通常称为j，初始值为数组起始位置）所指向的元素进行交换，并将j向后移动一位。

4. 最后交换：遍历完成后，将基准元素与j指向的元素进行交换，将基准元素放置到最终的位置上。

5. 返回基准索引：返回基准元素的索引。

这个过程完成后，基准元素将位于排序后的最终位置，同时左边的元素都小于基准元素，右边的元素都大于等于基准元素。

洛穆托分区方案相对于其他分区方案（如霍尔分区方案）可能会在某些情况下导致不太均衡的划分，因此在实践中可能不如其他分区方案效率高，但其简单直观的特点使得它在教学和初学者理解快速排序时仍然是一种常用的方法。

public class QuickSort {

    // 单边循环快排
    public void quickSort(int[] nums) {
        doQuickSort(nums, 0, nums.length - 1);
    }

    private void doQuickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        // 分区
        int p = partition(nums, left, right);
        doQuickSort(nums, left, p - 1);
        doQuickSort(nums, p + 1, right);
    }

    /**
     * <h3>单边循环快排（lomuto 洛穆托分区方案）</h3>
     * <p>核心思想：每轮找到一个基准点元素，把比它小的放到它左边，比它大的放到它右边，这称为分区</p>
     * <ol>
     * <li>选择最右元素作为基准点元素</li>
     * <li>j 找比基准点小的，i 找比基准点大的，一旦找到，二者进行交换</li>
     * <ul>
     * <li>交换时机：j 找到小的，且与 i 不相等</li>
     * <li>i 找到 >= 基准点元素后，不应自增</li>
     * </ul>
     * <li>最后基准点与 i 交换，i 即为基准点最终索引</li>
     * </ol>
     */
    private int partition(int[] nums, int left, int right) {
        int pv = nums[right]; // 基准元素
        int i = left; // 找比基准点大的值，如果找到大于等于基准点的值，不在移动
        int j = left; // 找比基准点小的值
        while (j < right) {
            if (nums[j] < pv) {
                if (j != i) {
                    swap(nums, i, j);
                }
                // 只有找到的值比基准点小,i才++，如果大于基准点的至,i不变,j++
                // 等到下次找到比基准点小的值,i和j不相等，进行交换
                i++;
            }
            j++;
        }
        swap(nums, right, i);
        return i;
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}
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

分区方法采用：双边循环快排

知识拓展：双边循环快排

双边循环快速排序（Dual-Pivot Quicksort）是一种改进的快速排序算法，于2009年由Vladimir Yaroslavskiy提出。与传统的快速排序算法相比，双边循环快速排序使用两个基准元素而不是一个，从而使得在处理大型数组时性能更好。

以下是双边循环快速排序的基本步骤：

1. 选择基准元素：从数组中选择两个基准元素。通常情况下，选择数组的第一个元素作为左基准，选择最后一个元素作为右基准。

2. 双边循环：使用两个指针，一个从左边开始（通常称为left），一个从右边开始（通常称为right）。它们分别向数组的中间移动，直到left指向一个大于等于左基准元素，right指向一个小于等于右基准元素的元素。

3. 交换元素：如果left指向的元素大于右基准元素，并且right指向的元素小于左基准元素，则交换它们。

4. 继续循环：继续移动left和right指针，直到它们相遇。

5. 交换基准元素：最后，交换左基准元素和right指针指向的元素，以及右基准元素和left指针指向的元素。此时，左基准元素左边的元素都小于等于左基准，右基准元素右边的元素都大于等于右基准。

6. 递归排序：对基准元素左边和右边的子数组分别递归进行双边循环快速排序。

7. 终止条件：当子数组的大小为0或1时，递归停止。

双边循环快速排序在处理大型数组时具有优势，因为它可以更有效地利用多核处理器的并行性。它的时间复杂度通常为O(nlogn)，且在大多数情况下表现优秀。

public class QuickSort {

    public void quickSort(int[] nums) {
        doQuickSort(nums, 0, nums.length - 1);
    }

    private void doQuickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(nums, left, right);
        doQuickSort(nums, left, p - 1);
        doQuickSort(nums, p + 1, right);
    }

    /**
     * <h3>双边循环快排</h3>
     * <ol>
     * <li>选择最左元素作为基准点元素</li>
     * <li>j 指针负责从右向左找比基准点小或等的元素，i 指针负责从左向右找比基准点大的元素，一旦找到二者交换，直至 i，j 相交</li>
     * <li>最后基准点与 i（此时 i 与 j 相等）交换，i 即为分区位置</li>
     * </ol>
     */
    private int partition(int[] nums, int left, int right) {
        int pv = nums[left]; // 选择最左侧元素作为基准点
        int i = left; // i 指针从左到右找大于基准点的值
        int j = right; // j 指针从右到左找小于基准点的值
        while (i < j) {
            // 1. j 从右向左找小(等)的
            while (i < j && nums[j] > pv) {
                j--;
            }
            // 2. i 从左向右找大的
            while (i < j && nums[i] <= pv) {
                i++;
            }
            // 3. 交换位置
            swap(nums, i, j);
        }
        swap(nums, left, j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}
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

随机基准点

使用随机数作为基准点，避免万一最大值或最小值作为基准点导致的分区不均衡

改进代码：

private int partition(int[] nums, int left, int right) {
        /***************************随机元素作为基准点***************************/
        int index = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(nums,index,left);
        /***************************随机元素作为基准点***************************/
        int pv = nums[left]; // 选择最左侧元素作为基准点
        int i = left; // i 指针从左到右找大于基准点的值
        int j = right; // j 指针从右到左找小于基准点的值
        while (i < j) {
            // 1. j 从右向左找小(等)的
            while (i < j && nums[j] > pv) {
                j--;
            }
            // 2. i 从左向右找大的
            while (i < j && nums[i] <= pv) {
                i++;
            }
            // 3. 交换位置
            swap(nums, i, j);
        }
        swap(nums, left, j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
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

处理重复值

如果重复值较多，则原来算法中的分区效果也不好，如下图中左侧所示，需要想办法改为右侧的分区效果

改进代码

/**
 * <h3>双边循环快排 - 处理相等元素</h3>
 */
public class QuickSortHandleDuplicate {
    public static void quickSort(int[] a) {
        doQuickSort(a, 0, a.length - 1);
    }

    private static void doQuickSort(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(a, left, right);
        doQuickSort(a, left, p - 1);
        doQuickSort(a, p + 1, right);
    }

    /*
            循环内
                i 从 left + 1 开始，从左向右找大的或相等的
                j 从 right 开始，从右向左找小的或相等的
                交换，i++ j--

            循环外 j 和 基准点交换，j 即为分区位置
    */
    private static int partition(int[] a, int left, int right) {
        //随机基准值
        int index = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(a, left, index);

        int pv = a[left]; //基准值
        int i = left + 1;
        int j = right;
        //处理重复值
        while (i <= j) {
            // i 从左向右找大的或者相等的
            while (i <= j && a[i] < pv) {
                i++;
            }
            // j 从右向左找小的或者相等的
            while (i <= j && a[j] > pv) {
                j--;
            }
            if (i <= j) {
                swap(a, i, j);
                i++;
                j--;
            }
        }
        swap(a, left, j);
        return j;
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}
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

• 核心思想是

  • 改进前，i 只找大于的，j 会找小于等于的。一个不找等于、一个找等于，势必导致等于的值分布不平衡
  • 改进后，二者都会找等于的交换，等于的值会平衡分布在基准点两边

• 细节：

  • 因为一开始 i 就可能等于 j，因此外层循环需要加等于条件保证至少进入一次，让 j 能减到正确位置
  • 内层 while 循环中 i <= j 的 = 也不能去掉，因为 i == j 时也要做一次与基准点的判断，好让 i 及 j 正确
  • i == j 时，也要做一次 i++ 和 j-- 使下次循环二者不等才能退出
  • 因为最后退出循环时 i 会大于 j，因此最终与基准点交换的是 j

• 内层两个 while 循环的先后顺序不再重要

六：复杂度分析

快速排序的平均时间复杂度为O(nlogn)，其中n是数组的大小。在最坏情况下，时间复杂度为O(n^2)，但这种情况很少发生，通常情况下表现良好。

其空间复杂度为O(logn)，因为快速排序是原地排序，只需要常数级的额外空间来存储递归调用时的栈空间。