排序算法之--快速排序

今天来整理一下快速排序。

快速排序采用分治策略对数据进行排序，什么是分治策略呢？简单地说就是“分而治之，各个击破”。啥意思呢？且听我慢慢道来：

假设现在给你一个数组int[] arr = {6, 2, 4, 9, 3, 10}，选择一个基准数（这个可以随便选，为了方便一般选择第一个元素为基准数）pivot = arr[0] = 6;将大于基准数pivot的元素放在pivot右侧，小于pivot的元素放在pivot左侧；这样基准值就处在它应该处在的位置了；然后对基准值左右两侧的子数组再选取基准值进行一轮如上的操作，这样不断的将数组一份为二，每一次都“安顿”好一个数值（基准值），最后一定能够将整个数组排序（“安顿”）好。

现在把上面的叙述抽象成步骤：

1. 从数组中挑选一个基准值，并设置i = 0， j = a.length - 1;
2. 先从右往左寻找比基准值小的值，再从左往右寻找比基准值大的值，交换它们；重复此步骤，直到 i 和 j 相遇
3. 将基准值和a[i]交换以完成归位
4. 递归地把"基准值前面的子数组"和"基准值后面的子数组"进行步骤1，2，3

针对上面的步骤有几点说明：

• 基准值一般选择当前数组的第一个元素，这样做是为了代码实现方便，更好理解
• 对于和基准值相等的数值放在左边或右边都可以，同时这也是快速排序不稳定的原因
• 经过步骤2后我们就把基准值“安顿”好了
• 步骤3所谓递归，其实就是不断地把基准值“安顿”好

说的再好都不如图来的畅快：

实现代码如下：

public class TestSort {
    public static void main(String[] args) {
        int[] arr = {12333, 34, 2, 1, 3, 5, 64, 2, 9, 12, 4, 8};
        quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    /*
         arr:   待排序数组
         left:  排序起始位置
         right: 排序终止位置
     */
    private static void quickSort(int[] arr, int left, int right) {
        if (left > right || arr == null || arr.length == 0) {
            return;
        }
        int pivot = arr[left];//以左边界的值为基准
        int i = left;
        int j = right;//使用局部变量接收参数

        while (i != j) { //当i = j时表示已经排序好（即基准点左侧都小于基准点，基准点右侧都大于基准点）
            while (arr[j] >= pivot && i < j) { //从右往左找小于基准点的数
                j--;
            }
            while (arr[i] <= pivot && i < j) { //从左往右找大于基准点的数
                i++;
            }
            if (i < j) { //寻找到的大于/小于基准点的下标还没有相遇，交换两个的位置
                swap(arr, i, j);
            }
        }
        //代码到这，即表示 i, j 已经相遇了

        //将基准数归位
        swap(arr, left, i);

        quickSort(arr, left, i - 1);//递归对左侧子数组排序
        quickSort(arr, i + 1, right);//递归对右侧子数组排序

    }
    //交换数组arr中下标from和to的元素
    private static void swap(int[] arr, int from, int to) {
        if (from < 0 || from >= arr.length || to < 0 || to >= arr.length) return;
        int tmp = arr[from];
        arr[from] = arr[to];
        arr[to] = tmp;
    }

}