快速排序

1. 算法思想

   每次选择一个数作为基数（一般都选第一个数），将所有比这个数大的放在这个数的右边，比它小的放左边

   对新产生的两个序列分别按上诉方法再次拆分

2. 对于 3 7 2 6 1 4 5 这个序列

• 选择第一个数 3 作为基数， 用两个指针实现把比基数大的移到右边，比基础小的移到左边。

• (1)要先动 high指针，5 > 3 不用移动，所以 high–， 此时 4 > 3 high – , 1 < 3

  就令 array[low] = array[high] （low 此时在 0 处）跳到2

• (2)再动 low 指针，1 < 3 所以 low++， 7 >3 所以 令array[high] = array[low],返回1

/**
 * 快速排序
 * 每次选择一个数作为基数（一般都选第一个数），将所有比这个数大的放在这个数的右边，比它小的放左边
 * 对新产生的两个序列分别按上诉方法再次拆分
 */

/**
 *    对于 3 7 2 6 1 4 5 这个序列
 *    选择第一个数 3 作为基数， 用两个指针实现把比基数大的移到右边，比基础小的移到左边。
 *    (1)要先动 high指针，5 > 3 不用移动，所以 high--， 此时 4 > 3 high -- , 1 < 3
 *       就令 array[low] = array[high] （low 此时在 0 处）跳到2
 *    (2)再动 low 指针，1 < 3 所以 low++， 7 >3 所以 令array[high] = array[low],返回1
 *       上诉过程就是 3 7 2 6 1 4 5 ——>  1 7 2 6 1 4 5 (low = 0， high = 4) ->
 *       1 7 2 6 7 4 5(low = 1 high = 4) -> 1 2 2 6 7 4 5 (low = 1, high = 2) ->
 *       1 2 2 6 7 4 5(low = 2, high = 2)
 *       最后令array[low] = base;
 *
 *
 */
public static void quick(int[] array, int high, int low) {
    if (low < high) {
        int base = part(array, high, low);
        quick(array, base - 1, low);
        quick(array, high, base + 1);
    }
}
public static int part (int[] array, int high, int low) {
    // 选择第一个数作为基准数并定义base存放
    int base = array[low];
    while (low < high) {
        while (low < high && array[high] > base) {
            high--;
        } // 找到比 base 小的数退出循环，再进行赋值
        array[low] = array[high];
        while (low < high && array[low] < base) {
            low++;
        }
        array[high] = array[low];
    }
    array[high] = base;
    return high;
}