同冒泡排序，快速排序也是交换排序

思想

每一轮挑选一个基准元素，并让其他比它大的元素移动到数列的一边，比它小的移动到另一边，从而把数列拆成两个部分，一个部分的数全部比基准元素打，另一个部分全部比它小。

这种思想叫做 分治法
原数列在每一轮都被拆成两部分，两部分中的每一部分又被拆成两部分，一直递归下去，直至不可再分，因此要遍历 logn 轮，而且每一轮的交换和比较要遍历数组，因此时间复杂度为 O(nlogn)

基准元素的选择

最简单的方式是选第一个元素，但是在数列基本有序，或者逆序的情况下，数列没有理想的被分为均匀的两半，每一轮只确定基准元素的位置，时间复杂度退化为O(n^2)

解决方法：随机选择一个元素作为基准元素，并让基准元素和数列首位元素交换位置

元素的交换

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

实现方法

双边循环法

也就是数据结构中学的方法，为双指针法。

首先选定基准元素pivot，并设置两个指针left，right，分别指向数组的最左边和最右边
进行循环，从right指针开始，让指针所指向的元素和基准元素做比较。
1. 如果大于或等于pivot，则right指针右移
2. 如果小于pivot，则right指针停止移动，right和left指向的值互换，切换到left指针
3. 让left指针指向的元素和基准元素作比较，如果小于等于pivot，则左移，反之停止移动，right和left指向的值互换，切换到right指针
一直循环下去，直到 right == left
最后把pivot的与两指针汇合处的元素与pivot互换，即完成第一次分治

实现

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);
}

public static int partition(int[] arr, int startIndex, int endIndex){
    //取第一个位置的元素作为基准元素
    int pivot = arr[startIndex];
    int left = startIndex;
    int right = endIndex;

    while(left != right){
        while(left < right && arr[right] > pivot)
            right--;
        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;
}

单边循环法

双边循环从数组的两边交替遍历元素，虽然更加直观，但是代码量较多。单边循环法只从数组的一边对元素进行遍历和交换。

选定基准元素pivot，设置一个mark指针指向数列起始位置，这个mark指针代表 小于基准元素的区域边界
接下来，从基准元素的下一个位置开始遍历数组
1. 如果遍历到的元素大于基准元素，就继续往后遍历
2. 如果小于基准元素，需要做两件事：
  第一，把mark指针右移一位，因为小于pivot的区域边界增加了1；
  第二，让最新遍历到的元素和mark指针所在位置的元素互换，因为最新遍历的元素归属与小于pivot的区域
按照这个思路，继续遍历，直至末位，最后把pivot元素交换到mark指针所在的位置，第一次分治结束

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

public static int partitionV2(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;
}