一、快速排序法的原理
二、Partition
我们通过partition这个函数,就能够实现我们上面的需求,那么我们的partition函数该如何写呢,看下面的图,相信很容易理解,我们慢慢深入看它
第一版快速排序法
package quicksort; import List.Array; import MergeSort.ArrayGenerator; import MergeSort.SortingHelper; import java.util.Arrays; public class QuickSort { private QuickSort() { } public static <E extends Comparable<E>> void sort(E[] arr) { sort(arr, 0, arr.length - 1); } private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) { if (l >= r) { return; } int p = partition(arr, l, r); sort(arr, l, p - 1); sort(arr, p + 1, r); } private static <E extends Comparable<E>> int partition(E[] arr, int l, int r) { // arr[l+1...j] < v; arr[j+1...i] >= v int j = l; for (int i = l + 1; i <= r; i++) { if (arr[i].compareTo(arr[l]) < 0) { j++; swap(arr, i, j); } } swap(arr, l, j); return j; } /** * 简单的数组元素交换 * * @param arr * @param i * @param j * @param <E> */ private static <E> void swap(E[] arr, int i, int j) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static void main(String[] args) { int n = 10000000; Integer[] arr = ArrayGenerator.generateRandomArray(n,n); Integer[] arr2 = Arrays.copyOf(arr,arr.length); SortingHelper.sortTest("MergeSort",arr); SortingHelper.sortTest("QuickSort",arr2); } }
代码运行情况
三、第一版快速排序用法的问题
之前我们测试的是随机的数组,现在我们来测试一下完全有序的数组,看看会怎么样
这时候不报错啦,但是我们也可以看到,时间居然高了那么多?
我们来看看它内部做了什么
解决办法
我们的标定点不是一直使用最左边了,变成随机选一个标定点,然后把它和最左边的进行互换,这样就可以解决了! [aru_43]
private static <E extends Comparable<E>> int partition(E[] arr, int l, int r) { // 生成[l,r] 之间的随机索引 int p = l + (new Random()).nextInt(r - l + 1); swap(arr, l, p); // arr[l+1...j] < v; arr[j+1...i] >= v int j = l; for (int i = l + 1; i <= r; i++) { if (arr[i].compareTo(arr[l]) < 0) { j++; swap(arr, i, j); } } swap(arr, l, j); return j; }
关键代码
// 生成[l,r] 之间的随机索引 int p = l + (new Random()).nextInt(r - l + 1); swap(arr, l, p);
结果输出
我们优化一下
完全代码
点击查看完整内容
package quicksort; import LinearSearch.ThreadDemo4; import List.Array; import MergeSort.ArrayGenerator; import MergeSort.SortingHelper; import java.util.Arrays; import java.util.Random; import java.util.concurrent.*; public class QuickSort { private QuickSort() { } public static <E extends Comparable<E>> void sort(E[] arr) { Random rnd = new Random(); sort(arr, 0, arr.length - 1, rnd); } private static <E extends Comparable<E>> void sort(E[] arr, int l, int r, Random rnd) { if (l >= r) { return; } int p = partition(arr, l, r, rnd); sort(arr, l, p - 1, rnd); sort(arr, p + 1, r, rnd); } private static <E extends Comparable<E>> int partition(E[] arr, int l, int r, Random rnd) { // 生成[l,r] 之间的随机索引 int p = l + rnd.nextInt(r - l + 1); swap(arr, l, p); // arr[l+1...j] < v; arr[j+1...i] >= v int j = l; for (int i = l + 1; i <= r; i++) { if (arr[i].compareTo(arr[l]) < 0) { j++; swap(arr, i, j); } } swap(arr, l, j); return j; } /** * 简单的数组元素交换 * * @param arr * @param i * @param j * @param <E> */ private static <E> void swap(E[] arr, int i, int j) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static void main(String[] args) { int n = 500000; Integer[] arr = ArrayGenerator.generateRandomArray(n, n); Integer[] arr2 = Arrays.copyOf(arr, arr.length); SortingHelper.sortTest("MergeSort", arr); SortingHelper.sortTest("QuickSort", arr2); Integer[] arr3 = ArrayGenerator.generateOrderedArray(n); Integer[] arr4 = Arrays.copyOf(arr3, arr3.length); SortingHelper.sortTest("MergeSort", arr3); SortingHelper.sortTest("QuickSort", arr4); } }
优化前的快速排序时间
优化后的快速排序时间
四、双路快速排序算法
原理大话解读
核心代码
public static <E extends Comparable<E>> void sort2ways(E[] arr) { Random rnd = new Random(); sort2ways(arr, 0, arr.length - 1, rnd); } private static <E extends Comparable<E>> void sort2ways(E[] arr, int l, int r, Random rnd) { if (l >= r) { return; } int p = partition2(arr, l, r, rnd); sort2ways(arr, l, p - 1, rnd); sort2ways(arr, p + 1, r, rnd); } private static <E extends Comparable<E>> int partition2(E[] arr, int l, int r, Random rnd) { // 生成[l,r] 之间的随机索引 int p = l + rnd.nextInt(r - l + 1); swap(arr, l, p); // arr[l+1...i-1] <= v; arr[j+1...r] >=v int i = l + 1, j = r; while (true) { while (i <= j && arr[i].compareTo(arr[l]) < 0) { i++; } while (j >= i && arr[j].compareTo(arr[l]) > 0) { j--; } if (i >= j) { break; } swap(arr, i, j); i++; j--; } swap(arr, l, j); return j; }
完整代码
点击查看完整内容
package quicksort; import LinearSearch.ThreadDemo4; import List.Array; import MergeSort.ArrayGenerator; import MergeSort.SortingHelper; import java.util.Arrays; import java.util.Random; import java.util.concurrent.*; public class QuickSort { private static final int CORE_POOL_SIZE = 5; private static final int MAX_POOL_SIZE = 10; private static final int QUEUE_CAPACITY = 100; private static final Long KEEP_ALIVE_TIME = 1L; private QuickSort() { } public static <E extends Comparable<E>> void sort(E[] arr) { Random rnd = new Random(); sort(arr, 0, arr.length - 1, rnd); } private static <E extends Comparable<E>> void sort(E[] arr, int l, int r, Random rnd) { if (l >= r) { return; } int p = partition(arr, l, r, rnd); sort(arr, l, p - 1, rnd); sort(arr, p + 1, r, rnd); } private static <E extends Comparable<E>> int partition(E[] arr, int l, int r, Random rnd) { // 生成[l,r] 之间的随机索引 int p = l + rnd.nextInt(r - l + 1); swap(arr, l, p); // arr[l+1...j] < v; arr[j+1...i] >= v int j = l; for (int i = l + 1; i <= r; i++) { if (arr[i].compareTo(arr[l]) < 0) { j++; swap(arr, i, j); } } swap(arr, l, j); return j; } public static <E extends Comparable<E>> void sort2ways(E[] arr) { Random rnd = new Random(); sort2ways(arr, 0, arr.length - 1, rnd); } private static <E extends Comparable<E>> void sort2ways(E[] arr, int l, int r, Random rnd) { if (l >= r) { return; } int p = partition2(arr, l, r, rnd); sort2ways(arr, l, p - 1, rnd); sort2ways(arr, p + 1, r, rnd); } private static <E extends Comparable<E>> int partition2(E[] arr, int l, int r, Random rnd) { // 生成[l,r] 之间的随机索引 int p = l + rnd.nextInt(r - l + 1); swap(arr, l, p); // arr[l+1...i-1] <= v; arr[j+1...r] >=v int i = l + 1, j = r; while (true) { while (i <= j && arr[i].compareTo(arr[l]) < 0) { i++; } while (j >= i && arr[j].compareTo(arr[l]) > 0) { j--; } if (i >= j) { break; } swap(arr, i, j); i++; j--; } swap(arr, l, j); return j; } /** * 简单的数组元素交换 * * @param arr * @param i * @param j * @param <E> */ private static <E> void swap(E[] arr, int i, int j) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static void main(String[] args) { int n = 100000; Integer[] arr = ArrayGenerator.generateRandomArray(n, n); Integer[] arr2 = Arrays.copyOf(arr, arr.length); System.out.println("乱序数组"); SortingHelper.sortTest("QuickSort", arr); SortingHelper.sortTest("QuickSort2", arr2); Integer[] arr3 = ArrayGenerator.generateOrderedArray(n); Integer[] arr4 = Arrays.copyOf(arr3, arr3.length); System.out.println("有序数组"); SortingHelper.sortTest("QuickSort", arr3); SortingHelper.sortTest("QuickSort2", arr4); System.out.println("完全一样的数组"); Integer[] arr5 = ArrayGenerator.generateRandomArray(n,1); Integer[] arr6 = Arrays.copyOf(arr5, arr5.length); SortingHelper.sortTest("QuickSort", arr5); SortingHelper.sortTest("QuickSort2", arr6); } }
结果输出
五、快速排序的复杂度分析
- 普通算法:看最差
- 能找到一组数据100%恶化
- 随机算法:看期望
- 不能找到一组数据100%恶化
- 多次调用?
- 尝试均摊分析
六、三路排序算法
先看一张图,了解我们自定义的标识
关键代码
public static <E extends Comparable<E>> void sort3ways(E[] arr) { Random rnd = new Random(); sort3ways(arr, 0, arr.length - 1, rnd); } private static <E extends Comparable<E>> void sort3ways(E[] arr, int l, int r, Random rnd) { if (l >= r) { return; } // 生成 【l,r】 之间的随机索引 int p = l + rnd.nextInt(r - l + 1); swap(arr, l, p); // arr[l+1,lt] < v,arr[lt+1,i-1] ==v,arr[gt,r]>v int lt = l, i = l + 1, gt = r + 1; while (i < gt) { if (arr[i].compareTo(arr[l]) < 0) { lt++; swap(arr, i, lt); i++; } else if (arr[i].compareTo(arr[l]) > 0) { gt--; swap(arr, i, gt); } else { //arr[i] == arr[l] i++; } } swap(arr, l, lt); // arr[l,lt-1]<v,arr[lt,gt-1]==v,arr[gt,r]>v sort3ways(arr, l, lt - 1, rnd); sort3ways(arr, gt, r, rnd); }
控制台输出
七、力扣题目——75. 颜色分类
具体题目
解析(引用慕课算法名师——波波老师)
-
- 实际上,这个问题是非常典型的,可以使用三路快速排序的partition思想解决的问题。因为,整个数组中只有0,1,2三种元素。如果我们把1当做标定点的话,就自然而然的可以把元素0当做是小于标定点的部分,元素2当做是大于标定点的部分。
- 所以,大家可以看出来,只要我们使用1当做标定点,只需要运行一遍三路快速排序的partition过程,就能完成任务了。
- 注意,在这个过程中,我们不需要随机去选择标定点了,我们已经通过对问题的分析,明确了标定点就是1.同时,我们也不需要一定把一个1放在数组的最左边。既然我们明确了标定点是1,在算法循环过程中,每个待处理的元素,直接和1进行比较就好了。
- 在下面的代码中,循环不变量的定义是:
-
-
nums[0...zero] == 0 nums[zero + 1,i - 1] == 1 nums[two,n - 1] == 2
-
- 其实,变量zero相当于我们在三路快速排序算法中的lt;变量two相当于我们在三路快速排序算法中的gt。有了这个定义,相信理解了快速排序算法的partition的逻辑。
-
具体代码
class Solution { public void sortColors(int[] nums) { // nums[0...zero] == 0,nums[zero + 1, i] == 1,num[two,n - 1] == 2 int zero = -1, i = 0, two = nums.length; while (i < two) { if (nums[i] == 0) { zero++; swap(nums, zero, i); i++; } else if (nums[i] == 2) { two--; swap(nums, i, two); } else { // nums[i] == 0; i++; } } } private void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } }
可以看到是没有问题的
八、经典selectK题目
我们首先来封装一个selectK的方法。我们的selectK的接口是这样的
// 在arr[l...r] 的范围里求解整个数组的第k小元素并返回 // k 是索引,即从0开始计算 int selectK(int[] arr,int l,int r,int k,Random rnd)
- 因为我们的partition 过程需要随机选取标定点,所以我们还需要传一个Random 类的对象rnd。
- 定义好函数签名以后,下面我们来书写相应的逻辑
- 首先,selectK的过程,我们就是要执行一遍partition,在这个,我们使用双路快速排序的partition。
- 注意,因为在这个问题中,我们肯定我们处理的数据类型是int,所以,在代码中,我们将不再使用泛型:
private int partition(int[] arr, int l, int r, Random rnd) { // 生成[l,r] 之间的随机索引 int p = l + rnd.nextInt(r - l + 1); swap(arr, l, p); //arr[l+1...i-1] <= v; arr[j+1...r] >= v int i = l + 1, j = r; while (true) { while (i <= j && arr[i] < arr[l]) { i++; } while (j >= i && arr[j] > arr[l]) { j--; } if (i >= j) { break; } swap(arr, i, j); i++; j--; } swap(arr, l, j); return j; } private void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
- 有了partition,我们的selectK的主题逻辑非常简单。
- 首先,进行partition,假设结果是p,我们只需要将k和p作比较。
- 如果k==p,直接返回arr[p]即可。
- 如果k<p,在arr[l,p-1]的范围继续找,即调用selectK(arr,l,p-1,k,rnd);
- 如果k>p,在arr[p+1,r]的范围继续找,即调用selectK(arr,p+1,r,k,rnd);
关键selectK代码
private int selectK(int[] arr, int l, int r, int k, Random rnd) { int p = partition(arr, l, r, rnd); if (k == p) { return arr[p]; } if (k < p) { return selectK(arr, l, p - 1, k, rnd); } return selectK(arr, p + 1, r, k, rnd); }
我们来看下面这题——力扣215题
public int findKthLargest(int[] nums, int k) { Random rnd = new Random(); return selectK(nums, 0, nums.length - 1, nums.length - k, rnd); }
完整代码
点击查看完整内容
package solution3; import java.util.Random; class Solution { public int findKthLargest(int[] nums, int k) { Random rnd = new Random(); return selectK(nums, 0, nums.length - 1, nums.length - k, rnd); } private int selectK(int[] arr, int l, int r, int k, Random rnd) { int p = partition(arr, l, r, rnd); if (k == p) { return arr[p]; } if (k < p) { return selectK(arr, l, p - 1, k, rnd); } return selectK(arr, p + 1, r, k, rnd); } private int partition(int[] arr, int l, int r, Random rnd) { // 生成[l,r] 之间的随机索引 int p = l + rnd.nextInt(r - l + 1); swap(arr, l, p); //arr[l+1...i-1] <= v; arr[j+1...r] >= v int i = l + 1, j = r; while (true) { while (i <= j && arr[i] < arr[l]) { i++; } while (j >= i && arr[j] > arr[l]) { j--; } if (i >= j) { break; } swap(arr, i, j); i++; j--; } swap(arr, l, j); return j; } private void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } }
输出结果
我们再来看一题,《剑指offer》——40题
public int[] getLeastNumbers(int[] arr, int k) { if (k == 0) { return new int[0]; } Random rnd = new Random(); selectK(arr, 0, arr.length - 1, k - 1, rnd); return Arrays.copyOf(arr, k); }
结果输出
本文作者为DBC,转载请注明。