快速排序

定义

快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列；

示例

下面我们举个例子，来图解快速排序的过程；假如有一个数组[6,8,5,9,3,7]，下面我们就对这个数组进行快速排序；

图1

快速排序的第一步，要确定三个值
起始点：left 0（数组起始点）
终点：right 5 (数组结束点)
基准数： key 6 （一般取数组的第一个数）
确定了这三个值，就开始根据基准数进行遍历排序了；
首先从右边right开始寻找比基础数小的数值；
第一次比较：

第一次比较

7>6 right指针左移，继续寻找
第二次比较

第二次比较
绿色块表示已经排过序；
6>3 满足条件 6和3交换位置 left指针右移
交换后的数组
比较后
然后从left指针开始，寻找比基准数大的值；
第三次比较
8>6 满足条件，6和8位置交换，right指针左移
交换后数组：
交换后

然后再从right指针开始，寻找比基准数小的值;

第四次比较

6<9不满足条件，right指针左移，继续比较

第五次比较

6>5，满足条件 ，5和6交换位置，left指针右移
交换后的数组

交换后

交换后发现left和right指针碰头了，即left==right，这时第一轮排序完成，排序完成后的数组为：

第一轮排序完成

可以看到第一轮排序完成后 基准数左边的都比基准数小，右边的都比基准数大，接下来我们只需要继续对left区域和right区域重复以上的排序过程，直到无法再拆分，即left和right区域只剩一个元素时，排序完成；

我们来简述一下整个排序的过程：
1、首先确定基准数，一般为数组的第一个元素，起始点和终点；
2、从终点（right）开始寻找比基准数小的值，如果找到和基准数交换位置；
3、然后从起点（left）开始寻找比基准数大的值，如果找到和基准数交换位置；
4、如此反复（2，3），直到起点和终点碰头（left==right）第一轮比较完成，确定两个区域（left和right） left区都比基准数小，right区都比基准数大；
5、对left和right区重复（1,2,3,4），直到数组不能再拆分，排序完成；

说了这么多，开始撸代码；

public class QuickSort {

    public static void quickSort(int[] array, int start, int end) {

        int left = start;
        int right = end;

        if (left < right) {//保证array至少有两个元素

            int key = array[left];//将数组的起始值付给基准数

            while (left != right) {//结束条件为 left==right

                while (right > left && array[right] >= key)//首先从右边开始寻找比基准数小的值
                    right--;

                array[left] = array[right];//找到后和基准数交换位置

                while (left < right && array[left] <= key)//然后从左边开始寻找比基准数大的值
                    left++;

                array[right] = array[left];//找到后和基准数交换位置
            }

            array[right] = key;//基准数归位 一轮排序完成

            quickSort(array, start, left - 1);//对基准数左侧数据重复以上排序（递归）

            quickSort(array, right + 1, end);//对基准数右侧数据重复以上排序（递归）
        }
    }
}

在主程序中运行测试

private void quickSort() {
        
        int[] a = {6, 8, 5, 9, 3, 7};

        QuickSort.quickSort(a, 0, a.length - 1);

        for (int i = 0; i < a.length; i++) {
            System.out.println("排序后 a[" + i + "] = " + a[i]);
        }

    }

测试结果：

测试结果

ok，快速排序搞定！