快速排序及其改进算法Java实现

import java.util.Random;
public class Main {
    //输出数组
    public static void show(int[] a){
        for(int i:a)
            System.out.print(i+" ");
        System.out.println();
    }
    //交换元素
    public static void swap(int[] a,int i,int j){
        if(i<0||j<0||i>a.length||j>a.length){
            return ;
        }
        int tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
    }
    //一趟快速排序
    public static int partition(int[] a,int low,int high){
        int key=a[low];
        while(low<high){
            while(low<high && a[high]>=key) high--;
            a[low]=a[high];
            while(low<high && a[low]<=key) low++;
            a[high]=a[low];
        }
        a[low]=key;
        return low;
    }
    /**
     * 普通算法：快速排序
     */
    public static void quickSort(int[] a,int low,int high){
        if(low>=high){
            return;
        }
        //固定切分
        int index=partition(a,low,high);
        quickSort(a,low,index-1);
        quickSort(a,index+1,high);
    }
    /**
     * 改进算法：快速排序
     */
    public static void midQuickSort(int[] a,int low,int high){
        if(low>=high){
            return;
        }
        //三取样切分
        int mid=(low+high)/2;
        if(a[mid]>a[high]) swap(a,a[mid],a[high]);
        if(a[low]>a[high]) swap(a,a[low],a[high]);
        //上面两步后，最大值在a[high]；下面将中值放到low处
        if(a[mid]>a[low]) swap(a,a[low],a[mid]);
        int index=partition(a,low,high);
        midQuickSort(a,low,index-1);
        midQuickSort(a,index+1,high);
    }
    /**
     * 随机算法：快速排序
     */
    public static void randomQuickSort(int[] a,int low,int high){
        if(low>=high){
            return;
        }
        //随机切分
        swap(a,low,new Random().nextInt(high)%(high-low+1)+low);
        int index=partition(a,low,high);
        randomQuickSort(a,low,index-1);
        randomQuickSort(a,index+1,high);
    }


    public static void main(String[] args) {
        int[] a1={49,3,17,6,29,58,9,49,31,87};
        quickSort(a1,0,a1.length-1);
        show(a1);
        int[] a2={49,3,17,6,29,58,9,49,31,87};
        midQuickSort(a2,0,a2.length-1);
        show(a2);
        int[] a3={49,3,17,6,29,58,9,49,31,87};
        randomQuickSort(a3,0,a3.length-1);
        show(a3);
    }

}