對(duì)于編程算法，可能很多讀者在學(xué)校***個(gè)了解的就是冒泡排序，但是你真的知道 Python 內(nèi)建排序算法 list.sort() 的原理嗎?它使用的是一種快速、穩(wěn)定的排序算法 Timsort，其時(shí)間復(fù)雜度為 O(n log n)，該算法的目標(biāo)在于處理大規(guī)模真實(shí)數(shù)據(jù)。

Timsort 是一種對(duì)真實(shí)數(shù)據(jù)非常有效的排序算法。Tim Peters 在 2001 年為 Python 編程語(yǔ)言創(chuàng)造了 Timsort。Timsort 首先分析它要排序的列表，然后基于該分析選擇合理方案。

Timsort 自發(fā)明以來(lái)，就成為 Python、Java 、Android 平臺(tái)和 GNU Octave 的默認(rèn)排序算法。

圖源：http://bigocheatsheet.com/

Timsort 的排序時(shí)間與 Mergesort 相近，快于其他大多數(shù)排序算法。Timsort 實(shí)際上借鑒了插入排序和歸并排序的方法，后文將詳細(xì)介紹它的具體過(guò)程。

Peters 設(shè)計(jì) Timsort 是為了利用大量存在于現(xiàn)實(shí)數(shù)據(jù)集中的有序元素，這些有序元素被稱為「natural runs」?？偠灾?，Timsort 會(huì)先遍歷所有數(shù)據(jù)并找到數(shù)據(jù)中已經(jīng)排好序的分區(qū)，且每一個(gè)分區(qū)可以稱為一個(gè) run，***再按規(guī)則將這些 run 歸并為一個(gè)。

數(shù)組中元素少于 64 個(gè)

如果排序的數(shù)組中元素少于 64 個(gè)，那么 Timsort 將執(zhí)行插入排序。插入排序是對(duì)小型列表最有效的簡(jiǎn)單排序，它在大型列表中速度很慢，但是在小型列表中速度很快。插入排序的思路如下：

• 逐個(gè)查看元素
• 通過(guò)在正確的位置插入元素來(lái)建立排序列表

下面的跟蹤表說(shuō)明了插入排序如何對(duì)列表 [34, 10, 64, 51, 32, 21] 進(jìn)行排序的：

在這個(gè)示例中，我們將從左向右開(kāi)始排序，其中黑體數(shù)字表示新的已排序子數(shù)組。在原數(shù)組每一個(gè)元素的排序中，它會(huì)從右到左對(duì)比已排序子數(shù)組，并插入適當(dāng)?shù)奈恢?。用?dòng)圖來(lái)說(shuō)明插入排序：

天然有序的區(qū)塊：run

如果列表大于 64 個(gè)元素，則 Timsort 算法首先遍歷列表，查找「嚴(yán)格」升序或降序的部分(Run)。如果一個(gè)部分遞減，Timsort 將逆轉(zhuǎn)這個(gè)部分。因此，如果 run 遞減，則如下圖所示(run 用粗體表示)：

如果沒(méi)有遞減，則如下圖所示：

minrun 的大小是根據(jù)數(shù)組大小確定的。Timsort 算法選擇它是為了使隨機(jī)數(shù)組中的大部分 run 變成 minrun。當(dāng) run N 的長(zhǎng)度等于或略小于 2 的倍數(shù)時(shí)，歸并 2 個(gè)數(shù)組更加高效。Timsort 選擇 minrun 是為了確保 minrun 等于或稍微小于 2 的倍數(shù)。

該算法選擇 minrun 的范圍為 32 ~ 64。當(dāng)除以 minrun 時(shí)，使原始數(shù)組的長(zhǎng)度等于或略小于 2 的倍數(shù)。

如果 run 的長(zhǎng)度小于 minrun，則計(jì)算 minrun 減去 run 的長(zhǎng)度。我們可以將 run 之外的新元素(minrun - run 個(gè))放到 run 的后面，并執(zhí)行插入排序來(lái)創(chuàng)建新的 run，這個(gè)新的 run 長(zhǎng)度和 minrun 相同。

