八大常用排序算法詳細(xì)分析 包括復(fù)雜度，原理和實(shí)現(xiàn)如下：

20161010095439425.jpg

1. 冒泡排序

1.1 算法原理：

S1：從待排序序列的起始位置開始纯蛾，從前往后依次比較各個(gè)位置和其后一位置的大小并執(zhí)行S2纤房。S2：如果當(dāng)前位置的值大于其后一位置的值，就把他倆的值交換（完成一次全序列比較后翻诉，序列最后位置的值即此序列最大值炮姨，所以其不需要再參與冒泡）。S3：將序列的最后位置從待排序序列中移除碰煌。若移除后的待排序序列不為空則繼續(xù)執(zhí)行S1舒岸，否則冒泡結(jié)束。
1.2 算法實(shí)現(xiàn)（Java）：
1.2.1 基礎(chǔ)實(shí)現(xiàn)：

public static void bubbleSort(int[] array) {
    int len = array.length;
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
            }
        }
    }
}

1.2.2 算法優(yōu)化：

若某一趟排序中未進(jìn)行一次交換芦圾，則排序結(jié)束

public static void bubbleSort(int[] array) {
    int len = array.length;
    boolean flag = true;
    while (flag) {
        flag = false;
        for (int i = 0; i < len - 1; i++) {
            if (array[i] > array[i + 1]) {
                int temp = array[i + 1];
                array[i + 1] = array[j];
                array[i] = temp;
                flag = true;
            }
        }
        len--;
    }
}

2. 快速排序

2.1 算法原理：

快速排序是對(duì)冒泡排序的一種改進(jìn)蛾派。基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分个少，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小洪乍，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行夜焦，以此實(shí)現(xiàn)整個(gè)數(shù)據(jù)變成有序序列壳澳。

2.2 算法實(shí)現(xiàn)（Java）：

public static void quickSort(int[] array, int left, int right) {
    if (left < right) {
        int pivot = array[left];
        int low = left;
        int high = right;
        while (low < high) {
            while (low < high && array[high] >= pivot) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= pivot) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = pivot;
        quickSort(array, left, low - 1);
        quickSort(array, low + 1, right);
    }
}

3. 直接插入排序

3.1 算法原理：

插入排序的基本方法是：每步將一個(gè)待排序序列按數(shù)據(jù)大小插到前面已經(jīng)排序的序列中的適當(dāng)位置，直到全部數(shù)據(jù)插入完畢為止糊探。假設(shè)有一組無序序列R0
,R1
, … ,Rn?1
：(1) 將這個(gè)序列的第一個(gè)元素R0視為一個(gè)有序序列钾埂；(2) 依次把R1
,R2
, … ,Rn?1
插入到這個(gè)有序序列中；(3) 將Ri
插入到有序序列中時(shí)科平，前 i-1 個(gè)數(shù)是有序的褥紫，將Ri
和R0
~Ri?1
從后往前進(jìn)行比較，確定要插入的位置瞪慧。

3.2 算法實(shí)現(xiàn)（Java）：

