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

一、单边循环法概述

单边循环法是快速排序的算法之一，之前的双边循环法从数列的两边交替遍历元素，虽然更加直观，不过代码实现起来相对复杂。而单边循环法就要简单多了，只需要从数组的一边对元素进行遍历和交换即可。

二、逻辑推演

单边循环法的详细过程，假设数列为：[4,7,3,5,6,2,8,1]

开始和双边循环法相似，首先选定基准元素。同时，设置一个mark指针记录数列的起始位置，该指针代表小于基准元素的区域边界。

接着，从基准元素的下一个位置开始遍历数组。

如果遍历到元素大于基准元素，就继续往后遍历。

如果遍历到元素小于基准元素，则要做两件事：1.把mark指针右移1位，因为小于基准元素的区域边界增大了1；2.让最新遍历到的元素和mark指针所在位置的元素交换位置，因为最新遍历的元素归属于小于基准元素的区域。

先遍历元素到7,因为7>4所以继续向后遍历。

然后遍历到元素3,3<4，所以mark指针右移1位。

元素3和mark指针所在位置的元素交换，因为元素3属于小于基准元素的区域。

如果按照这个思路继续遍历的话，图就如下所示了。

省略中间的过程...最后把基准元素交换到mark指针所在位置，这一轮宣告结束，得到这样一个排列

此时这一轮排序宣告结束，继续下一轮排序。

这个方法只需要单边循环，确实简单了许多，下面我们用代码来实现

三、代码实现

    public static void main(String[] args) {
   
   
        int[] arr = new int[]{
   
   4,3,7,5,6,2,8,1};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public 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) {
   
   
        //获取第一个位置，成为基准元素
        int pivot = arr[startIndex];
        int mark = startIndex;
        for (int i = startIndex+1; i <=endIndex ; i++) {
   
   
            if(arr[i]<pivot){
   
   
                mark++;
                int p = arr[mark];
                arr[mark]=arr[i];
                arr[i]=p;
            }
        }
        arr[startIndex] = arr[mark];
        arr[mark]=pivot;
        return mark;
    }

总结

以递归为基础的单边循环法成功实现排序，其实除了递归实现以外，我们还可以使用非递归的实现方式完成快速排序，非递归的方式在下一篇文章。