如果 minrun 是 63，而 run 的長(zhǎng)度是 33，那么可以獲取 63 - 33 = 30 個(gè)新元素。然后將這 30 個(gè)新元素放到 run 的末尾并作為新的元素，所以 run 的第 34 個(gè)元素 run[33] 有 30 個(gè)子元素。***只需要對(duì)后面 30 個(gè)元素執(zhí)行一個(gè)插入排序就能創(chuàng)建一個(gè)長(zhǎng)度為 63 的新 run。

在這一部分完成之后，現(xiàn)在應(yīng)該在一個(gè)列表中有一系列已排序的 run。

歸并

Timsort 現(xiàn)在需要執(zhí)行歸并排序來(lái)合并 run，需要確保在歸并排序的同時(shí)保持穩(wěn)定和平衡。為了保持穩(wěn)定，兩個(gè)等值的元素不應(yīng)該交換，這不僅保持了它們?cè)诹斜碇械脑嘉恢?，而且使算法更快?/p>

當(dāng) Timsort 搜索到 runs 時(shí)，它們會(huì)被添加到堆棧中。一個(gè)簡(jiǎn)單的堆棧是這樣的：

想象一堆盤子。你不能從底部取盤子，必須從頂部取，堆棧也是如此。

當(dāng)歸并不同的 run 時(shí)，Timsort 試圖平衡兩個(gè)相互矛盾的需求。一方面，我們希望盡可能地延遲歸并，以便利用之后可能出現(xiàn)的模式。但我們更希望盡快歸并，以利用剛才發(fā)現(xiàn)的在內(nèi)存層級(jí)中仍然排名很高的 run。我們也不能「過(guò)分」延遲合并，因?yàn)樗涀∥春喜⒌倪\(yùn)行需要消耗內(nèi)存，而堆棧的大小是固定的。

為了得到折衷方案，Timsort 追蹤堆棧上最近的三個(gè)項(xiàng)，并為這些堆棧項(xiàng)創(chuàng)建了兩個(gè)必須保持為 True 的規(guī)則：

• A > B + C
• B > C

其中 A、B 和 C 是堆棧中最近的三個(gè)項(xiàng)。

用 Tim Peters 自己的話來(lái)說(shuō)：

通常，將不同長(zhǎng)度的相鄰 run 歸并在一起是很難的。更困難的是還必須要保持穩(wěn)定。為了解決這個(gè)問(wèn)題，Timsort 設(shè)置了臨時(shí)內(nèi)存。它將兩個(gè) run 中較小的(同時(shí)調(diào)用 runA 和 runB)放在這個(gè)臨時(shí)內(nèi)存中。

GALLOPING(飛奔模式)

當(dāng) Timsort 歸并 A 和 B 時(shí)，它注意到一個(gè) run 已經(jīng)連續(xù)多次「獲勝」。如果 run A 的數(shù)值完全小于 run B，那么 run A 會(huì)回到原始位置。歸并這兩個(gè) run 會(huì)耗費(fèi)巨大工作量，而且還不會(huì)取得任何效果。

通常情況下，數(shù)據(jù)會(huì)有一些預(yù)設(shè)的內(nèi)部結(jié)構(gòu)。Timsort 假設(shè)，如果 run A 中的值大多低于 run B 的值，那么 A 的值可能就會(huì)小于 B。

然后 Timsort 將進(jìn)入飛奔模式。Timsort 不是檢查 A[0] 和 B[0]，而是二分法搜索 B[0] 在 A[0] 中的合理位置。這樣，Timsort 可以將 A 的整個(gè)部分移動(dòng)到合適的位置。然后，Timsort 在 B 中搜索 A[0] 的適當(dāng)位置。然后，Timsort 將立即移動(dòng)整個(gè) B 到合適的位置。

Timsort 檢查 B[0](值為 5)，并使用二分法搜索查找其 A 中的正確位置。

現(xiàn)在 B[0] 在 A 列表的后面，Timsort 檢查 B 的正確位置是否有 A[0](即 1)，所以我們要看 1 的位置。這個(gè)數(shù)在 B 的前部，現(xiàn)在我們知道 B 在 A 的后邊，A 在 B 的前邊。

如果 B[0] 的位置非常接近 A 的前端(反之亦然)，那么這個(gè)操作就沒(méi)必要了。Timsort 也會(huì)注意到這一點(diǎn)，并通過(guò)增加連續(xù)獲得 A 或 B 的數(shù)量提高進(jìn)入飛奔模式的門檻。如果飛奔模式合理，Timsort 使它更容易重新進(jìn)入該模式。

