前言

本文總結(jié)了常用的全部排序算法，內(nèi)容包括：

排序算法的定義和思路
排序算法的代碼實現(xiàn)：Python和Java，包括實現(xiàn)中需要注意的細節(jié)
排序算法性能分析：時間空間復雜度分析，穩(wěn)定排序算法背誦口訣等
不同排序算法最佳使用場景

此文干貨頗多，煩請收藏后慢慢研讀。

-----正文開始-----

算法性能分析

圖中糾正：歸并排序空間復雜度應該是O(n)，快排是O(logn)-O(n)

這里寫圖片描述

穩(wěn)定性定義：

假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

例如，對于如下冒泡排序算法，原本是穩(wěn)定的排序算法，如果將記錄交換的條件改成r[j]>=r[j+1]，則兩個相等的記錄就會交換位置，從而變成不穩(wěn)定的算法。

再如，快速排序原本是不穩(wěn)定的排序方法，但若待排序記錄中只有一組具有相同關(guān)鍵碼的記錄，而選擇的軸值恰好是這組相同關(guān)鍵碼中的一個，此時的快速排序就是穩(wěn)定的。

只需記住一句話（快些選一堆美女一起玩兒）是不穩(wěn)定的，其他都是穩(wěn)定的。

補充性能圖：

這里寫圖片描述

不同情況下的合適排序方法

初始數(shù)據(jù)越無序，快速排序越好。

已經(jīng)基本有序時，用直接插入排序最快。

在隨機情況下，快速排序是最佳選擇。

既要節(jié)省空間，又要有較快的排序速度，堆排序是最佳選擇，其不足之處是建堆時需要消耗較多時間。

若希望排序是穩(wěn)定的，且有較快的排序速度，則可選用2路歸并排序，其缺點需要較大的輔助空間分配。

算法實現(xiàn)

基于比較的排序算法

冒泡排序

思路：

冒泡排序的原理非常簡單，它重復地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。

步驟：

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對第0個到第n-1個數(shù)據(jù)做同樣的工作。這時，最大的數(shù)就“浮”到了數(shù)組最后的位置上。
針對所有的元素重復以上的步驟，除了最后一個。
持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

Python:

def bubble_sort(array):
    n = len(array)
    for i in range(n):  # i從0到n
        for j in range(1, n-i):  # 1開始，即j-1=0開始
            if array[j-1] > array[j]:
                array[j-1], array[j] = array[j], array[j-1]
    return array
#優(yōu)化1：某一趟遍歷如果沒有數(shù)據(jù)交換，則說明已經(jīng)排好序了，因此不用再進行迭代了。
#用一個標記記錄這個狀態(tài)即可。
def bubble_sort2(ary):
    n = len(ary)
    for i in range(n):
        flag = 1                    #標記
        for j in range(1,n-i):
            if  ary[j-1] > ary[j] :
                ary[j-1],ary[j] = ary[j],ary[j-1]
                flag = 0
        if flag :                   #全排好序了，直接跳出
            break
    return ary
#優(yōu)化2：記錄某次遍歷時最后發(fā)生數(shù)據(jù)交換的位置，這個位置之后的數(shù)據(jù)顯然已經(jīng)有序了。
# 因此通過記錄最后發(fā)生數(shù)據(jù)交換的位置就可以確定下次循環(huán)的范圍了。
def bubble_sort3(ary):
    n = len(ary)
    k = n                           #k為循環(huán)的范圍，初始值n
    for i in range(n):
        flag = 1
        for j in range(1,k):        #只遍歷到最后交換的位置即可
            if  ary[j-1] > ary[j] :
                ary[j-1],ary[j] = ary[j],ary[j-1]
                k = j               #記錄最后交換的位置
                flag = 0
        if flag :
            break
    return ary

Java:

public void bubble_sort(int [] a) {
        int n = a.length;
        for(int i=0;i<n;i++) {
            for(int j=1;j<n-i;j++) {
                if (a[j-1] > a[j]) {
                    int temp = a[j-1];
                    a[j-1] = a[j];
                    a[j] = temp;
                }
            }
        }
    }
