排序復(fù)雜度

package paixu;

/**
 * @author mengwen E-mail: meng_wen@126.com
 * @date 創(chuàng)建時(shí)間：2016年12月8日 下午3:18:59
 * @version 1.0
 * @parameter
 * @since
 * @return
 */
public class Sort {
    public int[] data = new int[] {8,30,1,45,5,89,9,0,54,34,2,25,56,8,76,200,90,33,25,25,25,23,
            333,22,12,80};
    static final String result = "0,1,2,5,8,8,9,12,22,23,25,25,25,25,30,33,34,45,54,56,76,80,89,90,200,333";

    public static void main(String[] args) {
        // 冒泡排序
        bubbleSort(new Sort().data);
        // 選擇排序
        selectSort(new Sort().data);
        // 優(yōu)化的選擇排序
        selectSort2(new Sort().data);
        // 插入排序
        InsertSort(new Sort().data);
        // 希爾排序
        shellSort(new Sort().data);
        // 快速排序
        quicksortResult(new Sort().data);
        //堆排序
        heapSort(new Sort().data);
        //桶排序  將數(shù)組分到有限數(shù)量的桶子里
        bucketSort(new Sort().data,500);
        //歸并排序
        mergeSort(new Sort().data);
    }

    //---------------------------------------------------------------------------------------------------------------
    /**
     * 冒泡排序 O(N^2)
     * 冒泡排序算法的步驟：

      1.比較相鄰的元素翁潘。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)焰情。

      2.對(duì)每一對(duì)相鄰元素作同樣的工作城菊，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)途凫。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。

      3.針對(duì)所有的元素重復(fù)以上的步驟笛厦，除了最后一個(gè)。

      4.持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟俺夕，直到?jīng)]有任何一對(duì)數(shù)字需要比較裳凸。
     * @param data
     */
    public static void bubbleSort(int[] data) {
        int temp;
        boolean didSwap;
        for (int i = 0; i < data.length - 1; i++) {
            didSwap = false;
            for (int j = 1; j < data.length - i; j++) {
                if (data[j - 1] > data[j]) {
                    temp = data[j - 1];
                    data[j - 1] = data[j];
                    data[j] = temp;
                    didSwap = true;
                }
            }
             if(didSwap == false)
                    break;

        }
        prints("冒泡排序結(jié)果:", data);
    }
    //---------------------------------------------------------------------------------------------------------------

    /**
     *  選擇排序 O(N^2)
     *  選擇排序(SelecSort)是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下：
     *  首先在未排序序列中找到最猩睹础（大）元素登舞，存放到排序序列的起始位置，
     *  然后悬荣，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最胁っ搿（大）元素，然后放到已排序序列的末尾氯迂。
     *  以此類推践叠，直到所有元素均排序完畢。
     * @param data
     */
    public static void selectSort(int[] data) {
        for (int i = 0; i < data.length - 1; i++) {
            int k = i;
            for (int j = i + 1; j < data.length; j++) {
                if (data[k] > data[j]) {
                    k = j;
                }
            }
            if (k != i) {
                swap(data, k, i);
            }
        }
        prints("選擇排序結(jié)果:", data);
    }

