快速排序

从大二开始,就没写过任何算法相关的东西了,数据结构也只是知道一个大概而已。最近在看《Thinking in Java》,看到集合一章的时候,书中使用到了快速排序。我一直在自嘲不会手写快排,不会翻转二叉树,今天就顺便看了下快排的思想。

初步

对于一个数组(简化为整数数组):

  1. 任选其中一个作为轴点(简化选择最后一个值)。
  2. 然后从两端用两个指针(L,R)进行遍历:

    • L指针从左侧开始遍历,如果指向的数值不小于轴点,则停止。
    • R指针开始从右侧遍历,如果指向的数值不大于轴点,则停止。
    • 交换LR指针所指向的值,LR指针继续移动。
    • 直至LR指针相遇
  3. LR指针指向同一点,交换此值与轴点。此时,此点左侧(L遍历过的)所有的值均小于此点,右侧(R遍历过的)所有的值均大于此点。
  4. 把此点左右分别进行递归快排。

实现

    private static void quickSort(int[] arrays, int start, int end) {
        //先判断是否已经不需要排序
        if (end > start) {
            //找到轴点
            int pivot = arrays[end];
            int l = start;
            int r = end - 1;
            while (l < r) {
                //从左边开始遍历,直到左边某个数不小于轴点
                while (arrays[l] < pivot && l < r) {
                    l++;
                }
                //从右边开始遍历,直到右边某个数不大于轴点
                while (arrays[r] > pivot && r > l) {
                    r--;
                }
                //此时l指向的值不小于轴点,r指向的值不大于轴点
                swap(arrays, l, r);
            }
            swap(arrays, l, end);
            quickSort(arrays, start, l - 1);
            quickSort(arrays, l + 1, end);
        }
    }

换种方式

再次把思路简化一下:

  1. 任选其中一个作为轴点。
  2. 搞个大动作,把轴点移动(交换到中间),使这个轴点左边的值均小于此点,右边的值都大于此点。
  3. 把此点左右分别进行递归快排。

伪实现

    private static void quickSort2(int[] arrays, int start, int end) {
        if (end > start) {
            //确定轴点
            int pivot = doBigThing(arrays, start, end);
            quickSort2(arrays, start, pivot - 1);
            quickSort2(arrays, pivot + 1, end);
        }
    }

具体细节

依旧可以像上面那样两个指针LR,分别从左和从右开始遍历,直至相遇。
也可以这样:

  1. 用两个指针,一前一后进行遍历。
  2. 保证其中一个指针L左侧所有的值都小于等于轴点,所在点大于轴点。
  3. 另外一个指针P则由L向右移动,当P指向的值小于轴点时,交换LP所指向的值。
  4. L向前移动,P也继续向前移动。
  5. 直至P移动到最后一位。
  6. 此时L点左侧都小于轴点,右侧都大于轴点(因为P遍历过,如果存在小于轴点的点,早就交换位置了)。

具体实现

    static int partition(int[] arrays, int start, int end) {
        int l = start;
        int pivot = arrays[end];
        for (int p = start; p < end; p++) {
            if (arrays[p] < pivot) {
                swap(arrays, p, l);
                l++;
            }
        }
        swap(arrays, l, end);
        return l;
    }