簡(jiǎn)而言之，Timsort 做了兩件非常好的事情：

• 具有預(yù)設(shè)的內(nèi)部結(jié)構(gòu)的數(shù)組具有良好的性能
• 能夠保持穩(wěn)定的排序

在此之前，為了實(shí)現(xiàn)穩(wěn)定的排序，必須將列表中的項(xiàng)壓縮為整數(shù)，并將其排序?yàn)樵M數(shù)組。

代碼

下面的源代碼基于我和 Nanda Javarma 的工作。源代碼并不完整，也不是類似于 Python 的官方 sort() 源代碼。這只是我實(shí)現(xiàn)的一個(gè)簡(jiǎn)化的 Timsort，可以對(duì) Timsort 有個(gè)整體把握。此外，Python 中的內(nèi)置 Timsort 算法是在 C 中正式實(shí)現(xiàn)的，因此能獲得更好的性能。

Timsort 的原始源代碼：

https://github.com/python/cpython/blob/master/Objects/listobject.c。

# based off of this code https://gist.github.com/nandajavarma/a3a6b62f34e74ec4c31674934327bbd3 
# Brandon Skerritt 
# https://skerritt.tech 
 
def binary_search(the_array, item, start, end): 
    if start == end: 
        if the_array[start] > item: 
            return start 
        else: 
            return start + 1 
    if start > end: 
        return start 
 
    mid = round((start + end)/ 2) 
 
    if the_array[mid] < item: 
        return binary_search(the_array, item, mid + 1, end) 
 
    elif the_array[mid] > item: 
        return binary_search(the_array, item, start, mid - 1) 
 
    else: 
        return mid 
 
""" 
Insertion sort that timsort uses if the array size is small or if 
the size of the "run" is small 
""" 
def insertion_sort(the_array): 
    l = len(the_array) 
    for index in range(1, l): 
        value = the_array[index] 
        pos = binary_search(the_array, value, 0, index - 1) 
        the_arraythe_array = the_array[:pos] + [value] + the_array[pos:index] + the_array[index+1:] 
    return the_array 
 
def merge(left, right): 
    """Takes two sorted lists and returns a single sorted list by comparing the 
    elements one at a time. 
    [1, 2, 3, 4, 5, 6] 
    """ 
    if not left: 
        return right 
    if not right: 
        return left 
    if left[0] < right[0]: 
        return [left[0]] + merge(left[1:], right) 
    return [right[0]] + merge(left, right[1:]) 
 
def timsort(the_array): 
    runs, sorted_runs = [], [] 
    lenlength = len(the_array) 
    new_run = [the_array[0]] 
 
    # for every i in the range of 1 to length of array 
    for i in range(1, length): 
        # if i is at the end of the list 
        if i == length - 1: 
            new_run.append(the_array[i]) 
            runs.append(new_run) 
            break 
        # if the i'th element of the array is less than the one before it 
        if the_array[i] < the_array[i-1]: 
            # if new_run is set to None (NULL) 
            if not new_run: 
                runs.append([the_array[i]]) 
                new_run.append(the_array[i]) 
            else: 
                runs.append(new_run) 
                new_run = [] 
        # else if its equal to or more than 
        else: 
            new_run.append(the_array[i]) 
 
    # for every item in runs, append it using insertion sort 
    for item in runs: 
        sorted_runs.append(insertion_sort(item)) 
 
    # for every run in sorted_runs, merge them 
    sorted_array = [] 
    for run in sorted_runs: 
        sorted_array = merge(sorted_array, run) 
 
    print(sorted_array) 
 
timsort([2, 3, 1, 5, 6, 7]) 

Timsort 實(shí)際上在 Python 中已經(jīng)內(nèi)建了，所以這段代碼只充當(dāng)概念解釋。要使用 Timsort，只需在 Python 中寫：

list.sort() 

或者：

sorted(list) 

如果你想掌握 Timsort 的工作方式并對(duì)其有所了解，我強(qiáng)烈建議你嘗試自己實(shí)現(xiàn)它!

原文鏈接：

https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399

【本文是51CTO專欄機(jī)構(gòu)“機(jī)器之心”的原創(chuàng)譯文，微信公眾號(hào)“機(jī)器之心( id: almosthuman2014)”】

戳這里，看該作者更多好文