最近在復(fù)習(xí)之前看過的數(shù)據(jù)結(jié)構(gòu)和算法衬廷，發(fā)現(xiàn)當(dāng)時看的排序算法忘得差不多了，所以今天就把常用的八大排序算法的 核心代碼 再次總結(jié)以下俯画，忘記時看下就能夠回憶起來蜕径。

大部分來自 胡昭民 的《圖解數(shù)據(jù)結(jié)構(gòu)——使用Java》的讀書筆記

1.冒泡排序

分為傳統(tǒng)的，和改進(jìn)版的败京。

    /**
     * 傳統(tǒng)冒泡排序
     */
    private static void bubble(int[] data) {
        int size = data.length;//原始數(shù)組大小
        int tem; //臨時變量
        for (int i = size-1;i>0;i--) {
            for (int j = 0;j<i;j++) {
                //比較相鄰兩數(shù)兜喻，若第一數(shù)較大則交換
                if (data[j] > data[j+1]) {
                    tem = data[j];
                    data[j] = data[j+1];
                    data[j+1] = tem;
                }
            }
        }
    }

下面是改進(jìn)版的

    /**
     * 改進(jìn)的冒泡排序，如果一次比較后沒有交換 證明已排好序赡麦，直接跳出循環(huán)
     */
    private static void improvedbubble(int[] data) {
        int tem;  //臨時變量
        int flag;  //判斷是否有執(zhí)行交換的動作
        int size = data.length;//原始數(shù)組大小
        for (int i = size-1;i>0;i--) {
            flag = 0;
            for (int j = 0;j<i;j++) {
                //比較相鄰兩數(shù)朴皆，若第一數(shù)較大則交換
                if (data[j] > data[j+1]) {
                    tem = data[j];
                    data[j] = data[j+1];
                    data[j+1] = tem;
                    flag++; //執(zhí)行過交換 flag不為0
                }
            }
            if (flag == 0) {
                break;
            }
        }
    }

2.選擇排序

    /**
     * 選擇排序
     * 例如N個數(shù)據(jù)要由大到小排序時，首先以第一個位置的數(shù)據(jù)泛粹，
     * 依次向2,3,4遂铡，N個位置的數(shù)據(jù)作比較，
     * 如果數(shù)據(jù)大于或等于其中一個位置晶姊，則兩個位置的數(shù)據(jù)不變扒接，
     * 若小于，則交換
     */
    private static void selectionSort (int[] data){
        int tem;  //臨時變量
        int size = data.length;//原始數(shù)組大小
        for (int i = 0;i<size-1;i++) { //掃描size-1次
            for (int j = i+1;j<size;j++) {//由i+1比較们衙，比較size-1次
                if (data[i] > data[j]) {//比較第i及第j份元素
                    tem = data[i];
                    data[i] = data[j];
                    data[j] = tem;
                }
            }
        }
    }

3.插入排序

    /**
     * 插入排序
     * 是將數(shù)組中的元素钾怔，逐一與已排序好的數(shù)據(jù)作比較，
     * 再將該數(shù)組元素插入適當(dāng)?shù)奈恢谩?     */
    private static void insertSort(int[] data) {
        int tem;  //臨時變量
        int size = data.length;//原始數(shù)組大小
        int j;//定位比較的元素
        for (int i =1;i<size;i++) {//默認(rèn)第一個元素已排好序蒙挑，從第二個元素開始掃描宗侦，掃描size-1次
            tem = data[i];
            j = i-1; //將data[i] 與 它的前一位data[i-1] 比較
            while (j>=0 && tem<data[j]) { //若小于
                data[j+1] = data[j]; //就把所有的元素往后推一個
                j--;
            }
            data[j+1] = tem; //最小的元素 放到移動后的缺口處
        }
    }

