快速排序
要求
算法描述
算法实现
单边循环快排（lomuto 洛穆托分区方案）
算法描述
图形化展示
代码展示
双边循环快排（不完全等价于 hoare 霍尔分区方案）
算法描述
图形化展示
算法展示
快排特点
洛穆托分区方案 vs 霍尔分区方案
其他排序代码补充
空穴法改进的双边快排
霍尔分区
四种分区实现的移动次数比较
要求
能够用自己语言描述快速排序算法
掌握手写单边循环、双边循环代码之一
能够说明快排特点
了解洛穆托与霍尔两种分区方案的性能比较
算法描述
每一轮排序选择一个基准点（pivot）进行分区
让小于基准点的元素的进入一个分区，大于基准点的元素的进入另一个分区
当分区完成时，基准点元素的位置就是其最终位置
在子分区内重复以上过程，直至子分区元素个数少于等于 1，这体现的是分而治之的思想 （divide-and-conquer）
从以上描述可以看出，一个关键在于分区算法，常见的有洛穆托分区方案、双边循环分区方案、霍尔分区方案
算法实现
单边循环快排（lomuto 洛穆托分区方案）
算法描述
选择最右元素作为基准点元素
j 指针负责找到比基准点小的元素，一旦找到则与 i 进行交换
i 指针维护小于基准点元素的边界，也是每次交换的目标索引
最后基准点与 i 交换，i 即为分区位置
图形化展示
代码展示
public static void quick(int[] a, int l, int h) { if (l >= h) { return; } int p = partition(a, l, h); // p 索引值 quick(a, l, p - 1); // 左边分区的范围确定 quick(a, p + 1, h); // 左边分区的范围确定 } private static int partition(int[] a, int l, int h) { int pv = a[h]; // 基准点元素 int i = l; for (int j = l; j < h; j++) { if (a[j] < pv) { if (i != j) { swap(a, i, j); } i++; } } if (i != h) { swap(a, h, i); } System.out.println(Arrays.toString(a) + " i=" + i); // 返回值代表了基准点元素所在的正确索引，用它确定下一轮分区的边界 return i; } public static void swap(int[] array, int i, int j) { int t = array[i]; array[i] = array[j]; array[j] = t; }
双边循环快排（不完全等价于 hoare 霍尔分区方案）
算法描述
选择最左元素作为基准点元素
j 指针负责从右向左找比基准点小的元素，i 指针负责从左向右找比基准点大的元素，一旦找到二者交换，直至 i，j 相交
最后基准点与 i（此时 i 与 j 相等）交换，i 即为分区位置
要点
基准点在左边，并且要先 j 后 i
while( i< j && a[j] > pv ) j–
while ( i< j && a[i] <= pv ) i++
图形化展示
算法展示
private static void quick(int[] a, int l, int h) { if (l >= h) { return; } int p = partition(a, l, h); quick(a, l, p - 1); quick(a, p + 1, h); } private static int partition(int[] a, int l, int h) { int pv = a[l]; int i = l; int j = h; while (i < j) { // j 从右找小的 while (i < j && a[j] > pv) { j--; } // i 从左找大的 while (i < j && a[i] <= pv) { i++; } swap(a, i, j); } swap(a, l, j); System.out.println(Arrays.toString(a) + " j=" + j); return j; } public static void swap(int[] array, int i, int j) { int t = array[i]; array[i] = array[j]; array[j] = t; }
快排特点
1、平均时间复杂度是
，最坏时间复杂度
2、数据量较大时，优势非常明显
3、属于不稳定排序
洛穆托分区方案 vs 霍尔分区方案
霍尔的移动次数平均来讲比洛穆托少3倍
https://qastack.cn/cs/11458/quicksort-partitioning-hoare-vs-lomuto
其他排序代码补充
空穴法改进的双边快排
import java.util.Arrays; // 空穴法(双边循环法改进) @SuppressWarnings("all") public class QuickSort3 { public static void main(String[] args) { int[] a = {5, 3, 7, 2, 9, 8, 1, 4}; System.out.println(Arrays.toString(a)); quick(a, 0, a.length - 1); } private static void quick(int[] a, int l, int h) { if (l >= h) { return; } int p = partition(a, l, h); quick(a, l, p - 1); quick(a, p + 1, h); } private static int partition(int[] a, int l, int h) { int pv = a[l]; int i = l; int j = h; while (i < j) { // j 从右找小的 while (i < j && a[j] > pv) { j--; } if (i < j) { a[i] = a[j]; i++; } // i 从左找大的 while (i < j && a[i] <= pv) { i++; } if (i < j) { a[j] = a[i]; j--; } } a[j] = pv; System.out.println(Arrays.toString(a) + " j=" + j); return j; } }
霍尔分区
import java.util.Arrays; public class QuickSortHoare { public static void main(String[] args) { // int[] a = {1,2,3}; // int[] a = {9, 3, 2, 1}; // int[] a = {9, 3, 7, 2, 5, 8, 1, 4}; int[] a = {1, 2, 3, 4, 5, 7, 8, 9}; System.out.println(Arrays.toString(a)); quick0(a, 0, a.length - 1); } private static void quick0(int[] a, int l, int h) { if (l >= h) { return; } int p = partition(a, l, h); colorPrint(a, l, p, p + 1, h); // 注意如果左边界选择了 p-1, 则会因为返回的 p 可能不是基准点位置导致出错 quick0(a, l, p); quick0(a, p + 1, h); } private static void colorPrint(int[] a, int r1l, int r1h, int r2l, int r2h) { System.out.print("["); for (int i = 0; i < a.length; i++) { if (i >= r1l && i <= r1h) { System.out.print("\033[31m" + a[i] + "\033[0m"); } else if (i >= r2l && i <= r2h) { System.out.print("\033[34m" + a[i] + "\033[0m"); } else { System.out.print("_"); } if (i < a.length - 1) { System.out.print(" "); } } System.out.println("]"); } private static int partition(int[] a, int l, int h) { // int pv = a[l]; int pv = a[(l + h) >>> 1]; System.out.println("pv=" + pv); int i = l - 1; int j = h + 1; while (true) { while (a[++i] < pv) { } while (a[--j] > pv) { } if (i >= j) { return j; } swap(a, i, j); } } } public static void swap(int[] array, int i, int j) { int t = array[i]; array[i] = array[j]; array[j] = t; }
四种分区实现的移动次数比较
import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.concurrent.atomic.AtomicInteger; public class LomutoVsHoare { public static void main(String[] args) { List<int[]> all1 = new ArrayList<>(); List<int[]> all2 = new ArrayList<>(); List<int[]> all3 = new ArrayList<>(); List<int[]> all4 = new ArrayList<>(); for (int i = 0; i < 20; i++) { int[] array = Utils.randomArray(10000); all1.add(array); all2.add(Arrays.copyOf(array, array.length)); all3.add(Arrays.copyOf(array, array.length)); all4.add(Arrays.copyOf(array, array.length)); } System.out.println("hoarePartition"); testPartition(all1, LomutoVsHoare::hoarePartition); System.out.println("LomutoPartition"); testPartition(all2, LomutoVsHoare::LomutoPartition); System.out.println("otherPartition"); testPartition(all3, LomutoVsHoare::otherPartition); System.out.println("moveInsteadSwapPartition"); testPartition(all4, LomutoVsHoare::moveInsteadSwapPartition); } private static void testPartition(List<int[]> all, FourConsumer consumer) { List<AtomicInteger> cs = new ArrayList<>(); for (int[] array : all) { AtomicInteger c = new AtomicInteger(); consumer.apply(array, 0, array.length - 1, c); cs.add(c); } // 打印的是平均移动次数，而非交换次数，一次交换有3次移动 System.out.println(cs + " avg:" + cs.stream().mapToLong(AtomicInteger::get).average().orElse(0)); } interface FourConsumer { void apply(int[] a, int b, int c, AtomicInteger d); } private static int hoarePartition(int[] a, int l, int h, AtomicInteger c) { // int pv = a[l]; int pv = a[(l + h) >>> 1]; int i = l - 1; int j = h + 1; while (true) { while (a[++i] < pv) { } while (a[--j] > pv) { } if (i >= j) { return j; } c.accumulateAndGet(3, Integer::sum); swap(a, i, j); } } private static int LomutoPartition(int[] a, int l, int h, AtomicInteger c) { int pv = a[h]; int i = l; for (int j = l; j < h; j++) { if (a[j] < pv) { if (i != j) { c.accumulateAndGet(3, Integer::sum); swap(a, i, j); } i++; } } if (i != h) { c.accumulateAndGet(3, Integer::sum); swap(a, h, i); } return i; } private static int otherPartition(int[] a, int l, int h, AtomicInteger c) { int pv = a[l]; int i = l; int j = h; while (i < j) { while (i < j && a[j] > pv) { j--; } while (i < j && a[i] <= pv) { i++; } c.accumulateAndGet(3, Integer::sum); swap(a, i, j); } c.accumulateAndGet(3, Integer::sum); swap(a, l, i); return i; } private static int moveInsteadSwapPartition(int[] a, int l, int h, AtomicInteger c) { int pv = a[l]; int i = l; int j = h; while (i < j) { // j 从右找小的 while (i < j && a[j] > pv) { j--; } if (i < j) { c.incrementAndGet(); a[i] = a[j]; i++; } // i 从左找大的 while (i < j && a[i] <= pv) { i++; } if (i < j) { c.incrementAndGet(); a[j] = a[i]; j--; } } c.incrementAndGet(); a[j] = pv; return j; } public static void swap(int[] array, int i, int j) { int t = array[i]; array[i] = array[j]; array[j] = t; } }
