算法：快速排序的学习（二）

第二节 快速排序

前言

算法对于一个程序员来说可以是一门必修课，基础的排序算法更是重要。在我学习期间，将自己学到的东西进行分享，希望可以帮到大家。
特别感谢《漫画算法-小灰的算法之旅》，魏梦舒著。提供的知识。

一、快速排序的实现（单边循环法）

双边循环法从数组的两边交替遍历元素，虽然更加直观，但是代码实现相对烦琐。而单边循环法则简单得多，只从数组的一边对元素进行遍历和交换。我们来看一看详细过程。

  1. 给出原始数列如下，要求对其从小到大进行排序。
    在这里插入图片描述

  2. 开始和双边循环法相似，首先选定基准元素pivot。同时，设置一个mark指针指向数列起始位置，这个mark指针代表小于基准元素的区域边界。
    在这里插入图片描述

  3. 接下来，从基准元素的下一个位置开始遍历数组。
    如果遍历到的元素大于基准元素，就继续往后遍历。
    如果遍历到的元素小于基准元素，则需要做两件事：第一，把mark指针右移1位，因为小于pivot的区域边界增大了1；第二，让最新遍历到的元素和mark指针所在位置的元素交换位置，因为最新遍历的元素归属于小于pivot的区域。
    首先遍历到元素7，7>4，所以继续遍历。
    在这里插入图片描述

  4. 接下来遍历到的元素是3，3<4，所以mark指针右移1位。
    在这里插入图片描述

  5. 随后，让元素3和mark指针所在位置的元素交换，因为元素3归属于小于pivot的区域。
    在这里插入图片描述

  6. 按照这个思路，继续遍历，后续步骤如图所示。
    在这里插入图片描述
    实现代码如下：

public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] array=new int[] {28,6,41,20,33,17,9,95,71};
        quickSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
    //递归调用快速排序算法
    public static void quickSort(int[] array, int startIndex, int endIndex) {
        if(startIndex>=endIndex) {
            return;
        }
        //基准元素的产生方法
        int pivotIndex=partition(array,startIndex,endIndex);
        quickSort(array,startIndex,pivotIndex-1);
        quickSort(array,pivotIndex+1,endIndex);
    }

    //单边循环的实现，找到基准点
    private static int partition(int[] array, int startIndex, int endIndex) {
        //基准点，当前数组的第一个元素作为基准点使用。
        int pivot=array[startIndex];
        //标记指针----->实现单边循环的关键对象，从当前数组的起点开始
        int mark=startIndex;
        //单边的具体实现
        for(int i=startIndex+1; i<=endIndex; i++) {
            //基准点大于当前i所在的元素，就要让mark标记自动加一，移动下一个位置，并将当前位置的元素与i除的元素进行交换即可。
            if(pivot>array[i]) {
                mark++;
                int temp=array[i];
                array[i]=array[mark];
                array[mark]=temp;
            }
        }
        //一次下来，将基准点与mark相互换位置
        array[startIndex]=array[mark];
        array[mark]=pivot;
        return mark;
    }