几种常见排序算法

冒泡，插入，选择，快排，归并学习ing。。请直接看源码；原理在注释中有体现，嘻嘻。。

 public class SortTest {

    public static void  main(String[] args){
            int[] a = new int[]{3,1,5,8,4,6,5,10,9};
            splitMerge(a,0,a.length-1);
            for(int value : a) {
            System.out.print(value + ",");
        }
    }

    /**
     * 快速排序
     * 分治+递归 选取第一个元素作为分界点，将其比他大和小的分成两组，与中间元素替换位置，依次对左，右两边进行递归
     * 时间复杂度 O(nlog2n) 空间O(logn)
     * @param a
     * @param low
     * @param high
     */
    public static void fastSort(int a[],int low,int high) {
        if(low >= high){
            return;
        }
         int l = low;
         int r = high-1;
         int temp = a[low];
         while(l!=r){
             while(a[r] >= temp && l<r){
                 r--;
             }
             while(a[l]<= temp && l<r){
                 l++;
             }
             if(l<r){
                 swap(a,l,r);
             }
         }
        swap(a,low,l);
        fastSort(a,low,l-1);
        fastSort(a,l+1,high);
    }

    private static void swap(int a[],int i, int r) {
        int temp = a[i];
        a[i] = a[r];
        a[r] = temp;
    }

    /**
     * 选择排序
     * 每轮循环记录数组中最小元素位置，将其与循环最开始端替换
     * @param a
     * @param low
     * @param high
     */
    private  static  void chooseSort(int a[],int low,int high){
        for(int i = low ;i < high-1 ;i++){
            int min = i;
            for(int j = i+1;j < high;j++){
                if(a[min] > a[j]){
                    min = j;
                }
            }
            if(i!= min)
                swap(a,i,min);
        }
    }

    /**
     * 插入排序
     * 从第1个元素开始，将其插入前面已排好序的队列中，需要注意，内部循环必须从右往左替换
     * @param a
     * @param low
     * @param high
     */
    private static void insertSort(int a[],int low,int high){
        for(int i = low+1;i<high;i++){
            int temp = a[i];
            for(int j = i-1;j>=0;j--){
                if(temp < a[j]){
                    swap(a,j,j+1);
                    temp = a[j];
                }
            }
        }
    }

    /**
     * 冒泡排序
     * 两辆相邻元素比较，将最大值推到循环末端
     * @param a
     * @param low
     * @param high
     */
    private static void maopaoSort(int a[],int low,int high){
        for(int i=low;i<high-1;i++){
            for(int j =0;j<high-i-1;j++){
                if(a[j] > a[j+1]){
                    swap(a,j,j+1);
                }
            }
        }
    }


    /**
     * 两个数组之间比较 low至mid ,mid+1至high
     * 请注意入参是mid+1,开区间
     * @param a
     * @param low
     * @param mid
     * @param high
     */
    private static void mergeSort(int a[],int low,int mid, int high){
        int[] leftArr = new int[mid - low];
        int[] rightArr = new int[high - mid+1];

        //往数组填充数据
        for(int i=0;i<mid-low;i++){
            leftArr[i]= a[low+i];
        }
        for(int j = 0;j<= high-mid;j++){
            rightArr[j] = a[mid+j];
        }
        int i = 0,j= 0,k = low;
        while(i < leftArr.length && j < rightArr.length){
            if(leftArr[i] <= rightArr[j]){
                a[k++]=leftArr[i++];
            }else{
                a[k++]=rightArr[j++];
            }
        }
        while(i < leftArr.length ){
            a[k++]=leftArr[i++];
        }
        while(j < rightArr.length ){
            a[k++]=rightArr[j++];
        }

    }

    //递归拆分数组,当数组中只有一个元素时停止
    private static void splitMerge(int a[],int low,int high){
        if(low == high){
            return ;
        }
        int mid = (low+high)/2;
        splitMerge(a,low,mid);
        splitMerge(a,mid+1,high);
        mergeSort(a,low,mid+1,high);
    }

}