對(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ā)明以來，就成為 Python、Java 、Android 平臺(tái)和 GNU Octave 的默認(rèn)排序算法。

 

 

圖源：http://bigocheatsheet.com/

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

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è)查看元素

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

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

 

 

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

 

 

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

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

 

 

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

 

 

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í)行插入排序來創(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í)行歸并排序來合并 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。我們也不能「過分」延遲合并，因?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 自己的話來說：

一個(gè)好的折衷方案是在堆棧項(xiàng)上維護(hù)兩個(gè)不變量，其中 A、B 和 C 是最右邊三個(gè)還未歸并片段的長(zhǎng)度。

通常，將不同長(zhǎng)度的相鄰 run 歸并在一起是很難的。更困難的是還必須要保持穩(wěn)定。為了解決這個(gè)問題，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]，而是二進(jìn)制搜索 B[0] 在 A[0] 中的合理位置。這樣，Timsort 可以將 A 的整個(gè)部分移動(dòng)到合適的位置。然后，Timsort 在 B 中搜索 A[0] 的適當(dāng)位置。然后，Timsort 將立即移動(dòng)整個(gè) B 到合適的位置。

Timsort 檢查 B[0](值為 5)，并使用二進(jìn)制搜索查找其 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è)操作就沒必要了。Timsort 也會(huì)注意到這一點(diǎn)，并通過增加連續(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)樵�組數(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

 

 

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

標(biāo)簽： 代碼 排名 搜索

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。