《算法 第四版》算法7--快速排序

快速排序

-描述：
快速排序是一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立地排序。
分治法的基本思想是：将原问题分解为若干个规模更小但是结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

-步骤：

1. 从数列中挑出一个元素，称为“基准”。
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以放到任一边）。
3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

-Java语言：

public class Quick{
  public static void sort(Comparable[] a){
    StdRandom.shuffle(a);        //消除对输入的依赖
    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);                     //将左半部分a[lo...j-1]排序
    sort(a, j+1, hi);                      //将有半部分a[j+1....hi]排序
  }
  // 切分
  private static int partition(Comparable[] a, int lo, int hi){
    int i = lo, j = hi +1;
    Comparable v = a[lo];
     while (true){
        while (less(a[++i], v)) if (i == hi) break;
        while (less(v, a[--j])) if (j == lo) break;
        if (i >=j) break;
        exch(a, i, j);
    }
    exch(a, lo, j);        
    return j;
  } 
}

快速排序轨迹

sort()方法的关键在于切分，这个过程使数组满足下面三个条件：

• 对于某个j， a[j]已经排定；
• a[lo] 到a[j-1]中所有元素都不大于a[j]；
• a[j+1]到a[hi]中的所有元素都不小于a[j];

切分方法partition(),一般的策略是先随意的取a[lo]作为切分元素，即那个将会被排定的袁术，然后我们从数组的左端开始想右扫描直到找到一个大于等于它的元素，再从数组的右端开始向左扫描直到找到一个小于等于它的元素。这两个元素显然是没有排定的，因此我们交换它们的位置。如此继续，我们就可以保证左指针i的左侧元素都不大于切分元素，右指针j的右侧元素都是不小于切分元素，当两个指针相遇时，我们只需要将切分元素a[lo]和左子数组最右侧的元素（a[j]）交换然后返回j即可。

切分 切分轨迹

简而言之：（我的理解）

1. 首先取数组的第一个元素作为切分的基准。
2. 把不大于这个元素的放到左边。
3. 把不小于这个元素的放到右边。
4. 把左边，右边的一段数据重复1,2,3步骤。（因为此时，左边的元素只是保证是小于基准的，还不是有序的，所以还需要在切分排序。右边同理。）