Quick Sort
今天学习quick sort，quick sort的基本思想是有一个数组，先shuffle以后，保证数组的item位置是均匀分布的，选择一个item然后，把所有比这个item大的放在item右边，所有比这个item小的放在左右，然后递归的进行这个操作，如下图所示
这里面的partition部分如何实现呢？首先定义两个指针i和j ，i = lo +1，j = hi，然后i从左到右的扫描数组如果less（a[i],a[lo]）, j从右到左的扫描数组如果less（a[lo],a[j]）, 然后交换a[i]和a[j]，重复这个过程直到指针i和指针j交叉。下面是partition方法的java implementation
public class QuickSort{ private static int partition(Comparable[] a, int lo, int hi){ int i = lo, j = hi + 1; while(True){ while(less(a[++i], a[lo])){ if(i == hi)break; } while(less(a[lo],a[--j])){ if(j == lo)break; } if(i >= j) break; exch(a, i, j); } exch(a, lo, j); return j; } }
下图是整个partition过程
接下来是quick sort的完整的java implementation
public class QuickSort{ public static void sort(Comparable[] a){ shuffle(a)； // 这里是为了让数组的item是均匀分布，是为了保证quick // sort的性能 sort(a, 0, a.length-1); } private static void sort(Comparable[] a, int lo, int hi){ if(hi <= lo){return;} int j = partition(a, lo, hi); sort(a, lo, j-1); sort(a, j+1, hi); } }
quick sort是in place的，他不需要额外的空间。在最好的情况下 quick sort的比较次数是正比于$NlgN$, 而在最坏的情况下是正比于$N^2$的.
我们可以分析一下在平均情况下的性能，下面是一个简单的证明过程。
在实际使用的时候，quick sort是非常有用的，因为比较次数是二次幂的情况是非常罕见的，它比merge sort要多大约百分之39的比较次数，但是在实际中quick sort要更快， 因为少了数据的移动。shuffle操作可以防止最坏的例子，但是如果当我们要排序的item的key是正序或者逆序或者是有很多相同的key，quick sort的性能也会很差。