除了冒泡排序，你知道Python內建的排序演算法嗎？

選自hackernoon

作者：Brandon Skerritt

機器之心編譯

參與：高璇、思源

對於編程演算法，可能很多讀者在學校第一個了解的就是冒泡排序，但是你真的知道 Python 內建排序演算法 list.sort() 的原理嗎？它使用的是一種快速、穩定的排序演算法 Timsort，其時間複雜度為 O(n log n)，該演算法的目標在於處理大規模真實數據。

Timsort 是一種對真實數據非常有效的排序演算法。Tim Peters 在 2001 年為 Python 編程語言創造了 Timsort。Timsort 首先分析它要排序的列表，然後基於該分析選擇合理方案。

Timsort 自發明以來，就成為 Python、Java 、Android 平台和 GNU Octave 的默認排序演算法。

圖源：http://bigocheatsheet.com/

Timsort 的排序時間與 Mergesort 相近，快於其他大多數排序演算法。Timsort 實際上借鑒了插入排序和歸併排序的方法，後文將詳細介紹它的具體過程。

Peters 設計 Timsort 是為了利用大量存在於現實數據集中的有序元素，這些有序元素被稱為「natural runs」。總而言之，Timsort 會先遍歷所有數據並找到數據中已經排好序的分區，且每一個分區可以稱為一個 run，最後再按規則將這些 run 歸併為一個。

數組中元素少於 64 個

如果排序的數組中元素少於 64 個，那麼 Timsort 將執行插入排序。插入排序是對小型列表最有效的簡單排序，它在大型列表中速度很慢，但是在小型列表中速度很快。插入排序的思路如下：

逐個查看元素

通過在正確的位置插入元素來建立排序列表

下面的跟蹤表說明了插入排序如何對列表 [34, 10, 64, 51, 32, 21] 進行排序的：

在這個示例中，我們將從左向右開始排序，其中黑體數字表示新的已排序子數組。在原數組每一個元素的排序中，它會從右到左對比已排序子數組，並插入適當的位置。用動圖來說明插入排序：

天然有序的區塊：run

如果列表大於 64 個元素，則 Timsort 演算法首先遍歷列表，查找「嚴格」升序或降序的部分（Run）。如果一個部分遞減，Timsort 將逆轉這個部分。因此，如果 run 遞減，則如下圖所示（run 用粗體表示）：

如果沒有遞減，則如下圖所示：

minrun 的大小是根據數組大小確定的。Timsort 演算法選擇它是為了使隨機數組中的大部分 run 變成 minrun。當 run N 的長度等於或略小於 2 的倍數時，歸併 2 個數組更加高效。Timsort 選擇 minrun 是為了確保 minrun 等於或稍微小於 2 的倍數。

該演算法選擇 minrun 的範圍為 32 ~ 64。當除以 minrun 時，使原始數組的長度等於或略小於 2 的倍數。

如果 run 的長度小於 minrun，則計算 minrun 減去 run 的長度。我們可以將 run 之外的新元素（minrun - run 個）放到 run 的後面，並執行插入排序來創建新的 run，這個新的 run 長度和 minrun 相同。

如果 minrun 是 63，而 run 的長度是 33，那麼可以獲取 63 - 33 = 30 個新元素。然後將這 30 個新元素放到 run 的末尾並作為新的元素，所以 run 的第 34 個元素 run[33] 有 30 個子元素。最後只需要對後面 30 個元素執行一個插入排序就能創建一個長度為 63 的新 run。

在這一部分完成之後，現在應該在一個列表中有一系列已排序的 run。

歸併

Timsort 現在需要執行歸併排序來合併 run，需要確保在歸併排序的同時保持穩定和平衡。為了保持穩定，兩個等值的元素不應該交換，這不僅保持了它們在列表中的原始位置，而且使演算法更快。

當 Timsort 搜索到 runs 時，它們會被添加到堆棧中。一個簡單的堆棧是這樣的：

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

當歸併不同的 run 時，Timsort 試圖平衡兩個相互矛盾的需求。一方面，我們希望儘可能地延遲歸併，以便利用之後可能出現的模式。但我們更希望儘快歸併，以利用剛才發現的在內存層級中仍然排名很高的 run。我們也不能「過分」延遲合併，因為它記住未合併的運行需要消耗內存，而堆棧的大小是固定的。

為了得到折衷方案，Timsort 追蹤堆棧上最近的三個項，並為這些堆棧項創建了兩個必須保持為 True 的規則：

A > B + C

B > C

其中 A、B 和 C 是堆棧中最近的三個項。

用 Tim Peters 自己的話來說：

一個好的折衷方案是在堆棧項上維護兩個不變數，其中 A、B 和 C 是最右邊三個還未歸併片段的長度。

通常，將不同長度的相鄰 run 歸併在一起是很難的。更困難的是還必須要保持穩定。為了解決這個問題，Timsort 設置了臨時內存。它將兩個 run 中較小的（同時調用 runA 和 runB）放在這個臨時內存中。

GALLOPING（飛奔模式）

當 Timsort 歸併 A 和 B 時，它注意到一個 run 已經連續多次「獲勝」。如果 run A 的數值完全小於 run B，那麼 run A 會回到原始位置。歸併這兩個 run 會耗費巨大工作量，而且還不會取得任何效果。

通常情況下，數據會有一些預設的內部結構。Timsort 假設，如果 run A 中的值大多低於 run B 的值，那麼 A 的值可能就會小於 B。

然後 Timsort 將進入飛奔模式。Timsort 不是檢查 A[0] 和 B[0]，而是二進位搜索 B[0] 在 A[0] 中的合理位置。這樣，Timsort 可以將 A 的整個部分移動到合適的位置。然後，Timsort 在 B 中搜索 A[0] 的適當位置。然後，Timsort 將立即移動整個 B 到合適的位置。

Timsort 檢查 B[0]（值為 5），並使用二進位搜索查找其 A 中的正確位置。

現在 B[0] 在 A 列表的後面，Timsort 檢查 B 的正確位置是否有 A[0]（即 1），所以我們要看 1 的位置。這個數在 B 的前部，現在我們知道 B 在 A 的後邊，A 在 B 的前邊。

如果 B[0] 的位置非常接近 A 的前端（反之亦然），那麼這個操作就沒必要了。Timsort 也會注意到這一點，並通過增加連續獲得 A 或 B 的數量提高進入飛奔模式的門檻。如果飛奔模式合理，Timsort 使它更容易重新進入該模式。

簡而言之，Timsort 做了兩件非常好的事情：

具有預設的內部結構的數組具有良好的性能

能夠保持穩定的排序

在此之前，為了實現穩定的排序，必須將列表中的項壓縮為整數，並將其排序為元組數組。

代碼

下面的源代碼基於我和 Nanda Javarma 的工作。源代碼並不完整，也不是類似於 Python 的官方 sort() 源代碼。這只是我實現的一個簡化的 Timsort，可以對 Timsort 有個整體把握。此外，Python 中的內置 Timsort 演算法是在 C 中正式實現的，因此能獲得更好的性能。

Timsort 的原始源代碼：https://github.com/python/cpython/blob/master/Objects/listobject.c。

Timsort 實際上在 Python 中已經內建了，所以這段代碼只充當概念解釋。要使用 Timsort，只需在 Python 中寫：

或者：

如果你想掌握 Timsort 的工作方式並對其有所了解，我強烈建議你嘗試自己實現它！

本文為機器之心編譯，轉載請聯繫本公眾號獲得授權。

------------------------------------------------

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！