要求

    • 能够用自己语言描述快速排序算法
    • 掌握手写单边循环、双边循环代码之一
    • 能够说明快排特点
    • 了解洛穆托与霍尔两种分区方案的性能比较

    算法描述

    1. 每一轮排序选择一个基准点（pivot）进行分区
      1. 让小于基准点的元素的进入一个分区，大于基准点的元素的进入另一个分区
      2. 当分区完成时，基准点元素的位置就是其最终位置
    2. 在子分区内重复以上过程，直至子分区元素个数少于等于 1，这体现的是分而治之的思想 （divide-and-conquer）
    3. 从以上描述可以看出，一个关键在于分区算法，常见的有洛穆托分区方案、双边循环分区方案、霍尔分区方案

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

    1. 选择最右元素作为基准点元素
    2. j 指针负责找到比基准点小的元素，一旦找到则与 i 进行交换
    3. i 指针维护小于基准点元素的边界，也是每次交换的目标索引
    4. 最后基准点与 i 交换，i 即为分区位置

    image.png

    1. public static void quick(int[] a, int l, int h) {
    2.     if (l >= h) {
    3.         return;
    4.     }
    5.     int p = partition(a, l, h); // p 索引值
    6.     quick(a, l, p - 1); // 左边分区的范围确定
    7.     quick(a, p + 1, h); // 左边分区的范围确定
    8. }
    10. private static int partition(int[] a, int l, int h) {
    11.     int pv = a[h]; // 基准点元素
    12.     int i = l;
    13.     for (int j = l; j < h; j++) {
    14.         if (a[j] < pv) {
    15.             if (i != j) { //减少交换
    16.                 swap(a, i, j);
    17.             }
    18.             i++;
    19.         }
    20.     }
    21.     if (i != h) { //减少交换
    22.         swap(a, h, i);
    23.     }
    24.     System.out.println(Arrays.toString(a) + " i=" + i);
    25.     // 返回值代表了基准点元素所在的正确索引，用它确定下一轮分区的边界
    26.     return i;
    27. }

    双边循环快排（不完全等价于 hoare 霍尔分区方案）

    1. 选择最左元素作为基准点元素
    2. j 指针负责从右向左找比基准点小的元素，i 指针负责从左向右找比基准点大的元素，一旦找到二者交换，直至 i，j 相交
    3. 最后基准点与 i（此时 i 与 j 相等）交换，i 即为分区位置

    要点（细节☆）

    1. 基准点在左边，并且要先 移动j 后移动 i。（否则会造成比基准点大的数换到最左位置。）
    2. while( i< j && a[j] > pv ) j—
    3. while ( i< j && a[i] <= pv ) i++

    image.png

    1. private static void quick(int[] a, int l, int h) {
    2.     if (l >= h) {
    3.         return;
    4.     }
    5.     int p = partition(a, l, h);
    6.     quick(a, l, p - 1);
    7.     quick(a, p + 1, h);
    8. }
    10. private static int partition(int[] a, int l, int h) {
    11.     int pv = a[l];
    12.     int i = l;
    13.     int j = h;
    14.     while (i < j) {
    15.         // j 从右找小的
    16.         while (i < j && a[j] > pv) { //内层循环也要加i < j条件，防止过度交换
    17.             j--;
    18.         }
    19.         // i 从左找大的
    20.         while (i < j && a[i] <= pv) { //这里必须<=
    21.             i++;
    22.         }
    23.         swap(a, i, j);
    24.     }
    25.     swap(a, l, j);
    26.     System.out.println(Arrays.toString(a) + " j=" + j);
    27.     return j;
    28. }

    快排特点

    1. 平均时间复杂度是 O(nlog_2⁡n )，最坏时间复杂度 O(n^2)
    2. 数据量较大时，优势非常明显
    3. 属于不稳定排序

    洛穆托分区方案 vs 霍尔分区方案