public static void insertSort(int[] array) {
    for (int i = 1, len = array.length; i < len; i++) {
        if (array[i] < array[i - 1]) {
            int temp = array[i];
            int j;
            for (j = i - 1; j >= 0 && temp < array[j]; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = temp;
        }
 
    }
}

4. Shell排序

4.1 算法原理：

希爾排序是一種插入排序算法髓考，又稱作縮小增量排序。是對(duì)直接插入排序算法的改進(jìn)弃酌。其基本思想是：
先取一個(gè)小于n的整數(shù)h1作為第一個(gè)增量氨菇，把全部數(shù)據(jù)分成h1個(gè)組儡炼。所有距離為h1的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序查蓉；然后乌询，取第二個(gè)增量h2重復(fù)上述的分組和排序，直至所取的增量ht=1(ht豌研，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹姑锰铩Ｔ摲椒▽?shí)質(zhì)上是一種分組插入方法。

4.2 算法實(shí)現(xiàn)（Java）：

public static void shellSort(int[] array) {
    int n = array.length;
    int h;
    for (h = n / 2; h > 0; h /= 2) {
        for (int i = h; i < n; i++) {
            for (int j = i - h; j >= 0; j -= h) {
                if (array[j] > array[j + h]) {
                    int temp = array[j];
                    array[j] = array[j + h];
                    array[j + h] = temp;
                }
            }
        }
    }
}

5. 直接選擇排序

5.1 算法原理：

直接選擇排序是一種簡(jiǎn)單的排序方法鹃共，它的基本思想是：第一次從R[0]_{R[n-1]中選取最小值鬼佣，與R[0]交換，第二次從R[1]}R[n-1]中選取最小值霜浴，與R[1]交換晶衷，….，第i次從R[i-1]_{R[n-1]中選取最小值阴孟，與R[i-1]交換晌纫，…..，第n-1次從R[n-2]}R[n-1]中選取最小值温眉，與R[n-2]交換缸匪，共通過n-1次翁狐，得到一個(gè)從小到大排列的有序序列类溢。

5.2 算法實(shí)現(xiàn)（Java）：

public static void selectSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (array[minIndex] > array[j]) {
                minIndex = j;
            }
        }
        if (i != minIndex) {
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }
}

6. 堆排序

6.1 算法原理：

6.1.1 二叉堆定義：

二叉堆是完全二叉樹或近似完全二叉樹。二叉堆滿足兩個(gè)特性：??1）父結(jié)點(diǎn)的鍵值總是大于或等于（小于或等于）任何一個(gè)子節(jié)點(diǎn)的鍵值露懒。??2）每個(gè)結(jié)點(diǎn)的左子樹和右子樹都是一個(gè)二叉堆闯冷。當(dāng)父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為大根堆。當(dāng)父結(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為小根堆懈词。下面展示一個(gè)小根堆：

這里寫圖片描述

堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法崎脉，它是選擇排序的一種拧咳。可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素囚灼。堆分為大根堆和小根堆骆膝，是完全二叉樹祭衩。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值，即A[PARENT[i]] >= A[i]阅签，小根堆則相反掐暮。堆排序利用了大根堆（或小根堆）堆頂記錄的關(guān)鍵字最大（或最小）這一特征政钟，使得在當(dāng)前無序區(qū)中選取最大（或最薪俾摇）關(guān)鍵字的記錄變得簡(jiǎn)單。（1）用大根堆排序的基本思想??① 先將初始數(shù)組
R1...Rn
建成一個(gè)大根堆锥涕，此堆為初始的無序區(qū)??② 再將最大的元素R1
（即堆頂）和無序區(qū)的最后一個(gè)記錄Rn
交換衷戈，由此得到新的無序區(qū)R1...Rn?1
和有序區(qū)Rn
，且滿足R1...Rn?1
的值<=Rn
的值层坠。??③由于交換后新的根R1
可能違反堆性質(zhì)殖妇，故應(yīng)將當(dāng)前無序區(qū)R1...Rn?1
調(diào)整為堆。然后再次將R1...Rn?1
中最大的元素R1
和該區(qū)間的最后一個(gè)記錄Rn?1
交換破花，由此得到新的無序區(qū)R1...Rn?2
和有序區(qū)Rn?1...Rn
谦趣，且仍滿足關(guān)系R1...Rn?2
的值<=Rn?1...Rn
的值，同樣要將R1...Rn?2
調(diào)整為堆座每∏岸欤……直到無序區(qū)只有一個(gè)元素為止。（2）大根堆排序算法的基本操作：??①建堆峭梳，建堆是不斷調(diào)整堆的過程舰绘，從len/2處開始調(diào)整，一直到第一個(gè)節(jié)點(diǎn)葱椭，此處len是堆中元素的個(gè)數(shù)捂寿。建堆的過程是線性的過程，從len/2到0處一直調(diào)用調(diào)整堆的過程孵运，相當(dāng)于o(h1)+o(h2)…+o(hlen/2) 其中h表示節(jié)點(diǎn)的深度秦陋，len/2表示節(jié)點(diǎn)的個(gè)數(shù)，這是一個(gè)求和的過程治笨，結(jié)果是線性的O(n)驳概。??②調(diào)整堆：調(diào)整堆在構(gòu)建堆的過程中會(huì)用到，而且在堆排序過程中也會(huì)用到旷赖。利用的思想是比較節(jié)點(diǎn)i和它的孩子節(jié)點(diǎn)left(i),right(i)顺又，選出三者最大(或者最小)者，如果最大（懈芾ⅰ）值不是節(jié)點(diǎn)i而是它的一個(gè)孩子節(jié)點(diǎn)待榔，那邊交互節(jié)點(diǎn)i和該節(jié)點(diǎn)，然后再調(diào)用調(diào)整堆過程，這是一個(gè)遞歸的過程锐锣。調(diào)整堆的過程時(shí)間復(fù)雜度與堆的深度有關(guān)系腌闯，是lgn的操作，因?yàn)槭茄刂疃确较蜻M(jìn)行調(diào)整的雕憔。??③堆排序：堆排序是利用上面的兩個(gè)過程來進(jìn)行的姿骏。首先是根據(jù)元素構(gòu)建堆。然后將堆的根節(jié)點(diǎn)取出(一般是與最后一個(gè)節(jié)點(diǎn)進(jìn)行交換)斤彼，將前面len-1個(gè)節(jié)點(diǎn)繼續(xù)進(jìn)行堆調(diào)整的過程分瘦，然后再將根節(jié)點(diǎn)取出，這樣一直到所有節(jié)點(diǎn)都取出琉苇。

