第三周下:QuickSort
2020-03-28 本文已影响0人
Lynn_4f26
Java sort for primitive types
1. Quicksort
-
思路:
- 打乱array中的item顺序(用来保障Performance)
- 锚定一个item,比如第一个a[lo],比它大的都去右边,比它小的都去左边
- i pointer:从左到右扫,直到a[i] > a[lo]时停下
- J pointer:从右到左扫,直到a[j] < a[lo]时停下
- 交换a[i]和a[j]
- 全部结束后(i>=j),交换a[lo]和a[j]
- 递归地将所有排好
-
Performance
- best case:~ compares
- worst case: ~ compares
- Average: ~ compares,~
- Compares 比 merge sort 多39%
- 但因为更少的data movement,所以比merge sort要快
-
Stability
- Quicksort is not stable
-
Java implementation
import edu.princeton.cs.algs4.StdRandom; public class Quick{ private static int partition(Comparable[] a, int lo, int hi){ int i = lo; int j = hi + 1; while(true){ // 找到比a[lo]大的a[i] while(less(a[++i], a[lo])){ if(i == hi){ break; } } // 找到比a[lo]小的a[j] while(less(a[lo], a[--j])){ if(j == lo){ break; }_ } // 检查i,j是否已经跨过彼此(即i>=j),是的话就结束 if(i >=j){ break; } // 交换a[i],a[j] exch(a, i, j); } // 狡猾a[lo],a[j] exch(a, lo, j); // 返回j,代表已经排好的item所在的index return j; } public static void sort(Comparable[] a){ // shuffle让performance至少大概率不会在worst case StdRandom.shuffle(a); sort(a, 0, a.length-1); } private static void sort(Comparable[] a, int lo, int hi){ // 递归地终止条件 if(hi <= lo){ return; } // 优化1:对于比较小的array(定cutoff=10),用quick sort太浪费memory,改用insertion sort int cutoff = 7; if(hi <= lo+cutoff - 1){ Insertion.sort(a); // Insertion.java与Merge.java放在同一个目录下 return; } // 结束优化1 // 优化2:不再随意地直接选第一个item,即a[lo]来锚定,而选用a[lo], a[hi], a[(lo+hi)/2]中的median int m = medianOf3(a, lo, (lo+hi)/2, hi); exch(a, lo, m); // 结束优化2 int j = partition(a, lo, hi); sort(a, lo, j-1); sort(a, j+1, hi); } // item v,w比较大小 private static boolean less(Comparable v, Comparable w){ return v.compareTo(w) < 0 } // a[i]和a[j]交换位置 private static void exch(Comparable[] a, int i, int j){ Comparable swap = a[i]; a[i] = a[j]; a[j] = swap; } private static int medianOf3(Comparable[] a, int lo, int md, int hi){ int[] arr3 = new int[]; arr3[0] = a[lo]; arr3[1] = a[md]; arr3[2] = a[hi]; Insertion.sort(arr3); return } }
2. Selection
- 目标:给定一个array(有n个items),找到第k个最小的item
- 思路:
- 找到合适的a[j],它的左边都比它小,右边都比它大
- 根据j,在一个subarray中重复,直到找到j=k
- (代码见上方)
- Performance
- on average:take linear time,~ compares
- worst case:~ compares (但已经靠random shuffle来提供一个probabilistic guarantee了)
3. Duplicate keys
-
Quicksort问题:
- 遇到和锚定的item相同时,会将相同的item都放在锚定的item的一边,这样是很没效率的。因为,当所有key全部相同时,需要比较$\frac{1}{2}N^2$次。我们希望,它在遇到相同的item时就能停下来,不改变这个item的位置。这样当所有key都相同时,只需比较
-
思路(3-way partitioning):
-
锚定item v,比如选第一个item a[lo]。
-
与v相同的都放在lt和gt之间,lt左边的item都小于v,gt*右边的item都大于v
- 当a[i] < v时,a[lt]和a[i]交换,lt和i都+1
- 当a[i] > v时,a[gt]和a[i]交换,gt-1
- 当a[i] == v时,i+1
-
-
Java implementation
import edu.princeton.cs.algs4.StdRandom; public class Quick3Way{ public static void sort(Comparable[] a){ // shuffle让performance至少大概率不会在worst case StdRandom.shuffle(a); sort(a, 0, a.length-1); } private static void sort(Comparable[] a, int lo, int hi){ int lt = lo; int gt = hi; int i = lo; Comparable v = a[lo]; if(hi <= lo){ return; } while(i <= gt){ int cmp = a[i].compareTo(v); if(cmp < 0){ // a[i] < v exch(a, lt++, i++); }else if(cmp > 0){ // a[i] > v exch(a, i, gt--); }else{ i++; } } sort(a, lo, lt-1); sort(a, lt+1, hi); } // a[i]和a[j]交换位置 private static void exch(Comparable[] a, int i, int j){ Comparable swap = a[i]; a[i] = a[j]; a[j] = swap; } }
4. System sorts
-
Java system sorts:
Array.sort()
- 遇到Reference types: 用merge sort。优点:稳定,保证 的compares
- 遇到primitive types:用quick sort。优点:占用更少的memory,更快
import java.util.Arrays import edu.princeton.cs.algs4.StdIn; import edu.princeton.cs.algs4.StdOut; public class StringSort{ public static void main(String args){ String[] a = StdIn.readString(); Array.sort(a); for(int i = 0; i < a.length; i++){ StdOut.println(a[i]); } } }