快速排序

快速排序理解起来有一下难度，代码逻辑也稍显复杂。当面对这样的问题的时候该怎么处理呢？
大家知道古人在学习的时候都是文言文，就是各种之乎者也，而且古人的文章是没有标点符号的，也就是说他们学习起来的难度其实更大，没有上过学的人真的是连识文断字的能力都没有。那么古人在这种教育环境下，当古人对着他们的老师说，报告老师，这篇文章我看不懂的时候，老师是怎么回答的呢---书读百遍，其义自现。
没错，老师绝对不是在忽悠学生，更不是因懒惰而不肯教学生。实在是这是一句真理。
智商比较高的同学请不要站起来反驳。
言归正传

快速排序，听这个名字就能想到它排序速度快，它是一种原地排序。其基本思想是随机找出一个数（通常就拿数组第一个数据就行），把它插入一个位置，使得它左边的数都比它小，它右边的数据都比它大，这样就将一个数组分成了两个子数组，然后再按照同样的方法把子数组再分成更小的子数组，直到不能分解为止。 它也是分治思想的一个经典实验（归并排序也是）

快速排序算法过程

下面通过一个例子介绍快速排序算法的思想，假设要对数组a[10]={6，1，2，7，9，3，4，5，10，8}进行排序，首先要在数组中选择一个数作为基准值，这个数可以随意选择，在这里，我们选择数组的第一个元素a[0]=6作为基准值，接下来，我们需要把数组中小于6的数放在左边，大于6的数放在右边，怎么实现呢？

我们设置两个“哨兵”，记为“哨兵i”和“哨兵j”，他们分别指向数组的第一个元素和最后一个元素，即i=0，j=8。首先哨兵j开始出动，哨兵j一步一步地向左挪动（即j–-），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。

即将开始查询

哨兵分别停在5和7上面，并且进行交换

交换完成

第二次的查询交换

第一轮查询交换结束

快速排序其实是建立在冒泡排序之上的，可以理解为冒泡排序的优化。
冒泡排序的特点是每次都比较相邻的两个数字，每次位置互换，也只能换一个跨度。 快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。

快速排序代码

    /**
     * 快速排序算法
     */
    public void quickSort(int[] list, int left, int right) {
        if (left < right) {
            // 分割数组，找到分割点
            int point = partition(list, left, right);

            // 递归调用，对左子数组进行快速排序
            quickSort(list, left, point - 1);
            // 递归调用，对右子数组进行快速排序
            quickSort(list, point + 1, right);
        }

    }

    /**
     * 分割数组，找到分割点
     */
    private int partition(int[] list, int left, int right) {
        // 用数组的第一个元素作为基准数
        int first = list[left];
        while (left < right) {
            while (left < right && list[right] >= first) {
                right--;
            }
            // 交换
            swap(list, left, right);

            while (left < right && list[left] <= first) {
                left++;
            }
            // 交换
            swap(list, left, right);
        }
        // 返回分割点所在的位置
        return left;
    }

    /**
     * 交换数组中两个位置的元素
     */
    private void swap(int[] list, int left, int right) {
        int temp;
        if (list != null && list.length > 0) {
            temp = list[left];
            list[left] = list[right];
            list[right] = temp;
        }
    }

快速排序思考：
在上文中的查询过程，为什么每次的查询都从哨兵j开始？