6.2 算法實(shí)現(xiàn)（Java）：

public static void heapSort(int[] array) {
    // 1. 創(chuàng)建最大堆：從最后一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)開始
    int lastIndex = array.length - 1;
    int startIndex = (lastIndex - 1) / 2;
    for (int i = startIndex; i >= 0; i--) {
        maxHeap(sort, sort.length, i);
    }
    // 2. 排序：末尾與頭交換嘲玫，逐一找出最大值，最終形成一個(gè)遞增的有序序列
    for (int i = array.length - 1; i > 0; i--) {
        int temp = array[0];
        array[0] = array[i];
        array[i] = temp;
        maxHeap(array, i, 0);
    }
}
 
private static void maxHeap(int[] data, int heapSize, int index) {
    // 左子節(jié)點(diǎn)
    int leftChild = 2 * index + 1;
    // 右子節(jié)點(diǎn)
    int rightChild = 2 * index + 2;
    // 最大元素下標(biāo)
    int largestIndex = index;
    // 分別比較當(dāng)前節(jié)點(diǎn)和左右子節(jié)點(diǎn)并扇，找出最大值
    if (leftChild < heapSize && data[leftChild] > data[largestIndex]) {
        largestIndex = leftChild;
    }
    if (rightChild < heapSize && data[rightChild] > data[largestIndex]) {
        largestIndex = rightChild;
    }
    // 如果最大值是子節(jié)點(diǎn)去团，則進(jìn)行交換
    if (largestIndex != index) {
        int temp = data[index];
        data[index] = data[largestIndex];
        data[largestIndex] = temp;
        // 交換后，其子節(jié)點(diǎn)可能就不是最大堆了穷蛹，需要對(duì)交換的子節(jié)點(diǎn)重新調(diào)整
        maxHeap(data, heapSize, largestIndex);
    }
}

7. 歸并排序

7.1 算法原理：

歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個(gè)非常典型的應(yīng)用土陪。將已有序的子序列合并，得到完全有序的序列肴熏；即先使每個(gè)子序列有序鬼雀，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表蛙吏，稱為二路歸并源哩。歸并過程為：??比較a[i]和a[j]的大小，若a[i]≤a[j]出刷，則將第一個(gè)有序表中的元素a[i]復(fù)制到r[k]中璧疗，并令i和k分別加上1；否則將第二個(gè)有序表中的元素a[j]復(fù)制到r[k]中馁龟，并令j和k分別加上1，如此循環(huán)下去漆魔，直到其中一個(gè)有序表取完坷檩，然后再將另一個(gè)有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)t的單元。歸并排序的算法我們通常用遞歸實(shí)現(xiàn)改抡，先把待排序區(qū)間[s,t]以中點(diǎn)二分矢炼，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序阿纤，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]句灌。歸并操作的工作原理如下：??S1: 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列??S2: 設(shè)定兩個(gè)指針胰锌，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置??S3: 比較兩個(gè)指針?biāo)赶虻脑仄疲x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置??S4: 重復(fù)S3资昧，直到某一指針超出序列尾??S5: 將另一序列剩下的所有元素直接復(fù)制到合并序列尾

7.2 算法實(shí)現(xiàn)（Java）：

public static void mergeSort(int[] array, int low, int high) {
    int middle = (low + high) / 2;
    if (low < high) {
        mergeSort(array, low, middle);
        mergeSort(array, middle + 1, high);
        merge(array, low, middle, high);
    }
}
 
public static void merge(int[] array, int low, int middle, int high) {
    int[] temp = new int[high - low + 1];
    int i = low;
    int j = middle + 1;
    int k = 0;
    while (i <= middle && j <= high) {
        if (array[i] < array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }
    while (i <= middle) {
        temp[k++] = array[i++];
    }
    while (j <= high) {
        temp[k++] = array[j++];
    }
    for (int m = 0; m < temp.length; m++) {
        array[m + low] = temp[m];
    }
}

8. 基數(shù)排序

8.1 算法原理：

基數(shù)排序的原理如下：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長(zhǎng)度酬土，數(shù)位較短的數(shù)前面補(bǔ)零。然后格带，從最低位開始撤缴，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個(gè)有序序列叽唱∏唬基數(shù)排序的方式有以下兩種：??最高位優(yōu)先(Most Significant Digit first)法，簡(jiǎn)稱MSD法：先按k1
排序分組棺亭，同一組中記錄凉袱，關(guān)鍵碼k1
相等，再對(duì)各組按k2
排序分成子組侦铜，之后专甩，對(duì)后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd
對(duì)各子組排序后钉稍。再將各組連接起來涤躲，便得到一個(gè)有序序列。??最低位優(yōu)先(Least Significant Digit first)法贡未，簡(jiǎn)稱LSD法：先從kd
開始排序种樱，再對(duì)kd?1
進(jìn)行排序，依次重復(fù)俊卤，直到對(duì)k1
排序后便得到一個(gè)有序序列嫩挤。

8.2 算法實(shí)現(xiàn)（Java）：

public static void radixSort(int[] array, int d) {
    int n = 1;
    int times = 1; // 排序次數(shù)，由位數(shù)最多的元素決定
    int[][] temp = new int[10][array.length]; //數(shù)組的第一維表示可能的余數(shù)0-9
    int[] order = new int[10]; //數(shù)組order用來表示該位是i的元素個(gè)數(shù)
    while (times <= d) {
        for (int i = 0; i < array.length; i++) {
            int lsd = ((array[i] / n) % 10);
            temp[lsd][order[lsd]] = array[i];
            order[lsd]++;
        }
        int k = 0;
        for (int i = 0; i < 10; i++) {
            if (order[i] != 0) {
                for (int j = 0; j < order[i]; j++) {
                    array[k] = temp[i][j];
                    k++;
                }
                order[i] = 0;
            }
        }
        n *= 10;
        times++;
    }
}