//兩種優(yōu)化不寫了

選擇排序

思路：

選擇排序無疑是最簡單直觀的排序。它的工作原理如下。

步驟：

在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?。
再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。
以此類推，直到所有元素均排序完畢。

Python:

def selection_sort(array):
    n = len(array)
    for i in range(n):
        minIndex = i
        for j in range(i+1, n):
            if array[j] < array[minIndex]:
                minIndex = j
        array[i], array[minIndex] = array[minIndex], array[i]
# 或者使用minNum存儲數(shù)值,避免每次都讀array[minIndex]，但如果每次都存儲新的minNum，也會有損耗。
def selection_sort(array):
    n = len(array)
    for i in range(n):
        minNum = array[i]
        minIndex = i
        for j in range(i+1, n):
            if array[j] < minNum:
                minIndex = j
                minNum = array[j]
        array[i], array[minIndex] = array[minIndex], array[i]

Java：

public void selection_sort(int [] a) {
        int n = a.length;
        for(int i=0;i<n;i++) {
            int minIndex = i;
            for(int j=i;j<n;j++) {
                if (a[j] < a[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;  
        }
    }

插入排序

思路：

從左邊第二個數(shù)開始，往前遍歷，將大于他的數(shù)都往后一個個移位，一旦發(fā)現(xiàn)小于等于他的數(shù)，就放在那個位置（之前的數(shù)已經(jīng)被移到后面一位了）

插入排序的工作原理是，對于每個未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應位置并插入。

步驟：

從第一個元素開始，該元素可以認為已經(jīng)被排序
取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
如果被掃描的元素（已排序）大于新元素，將該元素后移一位
重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
將新元素插入到該位置后
重復步驟2~5

image

Python：

def insert_sort(array):
    n = len(array)
    for i in range(1,n): # 從第二個數(shù)開始
        if array[i-1] > array[i]:  # 前面比后面大，需要調(diào)整位置
            num = array[i]
            index = i
            for j in range(i-1, -1, -1):
                if array[j] > num:
                    array[j+1] = array[j]
                    index = j
                else:  # 找到位置，插入
                    array[index] = num
                    break

Java：

public void insert_sort(int [] a) {
        int n = a.length;
        for(int i=1;i<n;i++) {
            if (a[i-1] > a[i]) {
                int num = a[i];
                int index = i;
                for(int j=i-1;j>-1;j--) {
                if (a[j] > num) {
                    a[j+1] = a[j];
                    index = j;
                }
                else {
                    a[index] = num;
                    break;
                }
                }
            } 
        }
    }

希爾排序（遞減增量排序算法，實質(zhì)是分組插入排序）

思路：

希爾排序的基本思想是：將數(shù)組列在一個表中并對列分別進行插入排序，重復這過程，不過每次用更長的列（步長更長了，列數(shù)更少了）來進行。最后整個表就只有一列了。將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法，算法本身還是使用數(shù)組進行排序。

例如，假設(shè)有這樣一組數(shù)，

[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]

如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應該看起來是這樣：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我們對每列進行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

將上述四行數(shù)字，依序接在一起時我們得到：

[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]

。這時10已經(jīng)移至正確位置了，然后再以3為步長進行排序：

排序之后變?yōu)椋?/p>

最后以1步長進行排序（此時就是簡單的插入排序了）。

具體實現(xiàn)：外面套一個gap，while內(nèi)做插入排序，并且將gap不斷除2，直到小于0出循環(huán)

Python：

def shell_sort(ary):
    n = len(ary)
    gap = round(n/2)  # 初始步長 , 用round取整(注意0.5向下取)
    while gap > 0 :
        for i in range(gap,n):  # 每一列進行插入排序 , 從gap 到 n-1
            temp = ary[i]
            index = i
            while ( index >= gap and ary[index-gap] > temp ):  # 插入排序
                ary[index] = ary[index-gap]
                index = index - gap
            ary[index] = temp
        gap = round(gap/2)  # 重新設(shè)置步長
    return ary

Java：

public void shell_sort(int [] a) {
        int n = a.length;
        int gap = n / 2;
        while (gap > 0) {
            for (int i=gap;i<n;i++) {
                int temp = a[i];
                int j = i;
                while (j>=gap && a[j-gap] > temp) {
                    a[j] = a[j-gap];
                    j = j - gap; 
                    }
                a[j] = temp;
            }
        gap = gap / 2;
        }
    }

歸并排序(遞歸合并)

思路：拆拆拆到單個數(shù)字，合并合并合并

歸并排序是采用分治法的一個非常典型的應用。歸并排序的思想就是先遞歸分解數(shù)組，再合并數(shù)組。

先考慮合并兩個有序數(shù)組，基本思路是比較兩個數(shù)組的最前面的數(shù)，誰小就先取誰，取了后相應的指針就往后移一位。然后再比較，直至一個數(shù)組為空，最后把另一個數(shù)組的剩余部分復制過來即可。

再考慮遞歸分解，基本思路是將數(shù)組分解成left和right，如果這兩個數(shù)組內(nèi)部數(shù)據(jù)是有序的，那么就可以用上面合并數(shù)組的方法將這兩個數(shù)組合并排序。如何讓這兩個數(shù)組內(nèi)部是有序的？可以再二分，直至分解出的小組只含有一個元素時為止，此時認為該小組內(nèi)部已有序。然后合并排序相鄰二個小組即可。

image

Python：

def merge_sort(array):  # 遞歸
    if len(array) <= 1: return array  # python每次都是新的數(shù)組，可以用數(shù)組長度小于等于1來判斷
    num = len(array) // 2  # py27 3/2和3//2相同,python3 3//2才是地板除
    left = merge_sort(array[:num])
    right = merge_sort(array[num:])
    return merge(left, right)

def merge(left, right):  # 合并
    l,r = 0,0
    result = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l = l + 1
        else:
            result.append(right[r])
            r += 1
    # 一邊沒有之后，加上所有的
    result += left[l:]
    result += right[r:]
    return result

Java：

//注意：新建的temp長度和原數(shù)組是一樣的，所以額外空間是O（n），temp數(shù)組一開始并未賦值，在合并時慢慢給其填充數(shù)值，所以說一共只有一個temp數(shù)組
public void mergeSort(int[] arr) {
        mergeSort(arr, new int[arr.length], 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left < right) {  // Java則通過左右指針來判斷
            int center = (left + right) / 2;
            mergeSort(arr, temp, left, center); // 左邊
            mergeSort(arr, temp, center + 1, right); // 右邊
            merge(arr, temp, left, center + 1, right); // 合并兩個有序
        }
    }
    private static void merge(int[] arr, int[] temp, int leftPos, int rightPos, int rightEnd) {
        int leftEnd = rightPos - 1; // 左邊結(jié)束下標
        int tempPos = leftPos; // 從左邊開始算
        int numEle = rightEnd - leftPos + 1; // 元素個數(shù)
        while (leftPos <= leftEnd && rightPos <= rightEnd) {
            if (arr[leftPos] <= arr[rightPos])
                temp[tempPos++] = arr[leftPos++];
            else
                temp[tempPos++] = arr[rightPos++];
        }
        while (leftPos <= leftEnd) {  // 左邊如果有剩余
            temp[tempPos++] = arr[leftPos++];
        }
        while (rightPos <= rightEnd) { // 右邊如果有剩余
            temp[tempPos++] = arr[rightPos++];
        }
        // 將temp復制到arr，覆蓋原來這里的位置
        for (int i = 0; i < numEle; i++) {
            arr[rightEnd] = temp[rightEnd];
            rightEnd--;
        }
    }

快速排序

快速排序通常明顯比同為Ο(n log n)的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多筆試面試中能經(jīng)?？吹娇炫诺挠白印？梢娬莆湛炫诺闹匾?。

快排特點：

每經(jīng)過一趟快排，軸點元素都必然就位，也就是說，一趟下來至少有關(guān)鍵字key節(jié)點在其最終位置，所以考察各個選項，看有幾個元素就位即可。
逆序的數(shù)列，選擇首位為key，則會退化到O（n^2），可以隨機選擇一個元素作為基準元素。

兩種交換方法：

指針交換法：youtube視頻：https://www.youtube.com/watch?v=gl_XQHTJ5hY （下圖代碼實現(xiàn)的方法，并且是兩兩交換，最后將key與left交換）

image

挖坑填數(shù)法：http://blog.csdn.net/morewindows/article/details/6684558 （key一開始就被挖坑填寫了別的數(shù)，我認為第二種是做?？途W(wǎng)選擇題時需要掌握的，應為選擇題答案的排序結(jié)果通常是按照這種算法得到的排序結(jié)果）

快排優(yōu)化方法：

https://blog.csdn.net/cpcpcp123/article/details/52739285

選擇基準的方式：三數(shù)取中（median-of-three）

舉例：待排序序列為：8 1 4 9 6 3 5 2 7 0

左邊為：8，右邊為0，中間為6.

我們這里取三個數(shù)排序后，中間那個數(shù)作為樞軸，則樞軸為6

下圖分別對應第一種和第二種排序的中間結(jié)果：

這里寫圖片描述

Python(指針交換)：

def quick_sort(ary):
    return _quick_sort(ary, 0, len(ary)-1)
def _quick_sort(ary, left, right):
    if left >= right: return ary
    key = ary[left]  # 每次都選最左邊為key
    lp = left
    rp = right
    while (lp < rp):
        while ary[rp] >= key and lp < rp:
            rp -= 1
        while ary[lp] <= key and lp < rp:
            lp += 1
        ary[lp], ary[rp] = ary[rp], ary[lp]
    ary[left], ary[lp] = ary[lp], ary[left]  # 這里不能用key，是交換數(shù)組內(nèi)數(shù)字
    _quick_sort(ary, left, lp-1)
    _quick_sort(ary, lp+1, right)  # 這里lp, rp永遠是相等的。所以都可以。
    return ary

Java(指針交換)：

public void quick_sort(int[] ary) {
        _quick_sort(ary, 0, ary.length-1);
    }
    public void _quick_sort(int[] ary, int left, int right) {
        if (left < right) { 
            int key = ary[left];
            int lp = left;
            int rp = right;
            while (lp < rp) {
                while (ary[rp] >= key && lp < rp ) {
                    rp--;
                }
                while (ary[lp] <= key && lp < rp ) {
                    lp++;
                }
                int temp = ary[lp];
                ary[lp] = ary[rp];
                ary[rp] = temp;
            }
            int temp = ary[lp];
            ary[lp] = ary[left];
            ary[left] = temp;
            _quick_sort(ary, left, lp-1);
            _quick_sort(ary, rp+1, right);
        }
    }

Java(挖坑法)

非遞歸形式實現(xiàn)（棧）：和剛才的遞歸實現(xiàn)相比，代碼的變動僅僅在quickSort方法當中。該方法中引入了一個存儲Map類型元素的棧，用于存儲每一次交換時的起始下標和結(jié)束下標。

每一次循環(huán)，都會讓棧頂元素出棧，進行排序，并且按照基準元素的位置分成左右兩部分，左右兩部分再分別入棧。當棧為空時，說明排序已經(jīng)完畢，退出循環(huán)。

該方法實現(xiàn)代碼請參考程序員小灰：

https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653195042&idx=1&sn=2b0915cd2298be9f2163cc90a3d464da&chksm=8c99f9f8bbee70eef627d0f5e5b80a604221abb3a1b5617b397fa178582dcb063c9fb6f904b3&mpshare=1&scene=1&srcid=0813k35KHoSO42jGGrMx5oUA#rd

堆排序

參考：

http://blog.csdn.net/minxihou/article/details/51850001

https://www.2cto.com/kf/201609/549335.html

例題：相當幫助理解

https://www.nowcoder.com/test/question/done?tid=14276624&qid=56294#summary

image

思路：

父節(jié)點i的左子節(jié)點在位置(2i+1)*

父節(jié)點i的右子節(jié)點在位置(2i+2)*

子節(jié)點i的父節(jié)點在位置floor((i-1)/2)

堆排序構(gòu)建堆的時間復雜度是N,而重調(diào)堆的時間復雜度是logN

堆可以分為大根堆和小根堆，這里用最大堆的情況來定義操作:

(1)最大堆調(diào)整(MAX_Heapify):

將堆的末端子節(jié)點作調(diào)整，使得子節(jié)點永遠小于父節(jié)點。這是核心步驟，在建堆和堆排序都會用到。比較i的根節(jié)點和與其所對應i的孩子節(jié)點的值。當i根節(jié)點的值比左孩子節(jié)點的值要小的時候，就把i根節(jié)點和左孩子節(jié)點所對應的值交換，當i根節(jié)點的值比右孩子的節(jié)點所對應的值要小的時候，就把i根節(jié)點和右孩子節(jié)點所對應的值交換。然后再調(diào)用堆調(diào)整這個過程，可見這是一個遞歸的過程。

(2)建立最大堆(Build_Max_Heap):

將堆所有數(shù)據(jù)重新排序。建堆的過程其實就是不斷做最大堆調(diào)整的過程，從len/2出開始調(diào)整，一直比到第一個節(jié)點。

(3)堆排序(HeapSort):

移除位在第一個數(shù)據(jù)的根節(jié)點，并做最大堆調(diào)整的遞歸運算。堆排序是利用建堆和堆調(diào)整來進行的。首先先建堆，然后將堆的根節(jié)點選出與最后一個節(jié)點進行交換，然后將前面len-1個節(jié)點繼續(xù)做堆調(diào)整的過程。直到將所有的節(jié)點取出，對于n個數(shù)我們只需要做n-1次操作。堆是用順序表存儲的的代碼可以先看：http://blog.51cto.com/ahalei/1427156 就能理解代碼中的操作

注意：

從小到大排序的時候不建立最小堆而建立最大堆。最大堆建立好后，最大的元素在h[ 1]。因為我們的需求是從小到大排序，希望最大的放在最后。因此我們將h[ 1]和h[ n]交換，此時h[ n]就是數(shù)組中的最大的元素。

請注意，交換后還需將h[1]向下調(diào)整以保持堆的特性。OK現(xiàn)在最大的元素已經(jīng)歸位，需要將堆的大小減1即n--，然后再將h[1]和h[ n]交換，并將h[1]向下調(diào)整。如此反復，直到堆的大小變成1為止。此時數(shù)組h中的數(shù)就已經(jīng)是排序好的了。

代碼如下：

Python:

def MAX_Heapify(heap, HeapSize, root):  # 在堆中做結(jié)構(gòu)調(diào)整使得父節(jié)點的值大于子節(jié)點

    left = 2 * root + 1
    right = left + 1
    larger = root
    if left < HeapSize and heap[larger] < heap[left]:
        larger = left
    if right < HeapSize and heap[larger] < heap[right]:  # 確定到底和左還是右節(jié)點換，先判斷做節(jié)點
        larger = right
    if larger != root:  # 如果做了堆調(diào)整：則larger的值等于左節(jié)點或者右節(jié)點的，這個時候做對調(diào)值操作
        heap[larger],heap[root] = heap[root],heap[larger]
        MAX_Heapify(heap, HeapSize, larger)  # 從頂端遞歸往下調(diào)整，用larger是因為larger是數(shù)組索引，并且已經(jīng)在比較時候更新過，而root沒有更新過！

def Build_MAX_Heap(heap):  # 構(gòu)造一個堆，將堆中所有數(shù)據(jù)重新排序
    HeapSize = len(heap)
    for i in range(((HeapSize-1）-1)//2,-1,-1):  # 從后往前出數(shù)(z最后一個節(jié)點的父節(jié)點)  '//' got integer
        MAX_Heapify(heap,HeapSize,i)  # 這里堆的大小是固定，root是i逐步減小

def HeapSort(heap):  # 將根節(jié)點取出與最后一位做對調(diào)，對前面len-1個節(jié)點繼續(xù)進行對調(diào)整過程。
    Build_MAX_Heap(heap)
    for i in range(len(heap)-1,-1,-1):
        heap[0],heap[i] = heap[i],heap[0]
        MAX_Heapify(heap, i, 0)  # 這里堆的大小是逐步縮小，root永遠是0
    return heap

Java：

有空補

非基于比較的排序算法

基于比較的排序算法是不能突破O(NlogN)的。簡單證明如下：

N個數(shù)有N!個可能的排列情況，也就是說基于比較的排序算法的判定樹有N!個葉子結(jié)點，比較次數(shù)至少為log(N!)=O(NlogN)(斯特林公式)。

計數(shù)排序

計數(shù)排序在輸入n個0到k之間的整數(shù)時(可以從a到b，不用非要從0開始，代碼可以實現(xiàn))，

時間復雜度最好情況下為O(n+k),最壞情況下為O(n+k),平均情況為O(n+k),空間復雜度為O(n+k)

算法的步驟如下：

1.找出待排序的數(shù)組中最大和最小的元素

2.統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項

3.對所有的計數(shù)累加（從C中的第一個元素開始，每一項和前一項相加）

4.反向填充目標數(shù)組：將每個元素i放在新數(shù)組的第C(i)項，每放一個元素就將C(i)減去1

當k不是很大時，這是一個很有效的線性排序算法。更重要的是，它是一種穩(wěn)定排序算法，即排序后的相同值的元素原有的相對位置不會發(fā)生改變(表現(xiàn)在Order上)，這是計數(shù)排序很重要的一個性質(zhì)，就是根據(jù)這個性質(zhì)，我們才能把它應用到基數(shù)排序。

# -*- coding:utf-8 -*-
def count_sort(ary):
    max=min=0  # min和max應該用sys.maxint
    for i in ary:
        if i < min:
            min = i
        if i > max:
            max = i 
    count = [0] * (max - min +1)
    for index in ary:
        count[index-min]+=1
    index=0
    for a in range(max-min+1):
        for c in range(count[a]):  # 重點：有多少個就for循環(huán)多少次
            ary[index]=a+min
            index+=1
    return ary

桶排序

假如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。這些數(shù)據(jù)全部在1—100之間。因此我們定制10個桶，然后確定映射函數(shù)f(k)=k/10。則第一個關(guān)鍵字49將定位到第4個桶中(49/10=4)。依次將所有關(guān)鍵字全部堆入桶中，并在每個非空的桶中進行快速排序。

因此，我們需要盡量做到下面兩點：

(1) 映射函數(shù)f(k)能夠?qū)個數(shù)據(jù)平均的分配到M個桶中，這樣每個桶就有[N/M]個數(shù)據(jù)量。

(2) 盡量的增大桶的數(shù)量。極限情況下每個桶只能得到一個數(shù)據(jù)，這樣就完全避開了桶內(nèi)數(shù)據(jù)的“比較”排序操作。當然，做到這一點很不容易，數(shù)據(jù)量巨大的情況下，f(k)函數(shù)會使得桶集合的數(shù)量巨大，空間浪費嚴重。這就是一個時間代價和空間代價的權(quán)衡問題了。

對于N個待排數(shù)據(jù)，M個桶，平均每個桶[N/M]個數(shù)據(jù)的桶排序平均時間復雜度為：
O(N)+O(M(N/M)log(N/M))=O(N+N(logN-logM))=O(N+NlogN-N*logM)
當N=M時，即極限情況下每個桶只有一個數(shù)據(jù)時。桶排序的最好效率能夠達到O(N)。

桶排序是穩(wěn)定的。

基數(shù)排序

基數(shù)排序的思想就是將待排數(shù)據(jù)中的每組關(guān)鍵字依次進行桶分配。比如下面的待排序列：

278、109、063、930、589、184、505、269、008、083

我們將每個數(shù)值的個位，十位，百位分成三個關(guān)鍵字： 278 -> k1(個位)=8 ，k2(十位)=7 ，k3=(百位)=2。

然后從最低位個位開始(從最次關(guān)鍵字開始)，對所有數(shù)據(jù)的k1關(guān)鍵字進行桶分配(因為，每個數(shù)字都是 0-9的，因此桶大小為10)，再依次輸出桶中的數(shù)據(jù)得到下面的序列。

930、063、083、184、505、278、008、109、589、269

再對上面的序列接著進行針對k2的桶分配，輸出序列為：

505、008、109、930、063、269、278、083、184、589

最后針對k3的桶分配，輸出序列為：

008、063、083、109、184、269、278、505、589、930

很明顯，基數(shù)排序的性能比桶排序要略差。每一次關(guān)鍵字的桶分配都需要O(N)的時間復雜度，而且分配之后得到新的關(guān)鍵字序列又需要O(N)的時間復雜度。假如待排數(shù)據(jù)可以分為d個關(guān)鍵字，則基數(shù)排序的時間復雜度將是O(d*2N) ，當然d要遠遠小于N，因此基本上還是線性級別的。基數(shù)排序的空間復雜度為O(N+M)，其中M為桶的數(shù)量。一般來說N>>M，因此額外空間需要大概N個左右。

但是，對比桶排序，基數(shù)排序每次需要的桶的數(shù)量并不多。而且基數(shù)排序幾乎不需要任何“比較”操作，而桶排序在桶相對較少的情況下，桶內(nèi)多個數(shù)據(jù)必須進行基于比較操作的排序。因此，在實際應用中，基數(shù)排序的應用范圍更加廣泛。

參考

穩(wěn)定性解釋：
https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%A8%B3%E5%AE%9A%E6%80%A7/9763250?fr=aladdin

性能分析與適應場景：
http://blog.csdn.net/p10010/article/details/49557763

動畫：
http://blog.csdn.net/tobeandnottobe/article/details/7192953
http://www.webhek.com/post/comparison-sort.html

Python排序總結(jié)：
http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/

Java排序總結(jié)：
https://www.cnblogs.com/10158wsj/p/6782124.html?utm_source=tuicool&utm_medium=referral

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

排序算法最強總結(jié)及其代碼實現(xiàn)（Python/Java）

排序算法最強總結(jié)及其代碼實現(xiàn)（Python/Java）

前言

-----正文開始-----

算法性能分析

不同情況下的合適排序方法

算法實現(xiàn)

基于比較的排序算法

冒泡排序

選擇排序

插入排序

希爾排序（遞減增量排序算法，實質(zhì)是分組插入排序）

歸并排序(遞歸合并)

快速排序

堆排序

非基于比較的排序算法

計數(shù)排序

桶排序

基數(shù)排序

參考

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

排序算法最強總結(jié)及其代碼實現(xiàn)（Python/Java）

前言

-----正文開始-----

算法性能分析

不同情況下的合適排序方法

算法實現(xiàn)

基于比較的排序算法

冒泡排序

選擇排序

插入排序

希爾排序（遞減增量排序算法，實質(zhì)是分組插入排序）

歸并排序(遞歸合并)

快速排序

堆排序

非基于比較的排序算法

計數(shù)排序

桶排序

基數(shù)排序

參考

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

希爾排序（遞減增量排序算法，實質(zhì)是分組插入排序）