图解：快速排序算法之双边循环法

一.快速排序介绍

由快速排序演变而来的快速排序也是沿用了交换排序，通过元素之间的比较和交换位置来达到排序的目的。不同的是快速排序使用了分治法。冒泡排序在每一轮只把1个元素冒泡到数列一端，而快速排序则先在每一轮挑选1个基准元素，并让其他比他大的元素移动到数列一端，比他小的元素移动到数列另一端，从而把数列拆成两个部分。

二.逻辑推演

每一轮挑选1个基准元素，并让其他比他大的元素移动到数列一端，比他小的元素移动到数列另一端，从而把数列拆成两个部分，这种操作方式被称为分治法。

分治法：

如图示：

橙色：挑选的基准元素

蓝色：小于基准元素的数

粉色：大于基准元素的数

假设给我8个数的数列，按照冒泡排序通常需要比较7轮，每一轮确定一个元素移动到数列的某一端，时间复杂度为O(n^2)。而快速排序采用分治法如图：

如图所示：

在分治法思想下，原数列在每一轮都被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可分为止。

每一轮的比较和交换，需要把数组全部元素都遍历一次，时间复杂度为O(n)。这样的遍历需要多少轮？假设元素个数为n，那平均情况下需要logn轮，因此快速排序算法总体的平均时间复杂度为O(nlogn)。

基准元素选择：

在分治过程中，以基准元素为中心，把其他元素移动到它的左右两边。分治法的第一环节就是确定基准元素，那么基准元素如何产生？

最简单的方式是选择数列的第1个元素，作为基准元素。

这种选择在绝大多数情况下，没有问题。但是假如有一个原本逆序的数列，期望排序成顺序数列，那就会出现这样的情况：

第4轮...

第5轮...

整个数列并没有被分成两半，每一轮都只是确定了基准元素的位置。这种情况下，数列的第1个元素要么数列的最小值，要么是数列的最大值，完全无法发挥分治法的优势。在这样的极端情况下，快速排序需要进行n轮，时间复杂度退化成了O(n^2)。

那么如何避免这样的情况发生呢？

其实很简单，我们可以随机选择一个元素作为基准元素，并让基准元素和数列首元素交换位置。

例如：随机得到元素4作为基准，然后将4与首位8进行交换。

这样的话，即使在数列完全逆序的情况下，也可以有效的将数列分成两部分了。

不过，即使是随机选择元素作为基准元素，也会有小概率选到数列的最大或者最小值，同样会影响分治的效果。因此虽然快速排序的平均时间复杂度为O(nlogn)，但是最坏情况下时间复杂度是O(n^2)。

元素的交换：

选定了基准元素以后，我们要做的就是把其他元素中小于基准元素的都交换到基准元素的一边，大于基准元素的都交换到基准元素的另外一边。

具体如何实现？有两种方法。

1.双边循环法

2.单边循环法

三.快速排序之双边循环法

分析：

何谓双边循环法？下面看看详细过程。

原始数列如下，要求对其从小到大排序。

1.首先，选定基准元素4，并且设置两个指针left和right，指向数列的最左和最右两个元素。

2.接下来进行第1次循环，从right指针开始，让指针所指向的元素和基准元素做比较。如果大于或等于基准元素，则指针向左移动；如果小于基准元素，则right指针停止移动，切换到left指针。

当前数列中，1<4，所以right指针直接停止移动，换到left指针，进行下一步行动。

3.轮到left指针行动，让指针所指向的元素和基准元素做比较。如果小于或等于基准元素，则指针向右移动，如果大于基准元素，则left指针停止移动。

当前数列中，left指针指向的就是基准元素所以相等，则left右移1位。

4.由于7>4，left指针在元素7的位置处停下来。这时候，让left和right指针指向的元素进行交换，即数字7和数字1进行交换。

5.接下来进行第2次循环，重新切换到right指针，向左移动。right指针先移动到8，8>4，继续向左移动。由于2<4，right指针停止在2的位置。

按照这个思路，后续步骤如图所示：

第2次循环right指针停在2的位置，left指针停在6的位置。

元素2和6进行交换

第3次循环，right指针在3的位置，left指针在5的位置，3和5发生元素交换

第4次循环，right指针停在3的位置和left指针重合。

最后把基准元素4和重合点3进行交换，这一轮宣告结束，数列分成两部分。。

代码实现：

下面通过递归的方式完成双边循环法的快速排序实现

初始数列为：4，4，6，5，3，2，8，1

    public static void main(String[] args) {
   
   
        int[] arr = {
   
   4,4,6,5,3,2,8,1};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int startIndex, int endIndex) {
   
   
        //递归结束条件：startIndex>=endIndex时
        if(startIndex>=endIndex){
   
   
            return;
        }
        //得到基准元素的位置
       int pivotIndex = partition(arr,startIndex,endIndex);
        //根据基准元素，分成两部分进行递归排序
        quickSort(arr,startIndex,pivotIndex-1);
        quickSort(arr,pivotIndex+1,endIndex);
    }

    private static int partition(int[] arr, int startIndex, int endIndex) {
   
   
        //取第1个位置（也可以选择随机位置）的元素作为基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;
        while (left != right){
   
   
            //控制right指针比较并右移
            while(left<right && arr[right]>pivot){
   
   
                right--;
            }
            //控制left指针比较并右移
            while (left<right && arr[left]<=pivot){
   
   
                left++;
            }
            //交换left和right指针所指向的元素
            if(left<right){
   
   
                int p = arr[left];
                arr[left]=arr[right];
                arr[right]=p;
            }

        }
        //pivot和指针重合点交换
        arr[startIndex] = arr[left];
        arr[left] = pivot;
        return left;
    }

小结：

在上述代码中，quickSort方法通过递归的方式，实现了分而治之的思想。

partition方法则实现了元素的交换，让数列中的元素依据自身大小，分别交换到基准元素的左右两边。这样的交换方式被称为双边循环法。

四.总结

partition方法实现挺复杂的，在一个大循环中还嵌套了两个小循环。不过以双边循环法作为基础，又延伸出来了单边循环法，单边循环法就要简单得多，只从数组的一遍对元素进行遍历和交换。下一章，我们将探寻单边循环法。