tim排序

tim 排序是歸併排序和插入排序的結合，是一個穩定的排序算法，由 Tim Peters 於 2002 年用 Python 實現。現在，tim 排序是 Python 的標準排序算法，且被 Java SE7 用於對非原始類型的數組排序。

tim 排序在最好情況下的時間複雜度為 \(O(n)\)，最差情況下的時間複雜度為 \(O(n \log n)\)，期望時間複雜度為 \(O(n \log n)\)。tim 排序在最壞情況下的空間複雜度為 \(O(n)\)。

算法

眾所周知，歸併排序是先將數組劃分為兩部分，然後遞歸地對兩個子數組進行歸併排序，最後合併兩個子數組。這樣一來，歸併排序合併操作的最小單位就是單個元素。但是，數組中可能原本就存在連續且有序的子數組，歸併排序無法利用這個特性。

tim 排序為了利用數組中本身就存在的連續且有序的子數組，以 RUN 作為合併操作的最小單位。其中，RUN 是一個滿足以下性質的子數組：

一個 RUN 要麼是非降序的，要麼是嚴格升序的。
一個 RUN 存在一個長度的下限。

tim 排序的過程就是一個類似歸併排序的過程，將數組劃分為多個 RUN，然後以某種規則不斷地合併兩個 RUN，直到數組有序。具體過程如下：

令 \(nRemaining\) 初始化為數組的大小，\(minRun\) 初始化為 \(getMinRunLength(nRemaining)\)。

\[ \begin{array}{ll} 1 & \textbf{do}\\ 2 & \qquad \text{確定} run \text{的起點}\\ 3 & \qquad \textbf{if} run \text{比} minRun \text{短}\\ 4 & \qquad \qquad \text{延長} run \text{直至} \min(minRun, nRemaining)\\ 5 & \qquad \textbf{push} run \text{放到} pending-run stack \text{上}\\ 6 & \qquad \textbf{if} pending-run stack \text{最頂上的 2 個} run \text{長度相近}\\ 7 & \qquad \qquad \text{合併} pending-run stack \text{最頂上的 2 個} run\\ 8 & \qquad \text{start index} \gets \text{start index} + run \text{的長度}\\ 9 & \qquad nRemaining \gets nRemaining - run \text{的長度}\\ 10 & \textbf{while} \text{ } nRemaining \ne 0\\ \end{array} \]

其中，\(getMinRunLength\) 函數是根據當前數組長度確定 \(minRun\) 具體值的函數，natural run 的意思是原本就非降序或者嚴格升序的 run，擴展長度不夠的 run 就是用插入排序往 run 中添加元素。

複雜度證明

最好情況下，數組本身就有序，即數組本身就是一個 RUN，這個時候 tim 排序就遍歷了一遍數組，找到了唯一的 RUN，就結束了。所以，最好的情況下，tim 排序的時間複雜度為 \(O(n)\)。

寫在後面

本文只是簡單介紹了 tim 排序的原理，實際上 tim 排序在實現的時候還有一些其他的優化，這裏不再一一列舉。tim 排序在 java 中的實現寫得非常好，要想知道真正的 tim 排序推薦去看 java 中 tim 排序的實現。

參考資料

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Backl1ght
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用