Java常用排序算法（插入排序，快速排序，歸並排序）

插入排序

插入排序的概念比較簡單，就像平時玩撲克一樣，將後面來的數插入到前面序列中,在插入的時候我們默認前面的序列已經是有序的。

public class InsertSort {
    publicstaticvoidinsertSort(int[] a){
        int i, j;
        int n =a.length;
        int target;
        for (i = 1; i < n; i++) {
           j = i;
            target = a[i];
            while (j > 0 && target < a[j-1])
            {
                a[j] = a[j-1];
                j--;
            }
            a[j] = target;
        }
    }
    publicstaticvoidmain(String[] args){
        int[]  a={1,5,9,4,10,8,7};
        insertSort(a);
        for(int i= 0;i<a.length;i++){
            System.out.print(a[i]+",");
        }
    }
}

快速排序

快速排序是一種選擇排序，在序列中選取一個中間值，是左邊的數全部不大於（不小於）這個中間值，右邊的數全部不小於（不大於）這個數。使整個序列分成左右兩個分序列，然後以遞歸的方式，使兩邊的數據集按上述規則處理，直到數據集的元素數不少於一個。

public class QuickSort {
    publicstaticintgerMark(int[] a, int left ,int right){
        int mark = a[left];
        while(left<right){
            while(left<right&&mark<a[right]){
                right--;
            }
            a[left]=a[right];
            while(left<right&&mark>a[right]){
                left++;
            }
            a[right]=a[left];
        }
        a[left]= mark;
        return left;
    }
    
    publicstaticvoidquickSort(int[] a, int left ,int right){
        if(left<right){
            int middle = gerMark(a,left,right);
            quickSort(a,left,middle-1);
            quickSort(a,middle+1,right);
        }
    }
    
    publicstaticvoidmain(String[] args){
        
        int[] a={7,2,5,4,12};
        quickSort(a,0,a.length-1);
        for(int i= 0;i<a.length;i++){
            System.out.print(a[i]+",");
        }
    }
}

歸並排序

歸並排序也是以遞歸的方式進行排序，但是它是插入排序的延伸，我們要以遞歸的逆過程和插入排序的二維插入（插入排序是一個一個插入，歸並排序是一組數據插入另一組數據）來思考，首先可以想象，整個序列相當於一個根節點，經過不斷地遞歸劃分成為一個二叉樹，直到每個節點都只有一個元素，再一層一層地向上進行二維的插入排序。

public class MergeSort {

    public  static int[] mergeSort(int[] a, int left,int right){
        int middle = (left+right)/2;
        if(left<right){
            mergeSort(a,left,middle);
            mergeSort(a,middle+1,right);
            merge(a,left,middle,right); 
        }
        return a;
    }
    
    publicstaticvoidmerge(int[] a ,int left ,int middle,int right){
        int[] temp = new int[right-left+1];
        int i=left;
        int j=middle+1;
        int k=0;
        while(i<=middle&&j<=right){
            if(a[i]<a[j]){
                temp[k++]=a[i++];
            }
            else{
                temp[k++]=a[j++];
            }
        }   
        while(i<=middle){
            temp[k++]=a[i++];
        }
        while(j<=right){
            temp[k++]=a[j++];
        }
        for(int m=0;m<temp.length;m++){
            a[left+m] = temp[m];
        }
    }
    
    publicstaticvoidmain(String[] args){
        int[] a={8,99,37,10,51,109};
        mergeSort(a,0,a.length-1);
        for(int i= 0;i<a.length;i++){
            System.out.print(a[i]+",");
        }
    }
}