计算机入门必备算法——快速排序法

1、引言

今天的运气不是很好，再加上项目的压力。准备停止学习一周，等把项目这一关过了，再继续深入学习分享算法。后来吧今天遇到的事情都比较郁闷，也无心情继续开发项目。便想转移一下注意力，继续学习快速排序算法的内容。

昨天了解了递归的使用原理。今天可以使用这个新技能来解决一个新的问题————快速排序。快速排序是一种排序算法，这个算法比前天学习的选择排序要快得多，实属优雅代码的典范。

2、快速排序

2.1 学习准备

这里讲解一个比较著名的递归式问题解决方法————分而治之（divide and comquer，D&C)。为了方便理解，还是使用一个示例给大家讲解一下这是个什么样的使用原理。

给定一个数字数组arr=[2,4,6],我们可以将这些数字相加并返回结果，使用循环其实可以很容易得出结论（具体代码可以自行来敲哦！可以粘到留言板我帮你检查哦~）,那么如何使用递归函数解决这个需求呢？

这里给出一种思路实现：

1、找出基线条件

我们首先考虑最简单的数组是什么样的？一种是空数组或者数组中只有一个元素，这完全可以直接计算出来，结果要么就是null或者就是这个元素的值。计算总和非常容易，这就是我们需要找的基线条件（不明白基线条件可以看昨天的文章哦）。

2、缩小数组

我们需要算出这个数组的和，其实可以表示为sum([2,4,6]),那么如何缩小数组的规模呢？那么sum([2,4,6])=2+sum([4,6]) = 2 + 4 + sum([6])(达到基线条件) = 2+4+6=12。

3、函数的运行过程

下图解释了函数是如何运行的，递归保存了运行的状态！

运行过程

运行状态

2.2 快速排序的原理

使用快速排序算法对数组进行排序，首先考虑对于排序算法而言，最简单的数组上面介绍要么是空数组或者只有一个元素的数组。因此基线条件为空或者只包含一个元素。在这种情况，可以直接返回该数组。

代码片段实现：

private int[] quickSort(int[] array){
		if(array.length < 2){
			return array;
		}
	}

我们再在数组里加一个元素，两个元素应该如何排序呢？思路也很简单，如果从小到大排序，就需要将这两个元素进行比较，如果前一个比较小，直接返回；如果前一个比较大，就需要互相交换，然后返回数组。那么包含三个元素或者更长的数组应该怎么排序呢？

此时我们可以考虑分而治之算法，将数组进行分解，直到满足基线条件。第一步，从数组中选择一个基准值，理论上这个基准值是可以随意挑选的，你可以选择数组首项也可以选择中项甚至可选择尾项。（有什么区别在后面讲）

我们暂时先将数组中的第一个值用作基准值，接下来，我们需要找出比基准值大的和小的元素，这被称为"分区"，这样操作之后，你会有一个比基准值小的数字组成的子数组、基准值、一个比基准值大的数字组成的子数组。

但是这里只是进行了分区，但这个分区数组并不一定就是有序的。但是我们三项的数组就可以在选出一个基准值的情况下，然后对后面的数组（只含有两项）进行排序（这个很容易），这样我们也得到了有序数组，那么四项数组、五项数组甚至更多项呢？

2.2 代码实现

书上使用的Python代码，我将其翻译为JAVA语言，快速排序算法利用python语言是很好实现的，但是java实现起来还是比较麻烦的。通过网上查阅，先将编译好的java代码进行展现。

private static int partition(int[] arr, int low, int high) {
        //指定左指针i和右指针j
        int i = low;
        int j= high;

        //将第一个数作为基准值。挖坑
        int x = arr[low];

        //使用循环实现分区操作
        while(i<j){//5  8
            //1.从右向左移动j，找到第一个小于基准值的值 arr[j]
            while(arr[j]>=x && i<j){
                j--;
            }
            //2.将右侧找到小于基准数的值加入到左边的（坑）位置， 左指针想中间移动一个位置i++
            if(i<j){
                arr[i] = arr[j];
                i++;
            }
            //3.从左向右移动i，找到第一个大于等于基准值的值 arr[i]
            while(arr[i]<x && i<j){
                i++;
            }
            //4.将左侧找到的打印等于基准值的值加入到右边的坑中，右指针向中间移动一个位置 j--
            if(i<j){
                arr[j] = arr[i];
                j--;
            }
        }

        //使用基准值填坑，这就是基准值的最终位置
        arr[i] = x;//arr[j] = y;
        //返回基准值的位置索引
        return i; //return j;
    }
    private static void quickSort(int[] arr, int low, int high) {//???递归何时结束
        if(low < high){
            //分区操作，将一个数组分成两个分区，返回分区界限索引
            int index = partition(arr,low,high);
            //对左分区进行快排
            quickSort(arr,low,index-1);
            //对右分区进行快排
            quickSort(arr,index+1,high);
        }

    }

2.3 运行时间

快速排序的运行时间在于你选择的基准值。假设你一直都选择第一个元素作为基准值，且要处理的数组是有序的。快速排序不检查数组元素的顺序，因此还是会尝试对其排序，但是这会有一个问题，每次选择第一个作为基准值，导致比基准值小的数组都是空的，使得调用栈非常高。运行时间较长。栈长表示为O(n)。

调用栈（最糟情况）

那有没有更好的办法呢？有的，我们可以参考二分查找的实现方法，每次选择中间的元素作为基准值，就会发现调用栈被减短了许多，不需要太多的递归调用，就会达到基线条件，最佳情况下栈长为O(logn)。

最佳情况

因此，在最糟糕的情况下（选择第一个为基准值）运行时间为O(n)。在最佳情况下，运行时间仅为O(nlogn)。