快速排序的基本思想

参考资料：
《剑指offer》P64

下面是我抄《剑指offer》P64的，partition函数的主要思路是，选中的pivot放在最后固定的位置，只用一个smallIndex指示左边的都是小于pivot，然后对全体的数进行遍历，如果小于就放到smallIndex后面一个的位置。最后交换pivot和smallIndex后面一个的位置。

不管small_index是否包含小于pivot的元素，pivot到底取start还是end-1，都是可以的，主要记住，在最后一步swap的时候，如果是start就要把一定是小于pivot的跟它交换，如果是end-1就要把一定是大于pivot的跟它交换。

可以对比下下面的实现

import java.util.Arrays;

/**
 * @program: offer
 * @description:
 * @author: liyuecheng
 * @create: 2020-05-25 20:24
 **/
public class QuickSort {
    public static void main(String[] args) {
        int[] array1 = new int[]{4,3,2,1};
        int[] array2 = new int[]{3,4,2,1};
        int[] array3 = new int[]{1,3,2,4};
        int[] array4 = new int[]{2,5,3,4,1};

        quickSort(array1);
        quickSort(array2);
        quickSort(array3);
        quickSort(array4);

        System.out.println(Arrays.toString(array1));
        System.out.println(Arrays.toString(array2));
        System.out.println(Arrays.toString(array3));
        System.out.println(Arrays.toString(array4));
    }

    static void quickSort(int[] array){
        // quickSort(array, 0, array.length);
        quickSort1(array, 0, array.length);
        // quickSort2(array, 0, array.length);
        // quickSort3(array, 0, array.length);
    }

    // pivot_index取start
    // last_small_index包含小于pivot的值
    static void quickSort(int[] array, int start, int end){
        if((end-start)<=1)
            return;

        int pivot_index = start;
        int pivot = array[pivot_index];
        int last_small_index = start;

        for (int i = last_small_index + 1; i < end; i++) {
            if(array[i] < pivot) {
                swap(array, i, last_small_index+1);
                last_small_index += 1;
            }
        }

        swap(array, pivot_index, last_small_index);
        quickSort(array, start, last_small_index);
        quickSort(array, last_small_index+1, end);
    }

    // pivot_index取end-1
    // last_small_index包含小于pivot的值
    static void quickSort1(int[] array, int start, int end){
        if((end-start)<=1)
            return;

        int pivot_index = end-1;
        int pivot = array[pivot_index];
        int last_small_index = start-1;

        for (int i = start; i < end-1; i++) {
            if(array[i]<pivot){
                swap(array, i, last_small_index+1);
                last_small_index += 1;
            }
        }

        swap(array, pivot_index, last_small_index+1);
        quickSort1(array, start, last_small_index+1);
        quickSort1(array, last_small_index+2, end);
    }

    static void quickSort2(int[] array, int start, int end){
        if((end-start)<=1)
            return;

        int pivot_index = start;
        int pivot = array[pivot_index];
        int next_to_put_small_index = start+1;

        for (int i = start+1; i < end; i++) {
            if(array[i] < pivot){
                swap(array, i, next_to_put_small_index);
                next_to_put_small_index += 1;
            }
        }

        // next_to_put_small_index-1 一定是小于pivot的，把它放到pivot_index = start那里去
        // pivot放到中间来
        swap(array, pivot_index, next_to_put_small_index-1);
        quickSort2(array, start, next_to_put_small_index-1);
        quickSort2(array, next_to_put_small_index, end);
    }

    // 两个指针
    static void quickSort3(int[] array, int start, int end){
        if((end-start)<=1){
            return;
        }

        int pivot = array[end-1];
        int small_index = start - 1;
        int big_index = end;

        while(small_index<big_index) {
            while((small_index+1) < big_index && array[small_index+1] < pivot)
                small_index += 1;

            if((small_index+1) >= big_index) {
                array[big_index-1] = pivot;
                quickSort3(array, start, big_index-1);
                quickSort3(array, big_index, end);
                break;
            }else{
                array[big_index-1] = array[small_index+1];
                big_index -=1;
            }

            while(small_index < (big_index-1) && array[big_index-1] > pivot)
                big_index -= 1;

            if(small_index >= (big_index-1)) {
                array[small_index+1] = pivot;
                quickSort3(array, start, small_index+1);
                quickSort3(array, small_index+2, end);
                break;
            } else {
                array[small_index+1] = array[big_index-1];
                small_index +=1;
            }
        }
    }

    static void swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}