博客

交换排序：1、快速排序

先假设一个中枢轴，将小于中枢轴的换到前面，大于中枢轴的换到后面，确定中枢轴的下标，返回给排序函数，进行递归。

public class QuickSort {
    //快速排序函数
    public static void quickSort(int[] arry,int left,int right){
        int pivo;
        if(left<right){
            pivo=partition(arry,left,right); //确定中枢轴
            quickSort(arry,left,pivo-1);
            quickSort(arry,pivo+1,right);
        }
    }
    //获取中枢轴下标函数
    public static int partition(int[] arry,int left,int right){
        //假设第一个为中枢轴
        int pivokey=arry[left];
        //左边找大于中枢轴的，右边找小于中枢轴的
        while(left<right){
            while(left<right && arry[right]>=pivokey){
                right--;
            }
            swap(arry,left,right);
            while(left<right && arry[left]<=pivokey){
                left++;
            }
            swap(arry,left,right);
        }
        //返回确定的中枢轴下标
        return left;
    }
    //交换函数
    static void swap(int[] arry,int a,int b){
        int temp=arry[a];
        arry[a]=arry[b];
        arry[b]=temp;
    }
    //主函数
    public static void main(String[] args) {
        int[] a={1,2,5,4,8,7,5,9};
        quickSort(a,0,a.length-1);
        for(int e:a){
            System.out.println(e);
        }
    }

}