4.希爾排序

    /**
     * 希爾排序
     * D.L.Shell 在 1959年7月發(fā)明的一種排序
     * 時間復(fù)雜度達(dá)到O(n^1.5)
     * 有點(diǎn)像插入排序，將數(shù)據(jù)區(qū)分成特定間隔的幾個小塊忆蚀，以插入排序法排完
     * 區(qū)塊內(nèi)的數(shù)據(jù)后再漸漸減少間隔距離
     */
    private static void shellSort(int[] data){
        int tem;  //臨時變量
        int jmp;  //設(shè)定間隔位移量
        int size = data.length;//原始數(shù)組大小
        int j;//定位比較的元素
        jmp = size/2; //先以數(shù)組大小的一半作為間隔位移量
        while (jmp != 0) {
            for (int i = jmp;i<size;i++) {
                tem = data[i];
                j = i - jmp;
                //下面就是插入排序了
                while (j>=0 && tem < data[j]) {
                    data[j+jmp] = data[j];
                    j = j - jmp;
                }
                data[jmp + j] = tem;
            }
            jmp = jmp/2;  //控制循環(huán)數(shù)
        }
    }

5.快速排序

    /**
     * 快速排序
     * 假設(shè)有n個記錄R1,R2,R3...Rn,鍵值為k1,k2,k3...kn
     * 1.取k為第一個鍵值
     * 2.由左向右找出一個鍵值Ki 使得Ki>K
     * 3.由右向左找出一個鍵值Kj 使得Kj<K
     * 4.若i<j 則Ki與Kj交換矾利，并繼續(xù)步驟2
     * 5.若i>=j 則將K與Kj交換，并以j為記住將數(shù)據(jù)分為左右兩部分馋袜，
     * 以遞歸方式分別對左右兩邊進(jìn)行排序男旗，直至完成排序
     */
    private static void quickSort2(int[] data,int left,int right) {
        int tem;//臨時變量
        int lf_idx;//從左向右移動的鍵
        int rg_idx;//從右向左移動的鍵
        //第一個鍵值為data[left]
        if (left < right) {
            lf_idx = left+1;
            rg_idx = right;
            //開始排序
            while (true) {
                for (int i = left+1;i<=right;i++) {//2.由左向右找出一個鍵值>data[left]者
                    if (data[i] >= data[left]) {
                        lf_idx = i;
                        break;
                    }
                    lf_idx++;
                }
                for (int j = right;j>=left+1;j--) {//3.由右向左找出一個鍵值<data[left]者
                    if (data[j] <= data[left]) {
                        rg_idx = j;
                        break;
                    }
                    rg_idx--;
                }
                if (lf_idx < rg_idx) {//4.若lf_idx < rg_idx
                    tem = data[lf_idx]; //則交換data[lf_idx]和data[rg_idx]
                    data[lf_idx] = data[rg_idx];
                    data[rg_idx] = tem;
                }else {
                    break;
                }
            }
            //整理
            if (lf_idx >= rg_idx) {  //5-1 若lf_idx >= rg_idx
                tem = data[left]; //則交換 data[left] 和 data[rg_idx]
                data[left] = data[rg_idx];
                data[rg_idx] = tem;
                //5-2 并以rg_idx為基準(zhǔn)點(diǎn)分成兩半，遞歸排序
                quickSort2(data,left,rg_idx-1);
                quickSort2(data,rg_idx+1,right);
            }
        }
    }

6.堆排序

