小橙书阅读指南（六）——快速排序和三向切分快速排序

算法描述：快速排序是一种分治的排序算法。它将数组分为两个子数组，并将两部分独立的排列。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。

算法图示：

算法解释：选择标的元素（5）并且便利数组，将素有小于5的元素都安排在它的左侧，而大于5的元素都安排在它的右侧。之后再通过递归的方法分别处理左边的子数组和右边的子数组。

快速排序的算法难点在于尽量不要使用额外的存储空间（即保证原地切分）以及如何处理与标的元素（5）相等的元素。

Java代码示例：

package algorithms.sorting;

import algorithms.Sortable;
import algorithms.common.Arrays;
import algorithms.common.ArraysGenerator;

/**
 * Created by learnhow on 2018/8/17.
 */
public class Quick extends Arrays<Integer> implements Sortable<Integer> {
    @Override
    public void sort(Integer[] array) {
        sort(array, 0, array.length - 1);
    }

    // 递归体
    private void sort(Integer[] array, int lo, int hi) {
        if (lo >= hi) {
            return;
        }

        int part = partition(array, lo, hi);
        sort(array, lo, part - 1);
        sort(array, part + 1, hi);
    }

    // 切分算法
    private int partition(Integer[] array, int lo, int hi) {
        // 限制数组的遍历范围 array(lo, hi];
        int i = lo;
        int j = hi + 1;
        int temp = array[lo];
        while (true) {
            while (array[++i] < temp) {
                if (i == hi) {
                    break;
                }
            }
            while (array[--j] > temp) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            exchange(array, i, j);
        }
        exchange(array, lo, j);
        return j;
    }

    public static void main(String[] args) {
        Integer[] arr = ArraysGenerator.generate(10, 0, 10);
        Quick quick = new Quick();
        quick.sort(arr);

        System.out.println(java.util.Arrays.toString(arr));
    }
}

Qt/C++代码示例：

void Quick::sort(int *arr, int lo, int hi)
{
    if (lo >= hi) {
        return;
    }
    int part = partition(arr, lo, hi);
    sort(arr, lo, part - 1);
    sort(arr, part + 1, hi);
}

int Quick::partition(int *arr, int lo, int hi)
{
    int i = lo;
    int j = hi + 1;
    int targetValue = arr[lo];
    while (true) {
        while (arr[++i] < targetValue) {
            if (i == hi) {
                break;
            }
        }
        while (arr[--j] > targetValue) {
            if (j == lo) {
                break;
            }
        }
        if (i >= j) {
            break;
        }
        // 交换元素位置
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    int temp = arr[lo];
    arr[lo] = arr[j];
    arr[j] = temp;

    return j;
}

算法性能分析：

快速排序速度优势子啊与它的比较次数很少，但是排序效果还是依赖切分数组的情况，并且如果在数组中存在大量重复元素。算法性能还可以大幅度提升。下面我们给出三向切分的快速排序算法。大家作为了解即可。

算法图示：

算法解释：在三向切分快速排序算法中我们定义了三个指针变量：gt 小于 V 的数组的上界，i 等于 V 的数组的上界，gt 大于 V 的数组的下界。以及一段中间数组array[i, gt]。一次遍历的判断过程如下：

array[i]小于V，将array[lt]和array[i]交换，并将lt和i分别加1；
array[i]大于V，将array[gt]和array[i]交换，并将gt减1；
array[i]等于V，将i单独加1；

Java代码示例：

package algorithms.sorting;

import algorithms.Sortable;
import algorithms.common.Arrays;
import algorithms.common.ArraysGenerator;

public class Quick3way extends Arrays<Integer> implements Sortable<Integer> {
    @Override
    public void sort(Integer[] array) {
        sort(array, 0, array.length - 1);
    }

    private void sort(Integer[] array, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int temp = array[lo]; // 比较标的
        int lt = lo; // 小于temp的index记录
        int eq = lo + 1; // 等于temp的index记录
        int gt = hi; // 大于temp的index记录

        while (eq <= gt) {
            if (array[eq] < temp) {
                exchange(array, lt++, eq++);
            } else if (array[eq] > temp) {
                exchange(array, eq, gt--);
            } else {
                eq++;
            }
        }
        sort(array, lo, lt - 1);
        sort(array, gt + 1, hi);
    }

    public static void main(String[] args) {
        Integer[] arr = ArraysGenerator.generate(10, 0, 10);
        Quick3way quick3way = new Quick3way();
        quick3way.sort(arr);

        System.out.println(java.util.Arrays.toString(arr));
    }
}

Qt/C++代码示例（略）

三向切分快速排序针对特定数组能够起到非常优秀的效果，但是在处理下标越界的事情往往容易弄错。因此在考虑算法性能的同时，保证正确应该优先考虑。