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的性能也会很差。