堆排序參考了網(wǎng)上這篇文章
http://www.cnblogs.com/ttltry-air/archive/2012/08/03/2621962.html
里面有動畫欣鳖，大家可以去看下剑肯，很好看。
核心代碼在下面

    /**
     * 堆排序
     *1.建初始堆：將R[1..n]構(gòu)造為初始堆观堂；
     *2.堆調(diào)整：將當(dāng)前無序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個記錄交換让网，然后將新的無序區(qū)調(diào)整為堆呀忧。
     */
    public static void buildHeap(int a[]) {
        int heapSize = a.length;
        int filter = heapSize / 2;
        // i從第一個非葉子結(jié)點(diǎn)開始
        for (int i = filter - 1; i >= 0; i--) {
            heapAdjust(a, i, heapSize);
        }
    }

    // 已知H.r[i...heapSize]中記錄的關(guān)鍵字除H.r[i]外，均滿足最大堆結(jié)構(gòu)
    public static void heapAdjust(int arr[], int i, int heapSize) {
        // 當(dāng)前待調(diào)整的元素
        int tmp = arr[i];
        // 該元素的左孩子
        int index = 2 * i + 1;
        while (index < heapSize) {
            // 如果右孩子大于左孩子,則index+1溃睹，即交換右孩子和雙親節(jié)點(diǎn)
            if (index + 1 < heapSize && arr[index] < arr[index + 1]) {
                index = index + 1;
            }
            if (arr[i] < arr[index]) {
                arr[i] = arr[index];// 交換孩子和雙親節(jié)點(diǎn)
                i = index;// 重新賦初值
                index = 2 * i + 1;
            }
            else {
                break;// 已經(jīng)是最大堆
            }
            arr[i] = tmp;// 把雙親值賦給孩子節(jié)點(diǎn)
        }
    }

    public static void heapSort(int a[]) {
        int heapSize = a.length;
        for (int i = heapSize - 1; i > 0; i--) {
            // 交換堆頂和最后一個元素
            int tmp = a[0];
            a[0] = a[i];
            a[i] = tmp;
            // 在heapSize范圍內(nèi)根結(jié)點(diǎn)的左右子樹都已經(jīng)是最大堆,所以只需看新交換的堆頂元素是否滿足最大堆結(jié)構(gòu)即可而账。
            // 將H.r[0...i]重新調(diào)整為最大堆
            heapAdjust(a, 0, i);
        }
    }

7.歸并排序

歸并排序，我覺得維基百科講的就很不錯因篇，大家可以看看維基百科的講解https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F#Java
下面是java迭代版的核心代碼

    /**
     * 歸并排序
     */
    public static int[] merge_sort(int[] arr) {
        int len = arr.length;
        int[] result = new int[len];
        int block, start;

        for(block = 1; block < len ; block *= 2) {
            for(start = 0; start <len; start += 2 * block) {
                int low = start;
                int mid = (start + block) < len ? (start + block) : len;
                int high = (start + 2 * block) < len ? (start + 2 * block) : len;
                //兩個塊的起始下標(biāo)及結(jié)束下標(biāo)
                int start1 = low, end1 = mid;
                int start2 = mid, end2 = high;
                //開始對兩個block進(jìn)行歸并排序
                while (start1 < end1 && start2 < end2) {
                    result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
                }
                while(start1 < end1) {
                    result[low++] = arr[start1++];
                }
                while(start2 < end2) {
                    result[low++] = arr[start2++];
                }
            }
            int[] temp = arr;
            arr = result;
            result = temp;
        }
        result = arr;
        return result;
    }

8.基數(shù)排序

    /**
     * 基數(shù)排序
     * 假設(shè)每個數(shù)位數(shù)不超過3位
     */
    private static void radixSort(int[] data) {
        int size = data.length;
        int k;
        int n;
        int m;
        for (n = 1;n<=100;n = n*10) { //n為基數(shù) 從個位開始排序
            //設(shè)定暫存數(shù)組泞辐，[0~9位數(shù)][數(shù)據(jù)個數(shù)]，所有內(nèi)容均為0
            int[][] tem = new int[10][100];
            for (int i=0;i<size;i++) {   //比較所有數(shù)據(jù)
                m = (data[i]/n)%10;   //m為n位數(shù)的值
                tem[m][i] = data[i]; //把data[i]的值暫存在tem里
            }
            k=0;
            for (int i =0;i<10;i++) {
                for (int j=0;j<size;j++) {
                    if (tem[i][j] != 0) {  //一開始設(shè)定tem={0}竞滓，所以不為0證明里面有數(shù)
                        //把data暫存在tem里的值 放回data[]里
                        data[k] = tem[i][j];
                        k++;
                    }
                }
            }
        }
    }

附上一張 各種排序的總結(jié)

排序總結(jié)

參考資料

大部分來自 胡昭民 的《圖解數(shù)據(jù)結(jié)構(gòu)——使用Java》的讀書筆記
一部分來自大神網(wǎng)友的博客
https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F#Java
http://www.cnblogs.com/ttltry-air/archive/2012/08/03/2621962.html
http://www.cnblogs.com/rollenholt/archive/2012/04/15/2450175.html
http://blog.csdn.net/morewindows/article/details/6709644