    //---------------------------------------------------------------------------------------------------------------
    /**
     *       選擇排序的優(yōu)化 O(N^2)
     *    傳統(tǒng)的簡(jiǎn)單選擇排序,每趟循環(huán)只能確定一個(gè)元素排序后的定位嚼蚀。
     *    我們可以考慮改進(jìn)為每趟循環(huán)確定兩個(gè)元素(當(dāng)前趟最大和最小記錄)的位置,
     *    從而減少排序所需的循環(huán)次數(shù)禁灼。
     *    改進(jìn)后對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序,最多只需進(jìn)行[n/2]趟循環(huán)即可。
     * @param data
     */
    public static void selectSort2(int[] data) {
        int begin = 0;
        int end = data.length - 1;
        while (begin < end) {
            int min = begin;
            int max = end;
            for (int i = begin; i <= end; i++) {
                if (data[min] > data[i]) {
                    swap(data, min, i);
                }
                if (data[max] < data[i]) {
                    swap(data, max, i);
                }
            }
            ++begin;
            --end;

        }
        prints("選擇排序的優(yōu)化:", data);

    }
    //---------------------------------------------------------------------------------------------------------------
    /**
     * 插入排序 O(N^2)
     * 插入排序就是每一步都將一個(gè)待排數(shù)據(jù)按其大小插入到已經(jīng)排序的數(shù)據(jù)中的適當(dāng)位置轿曙，
     * 直到全部插入完畢弄捕。 插入排序方法分直接插入排序和折半插入排序兩種。
     * @param data
     */
    public static void InsertSort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            if (data[i - 1] > data[i]) {
                // 待排序的項(xiàng)
                int temp = data[i];
                // 該輪排序的最后一個(gè)元素的位置
                int end = i;
                // 如果前邊的大于后邊元素則交換位置导帝，遞歸向前直到全部比完
                while (end > 0 && data[end - 1] > temp) {
                    data[end] = data[end - 1];
                    end--;
                }
                // 將待排序的元素插入到該位置
                data[end] = temp;
            }
        }
        prints("插入排序結(jié)果", data);
    }
    //---------------------------------------------------------------------------------------------------------------
    /** 
     *  希爾排序 當(dāng)N大時(shí)守谓，平均的時(shí)間復(fù)雜度，大約在N^1.25--1.6N^1.25之間您单。
     *  希爾排序（ShellSort）又稱為“縮小增量排序”斋荞。該方法的基本思想是：
     *  先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序，
     *  然后依次縮減增量再進(jìn)行排序虐秦，待整個(gè)序列中的元素基本有序（增量足夠衅侥稹）時(shí)凤优，再對(duì)全體元素進(jìn)行一次直接插入排序。
     *  因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況）蜈彼，效率是很高的筑辨，因此希爾排序在時(shí)間效率上比前兩種方法有較大提高。

        希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

       1.插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)柳刮， 效率高挖垛， 即可以達(dá)到線性排序的效率。

       2.插入排序一般來(lái)說(shuō)是低效的秉颗， 因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位痢毒，步長(zhǎng)的選擇是希爾排序的重要部分。只要最終步長(zhǎng)為1任何步長(zhǎng)序列都可以工作蚕甥。
     * @param list
     */
    public static void shellSort(int[] list) {
        int gap = list.length / 2;
        while (1 <= gap) {
            // 把距離為 gap 的元素編為一個(gè)組哪替，掃描所有組
            for (int i = gap; i < list.length; i++) {
                int j = 0;
                int temp = list[i];
                // 對(duì)距離為 gap 的元素組進(jìn)行排序
                for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
                    list[j + gap] = list[j];
                }
                list[j + gap] = temp;
            }
            System.out.format("gap = %d:\t", gap);
            gap = gap / 2; // 減小增量
        }
        prints("希爾排序結(jié)果", list);

    }
    //----------------------------------------------------------------------------------------------------------------

    // 用于輸出快速排序的結(jié)果
    public static void quicksortResult(int data[]) {
        int len = data.length;
        quicksort(data, 0, len - 1);
        prints("快速排序結(jié)果", data);
    }

    /**
     * 
     * 快速排序算法的步驟：

       1.從數(shù)列中挑出一個(gè)元素，稱為 "基準(zhǔn)"菇怀，重新排序數(shù)列凭舶，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）爱沟。

       2.遞歸地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序帅霜。

       3.遞歸的最底部情形，是數(shù)列的大小是零或一呼伸，也就是永遠(yuǎn)都已經(jīng)被排序好了身冀。
       
     * 1．i =L; j = R; 將基準(zhǔn)數(shù)挖出形成第一個(gè)坑a[i]。
     * 
     * 2．j--由后向前找比它小的數(shù)括享，找到后挖出此數(shù)填前一個(gè)坑a[i]中搂根。
     * 
     * 3．i++由前向后找比它大的數(shù)，找到后也挖出此數(shù)填到前一個(gè)坑a[j]中铃辖。
     * 
     * 4．再重復(fù)執(zhí)行2剩愧，3二步，直到i==j娇斩，將基準(zhǔn)數(shù)填入a[i]中仁卷。
     * 
     * @param data
     * @param l
     * @param r
     */
    public static void quicksort(int data[], int l, int r) {
        if (l < r) {
            // Swap(s[l], s[(l + r) / 2]); //將中間的這個(gè)數(shù)和第一個(gè)數(shù)交換 參見(jiàn)注1
            int i = l, j = r, x = data[l];
            while (i < j) {
                while (i < j && data[j] >= x) // 從右向左找第一個(gè)小于x的數(shù)
                    j--;
                if (i < j)
                    data[i++] = data[j];

                while (i < j && data[i] < x) // 從左向右找第一個(gè)大于等于x的數(shù)
                    i++;
                if (i < j)
                    data[j--] = data[i];
            }
            data[i] = x;
            quicksort(data, l, i - 1); // 遞歸調(diào)用
            quicksort(data, i + 1, r);
        }
    }
    //-----------------------------------------------------------------------------------------------------
    //將元素array[k]自下往上逐步調(diào)整樹(shù)形結(jié)構(gòu)
     private static void adjustDownToUp(int[] array,int k,int length){
            int temp = array[k]; 
            //判斷該數(shù)組最后的根節(jié)點(diǎn)是否有右孩子,有的話下面 2*k+1 左孩子的值要小于 length-1
            if((length-2)%2!=0){
                length =length -1;
            }
             //i為初始化為節(jié)點(diǎn)k的左孩子，沿節(jié)點(diǎn)較大的子節(jié)點(diǎn)向下調(diào)整
                 for(int i=2*k+1; i<length; i=2*i+1){    
                     //當(dāng)末端根節(jié)點(diǎn)有右孩子 i這時(shí)小于 length-1,以下語(yǔ)句肯定會(huì)執(zhí)行
                     //但如果沒(méi)有右孩子犬第，則是左孩子小于 length,當(dāng)滿足i=length-1 的情況是五督，以下語(yǔ)句不執(zhí)行
                    if(i!=length-1 && array[i]<array[i+1]){  
                        //取節(jié)點(diǎn)較大的子節(jié)點(diǎn)的下標(biāo)
                        //如果節(jié)點(diǎn)的右孩子>左孩子，則取右孩子節(jié)點(diǎn)的下標(biāo)
                        i++;   
                    }
                    if(temp>=array[i]){  //根節(jié)點(diǎn) >=左右子女中關(guān)鍵字較大者瓶殃，調(diào)整結(jié)束
                        break;
                    }else{   //根節(jié)點(diǎn) <左右子女中關(guān)鍵字較大者
                        array[k] = array[i];  //將左右子結(jié)點(diǎn)中較大值array[i]調(diào)整到雙親節(jié)點(diǎn)上
                        k = i; //【關(guān)鍵】修改k值，以便繼續(xù)向下調(diào)整
                    }
                }
                
            
            array[k] = temp;  //被調(diào)整的結(jié)點(diǎn)的值放人最終位置
        }
            

     /**
      * 堆排序
      * 移除位在第一個(gè)數(shù)據(jù)的根結(jié)點(diǎn)副签，并做最大堆調(diào)整的遞歸運(yùn)算遥椿。
      * @param list
      */
    public static void heapSort(int[] list) {

       //從最后一個(gè)節(jié)點(diǎn)array.length-1的父節(jié)點(diǎn)（array.length-1-1）/2開(kāi)始基矮，直到根節(jié)點(diǎn)0，反復(fù)調(diào)整堆
        for(int i=(list.length-2)/2;i>=0;i--){ 
            adjustDownToUp(list, i,list.length);   
        }
        // 進(jìn)行n-1次循環(huán)冠场，完成排序

        for (int i = list.length - 1; i > 0; i--) {

            // 最后一個(gè)元素和第一元素進(jìn)行交換

            int temp = list[i];

            list[i] = list[0];

            list[0] = temp;

            // 篩選 R[0] 結(jié)點(diǎn)家浇，得到i-1個(gè)結(jié)點(diǎn)的堆

            adjustDownToUp(list, 0, i);
        }
        prints("堆排序結(jié)果",list);
    }
    //-------------------------------------------------------------------------------------------------------------
    
    /**
     * 桶排序
     * @param a
     * @param max
     */
    public static void bucketSort(int[] a, int max) {
    int[] buckets;

    if (a==null || max<1)
        return ;

    // 創(chuàng)建一個(gè)容量為max的數(shù)組buckets，并且將buckets中的所有數(shù)據(jù)都初始化為0碴裙。
    buckets = new int[max];

    // 1. 計(jì)數(shù)
    for(int i = 0; i < a.length; i++) 
        buckets[a[i]]++; 

    // 2. 排序
    for (int i = 0, j = 0; i < max; i++) {
        while( (buckets[i]--) >0 ) {
            a[j++] = i;
        }
    }

    buckets = null;
    prints("桶排序結(jié)果", a);
}
    //------------------------------------------------------------------------------------------------------------------

    /**
     * 歸并排序（Merge）是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表钢悲，
     * 即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的舔株。
     * 然后再把有序子序列合并為整體有序序列莺琳。
     * @param data
     */
    public static void mergeSort(int[] data){
        int[] temp =new int[data.length];
        internalMergeSort(data, temp, 0, data.length-1);
        prints("歸并排序結(jié)果", data);
    }
    private static void internalMergeSort(int[] a, int[] b, int left, int right){
        //當(dāng)left==right的時(shí)，已經(jīng)不需要再劃分了
        if (left<right){
            int middle = (left+right)/2;
            internalMergeSort(a, b, left, middle);          //左子數(shù)組
            internalMergeSort(a, b, middle+1, right);       //右子數(shù)組
            mergeSortedArray(a, b, left, middle, right);    //合并兩個(gè)子數(shù)組
        }
    }
    // 合并兩個(gè)有序子序列 arr[left, ..., middle] 和 arr[middle+1, ..., right]载慈。temp是輔助數(shù)組惭等。
    private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
        int i=left;     
        int j=middle+1;
        int k=0;
        while ( i<=middle && j<=right){
            if (arr[i] <=arr[j]){
                temp[k++] = arr[i++];
            }
            else{
                temp[k++] = arr[j++];
            }
        }
        while (i <=middle){
            temp[k++] = arr[i++];
        }
        while ( j<=right){
            temp[k++] = arr[j++];
        }
        //把數(shù)據(jù)復(fù)制回原數(shù)組
        for (i=0; i<k; ++i){
            arr[left+i] = temp[i];
        }
    }
    //------------------------------------------------------------------------------------------------------------------
    
    //輸出結(jié)果，驗(yàn)證正確性
    public static void prints(String str, int[] data) {
        System.out.println(str);
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < data.length; i++) {
            // System.out.print(data[i]+",");
            sb.append(data[i] + ",");
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb);
        if (sb.toString().equals(result)) {
            System.out.println("和預(yù)期結(jié)果一致");
            System.out.println();
        } else {
            System.out.println("排序有誤");
            System.out.println();
        }
    }
    
    /**
     * 交換data數(shù)組中下標(biāo)為i和j元素的位置
     * @param data
     * @param i
     * @param j
     */
    public static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}