快速排序及其优化

package leetcode.mySort;

import java.util.Random;

public class QuickSort {

private final static Random random = new Random(System.currentTimeMillis());

// 快速排序的不同类型的写法，差别在于partition 下面的partition是大学时候老师教的方法 partition2是
// 类似三色国旗的写法，为后续的优化做准备 partition和partition2本质上都是二路快排

public static int partition(int[] array,int start,int end){
    int base = array[start];
    while (start<end){
        while (start<end&&array[end]>=base)  end--;
        array[start] = array[end];

        while (start<end&&array[start]<=base)  start++;
        array[end] = array[start];
    }
    array[start] = base;
    return start;
}

public static int partition2(int[] array,int start,int end){
    int pivot = array[start];

    // j代表较小区间的最后一个
    // all in array[left+1,j] <= pivot
    // all in array(j,i) > pivot

    int j = start;

    // 大方过，小交换
    for (int i = start+1; i <= end; i++) {
        if (array[i]<pivot){
            j++;
            swap(array,i,j);
        }
    }
    swap(array,start,j);
    return j;
}

// 随机初始化pivot
public static int partition3(int[] array,int start,int end){
int randomIndex =start + random.nextInt(end - start + 1);
swap(array,start,randomIndex);
int pivot = array[start];
int j = start;

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

    }
    swap(array,start,j);
    return j;
}

// 三路快排
public static void quickSort3(int[] array, int start, int end){

    if (start>=end){
        return;
    }

    int randomIndex = start + random.nextInt(end - start + 1);
    swap(array,start,randomIndex);
    int pivot = array[start];

    int lt = start + 1;     // lt:less than
    int gt = end;           // gt:greater than

    // all in nums[left+1,lt) < pivot
    // all in nums[lt,i) = pivot
    // all in nums(gt,right] > pivot
    int i = start + 1;

    while (i <= gt){
        if(array[i]<pivot){
            swap(array,i,lt);
            i++;
            lt++;
        }else if (array[i]==pivot){
            i++;
        }else{
            swap(array,i,gt);
            gt--;
        }
    }
    swap(array,start,lt-1);
    quickSort3(array,start,lt-1);
    quickSort3(array,gt+1,end);
}


private static void swap(int[] array, int start, int end) {
    int temp = array[start];
    array[start] = array[end];
    array[end] = temp;
}

public static void quickSort(int[] array,int start,int end){

    if (start<end){
        int index = partition3(array,start,end);
        quickSort(array,start,index-1);
        quickSort(array,index+1,end);
    }
}


public static void main(String[] args) {

// int[] array = {2,4,6,1,3,5};
int[] array = {3,2,3,1,2,4,5,5,6};
quickSort3(array,0,array.length-1);
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
}

参考：https://www.bilibili.com/video/BV1Kr4y187VP/?spm_id_from=333.788&vd_source=46d50b5d646b50dcb2a208d3946b1598