手写快速排序

Publish Date: 2020-04-18

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序算法是冒泡排序的一种改进，在面试中经常会有排序算法题，快速排序是高频的算法考查点。

算法思想

快速排序属于分治思想，即把原数组按一定的规则划分为两个部分，然后再以同样的规则继续划分这两个部分，直到不能再划分为止。那为什么使用二分法把数组分为两个部分，而不使用三分法把数组分成三个部分呢。二分法相比于三分法思路更清晰简单。而且就算法复杂度而言，三分法也没什么优势。算法步骤也很简单，我总结分为四步

选基准数：在数组中随机选择一个数字作为基准数。不要被基准数这个名词吓到，说白了就是在数组中随便选一个数，我们把它叫做基准数。一般的我们就选择数组的第一个元素作为基准数。
比较交换：设置两个游标，一个游标从数组的右边左走，遇到比基准数小的就停下，另一个游标从数组的左边往右走，遇到比基准数大的就停下，然后交换这个数字的位置。重复步骤2，直到两个游标相遇时进入步骤3（其实就是在用两个游标遍历数组，最终目的就是把数组中大于基准数的数字放数组右边，把小于基准数的数字放数组左边）
校准中轴：步骤2中两个游标相遇的点，我们称之为中轴。这一步我们要做的就是把基准数和中轴点所在的数字交换位置。（因为中轴的位置和基准数的位置不一定会重合，经过步骤2后，我们需要保证数组被分为的两部分左边的比基本数小，右边的比基准数大，这必须把基准数和中轴数位置交换。这是整个快速排序的关键步骤）
递归快排：经过步骤3后，数组的两个部分已经划分完毕，只需以同样的方式，继续划分这个两个部分即可

算法图解

这里以一个具体的实例来图解算法过程吧，假设有一个数组 int[] array = {3,1,4,7,5,2,8,9,6} ，用快速排序进行排序。

第一次递归

第一次递归的数组是原始数组，我们选择数组的第一个元素3作为基准数

首先哨兵j开始出动。一定需要让哨兵j先出动，这一点非常重要（也是算法实现的一个细节点，如果不是左边的哨兵先动，最后无法完成排序）。哨兵j一步一步地向左挪动（即j--），直到找到一个小于3的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于3的数停下来。最后哨兵j停在了数字2上，哨兵i停在了数字4上。

然后交换4和2的位置。交换后数组的序列顺序如下

到此，第一次交换结束。接下来开始哨兵j继续向左挪动。这时移动到2数字上时，哨兵j发现了2比3小于是停下。然后i往右移。正当哨兵i准备右移时，他发现哨兵j就在2上，他们两个相遇了。

至此第一次递归结束，这时我们可以看到中轴数是2，中轴数的右边全都比基准数3大，中轴数的左边除了3都比基准数小。这是需要校准中轴了，即把中轴数和基准数交换位置，交换位置后，数组序列如下

第二次递归

经过第一次递归后，原始数组被划分为两个数组，分别是 [2,1] 和 [7,5,4,8,9,6]。以第二个数组为例。

后面的就不说了，和前面的步骤一样。

Java代码实现

package com.example.sort;

/**
 * @Auther: Lushunjian
 * @Date: 2020/4/18 14:07
 * @Description:
 */
public class SortTest {

    public static void main(String[] args){
        int[] array = {3,1,4,7,5,2,8,9,6};
        quickSort(array,0,array.length-1);
        for (int item : array) {
            System.out.println(item);
        }
    }

    /**
     * 快速排序
     * */
    public static void quickSort(int[] arr,int start,int end){
        if(start>end){
            return;
        }
        int low = start;
        int height = end;
        // 基准数
        int base = arr[low];

        while (start<end){
            // 注意点
            // 1.必须从数组的右边先开始
            // 2.与基准数比较时必须是>=或<=，不能只是>或<
            while (arr[end]>=base && start<end)
                end--;

            while (arr[start]<=base && start<end)
                start++;

            // 左边找到一个比基准数大的，右边找到一个比基准数小的。两个数交换位置
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }

        // 找完一轮后，将轴中数与基准数交换位置（目的是保证基准数始终处于交换轴的位置）
        arr[low] = arr[start];
        arr[start] = base;

        // 左右两个数组继续递归快排
        quickSort(arr,low,start-1);
        quickSort(arr,start+1,height);
    }
}