1，快速排序

基本思想：選擇一個(gè)基準(zhǔn)元素,通常選擇第一個(gè)元素或者最后一個(gè)元素,通過一趟掃描喂急，將待排序列分成兩部分,一部分比基準(zhǔn)元素小,一部分大于等于基準(zhǔn)元素,此時(shí)基準(zhǔn)元素在其排好序后的正確位置,然后再用同樣的方法遞歸地排序劃分的兩部分念赶。

image.png

public class QuickSort {
    public static void main(String[] args) {
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
        System.out.println("排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        //快速排序
        quick(a);
        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

    private static void quick(int[] a) {
        if(a.length>0){
            quickSort(a,0,a.length-1);
        }
    }

    private static void quickSort(int[] a, int low, int high) {
        if(low<high){ //如果不加這個(gè)判斷遞歸會(huì)無法退出導(dǎo)致堆棧溢出異常
            int middle = getMiddle(a,low,high);
            quickSort(a, 0, middle-1);
            quickSort(a, middle+1, high);
        }
    }

    private static int getMiddle(int[] a, int low, int high) {
        int temp = a[low];//基準(zhǔn)元素
        while(low<high){
            //找到比基準(zhǔn)元素小的元素位置
            while(low<high && a[high]>=temp){
                high--;
            }
            a[low] = a[high]; 
            while(low<high && a[low]<=temp){
                low++;
            }
            a[high] = a[low];
        }
        a[low] = temp;
        return low;
    }
}

2伴箩，歸并排序

基本思想：對(duì)于給定的一組集合启涯，利用遞歸與分治技術(shù)將數(shù)據(jù)序列劃分成為越來越小的子集合困肩，再對(duì)子集合排序整陌，最后再用遞歸方法將排好序的子集合合并成為越來越大的有序序列拗窃。
經(jīng)過第一輪比較后得到最小的記錄瞎领，然后將該記錄的位置與第一個(gè)記錄的位置交換；接著對(duì)不包括第一個(gè)記錄以外的其他記錄進(jìn)行第二次比較随夸，得到最小記錄并與第二個(gè)位置記錄交換九默；重復(fù)該過程，知道進(jìn)行比較的記錄只剩下一個(gè)為止宾毒。

20160427172905073.png

public class MergeSort {

    public static void main(String[] args) {
        int[] data = {50,10,90,30,70,40,80,60,20};
        print(data,true);
        mergeSort(data, 0, data.length -1 );
        print(data,false);
    }

    private static void mergeSort(int[] data, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            mergeSort(data, left, middle);
            mergeSort(data, middle + 1, right);
            merge(data, left, middle, right);
        }

    }

    private static void merge(int[] data, int left, int middle, int right) {
        int[] tmpArray = new int[data.length];
        int mid = middle + 1;
        int third = left;
        int tmp = left;

        while(left <= middle && mid <= right) {

            if(data[left] <= data[mid]) {
                tmpArray[third++] = data[left++];
            }else {
                tmpArray[third++] = data[mid++];
            }
        }

        // 剩余部分依次放入臨時(shí)數(shù)組（實(shí)際上兩個(gè)while只會(huì)執(zhí)行其中一個(gè)）
        while (mid <= right) {
            tmpArray[third++] = data[mid++];
        }
        while (left <= middle) {
            tmpArray[third++] = data[left++];
        }

        // 將臨時(shí)數(shù)組中的內(nèi)容拷貝回原數(shù)組中
        // （原left-right范圍的內(nèi)容被復(fù)制回原數(shù)組）
        while (tmp <= right) {
            data[tmp] = tmpArray[tmp++];
        }

    }

    private static void print(int[] data, boolean before) {
        if(before) {
            System.out.println("排序之前：");
        }else {
            System.out.println("排序之后：");
        }
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + ", ");
        }
        System.out.println();
    }