您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

TimSort 排序算法簡易版實現與原理解析

編輯：Java 綜合教學

TimSort 算法簡介

TimSort 是 Python 和 Java 中對象數組的默認排序算法。其本質是歸並排序，但在標準歸並排序基礎上進行了大量優化。現實數據往往部分有序或部分逆序，TimSort 充分利用這些已有序片段進行歸並，大幅提升效率。

本文提供一個簡易版 TimSort 實現，主要包含三大優化策略：

1. 利用原有有序片段

規定最小歸並長度 MIN_MERGE = 16。掃描數組中的天然有序片段（升序或降序），若長度小於最小歸並長度，則用插入排序擴充該片段。將有序片段的起始索引和長度壓入棧中管理。

2. 避免長短片段歸並效率低

維護一個棧存儲有序片段，遵循以下合併規則：

若棧中有至少三個片段 X、Y、Z（棧頂向下），滿足 X + Y >= Z 時觸發合併：
- 若 X 最長，先合併 Y 和 Z，再壓入 X
- 否則合併 X 和 Y
若不滿足上述條件或僅有兩個片段 X、Y，當 X >= Y 時合併

實際編碼中不會真正出棧，而是用技巧達到同等效果。

3. 飛奔模式優化歸並

合併兩個有序片段 X 和 Y 時：

若 X 前 m 個元素都小於 Y 首元素，這 m 個元素無需參與歸並
若 Y 後 n 個元素都大於 X 尾元素，這 n 個元素也可跳過

簡易版未實現此優化，完整版會用二分查找定位邊界，減少數據拷貝。

Java 完整源碼實現

package datastruct;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class SimpleTimSort<T extends Comparable<? super T>> {
    private static final int MIN_MERGE = 16;
    private final T[] a;
    private T[] aux;
    private int[] runsBase = new int[40];
    private int[] runsLen = new int[40];
    private int stackTop = 0;

    @SuppressWarnings("unchecked")
    public SimpleTimSort(T[] a) {
        this.a = a;
        aux = (T[]) Array.newInstance(a[0].getClass(), a.length);
    }

    // 插入排序擴充有序片段
    private void insertSort(T[] a, int from, int to, int n) {
        int i = to + 1;
        while (n > 0) {
            T tmp = a[i];
            int j;
            for (j = i - 1; j >= from && tmp.compareTo(a[j]) < 0; j--) {
                a[j + 1] = a[j];
            }
            a[++j] = tmp;
            i++;
            n--;
        }
    }

    // 獲取從 from 開始的最長有序片段長度（含逆序轉換）
    private int maxAscendingLen(T[] a, int from) {
        int n = 1, i = from;
        if (i >= a.length) return 0;
        if (i == a.length - 1) return 1;
        
        if (a[i].compareTo(a[i + 1]) < 0) { // 升序
            while (i + 1 <= a.length - 1 && a[i].compareTo(a[i + 1]) <= 0) {
                i++; n++;
            }
            return n;
        } else { // 降序（嚴格 > 保證穩定性）
            while (i + 1 <= a.length - 1 && a[i].compareTo(a[i + 1]) > 0) {
                i++; n++;
            }
            // 逆序翻轉
            int j = from;
            while (j < i) {
                T tmp = a[i]; a[i] = a[j]; a[j] = tmp;
                j++; i--;
            }
            return n;
        }
    }

    private void pushRun(int base, int len) {
        runsBase[stackTop] = base;
        runsLen[stackTop] = len;
        stackTop++;
    }

    // 判斷是否需要合併，返回合併位置或 -1
    public int needMerge() {
        if (stackTop > 1) {
            int x = stackTop - 2;
            if (x > 0 && runsLen[x - 1] <= runsLen[x] + runsLen[x + 1]) {
                if (runsLen[x - 1] < runsLen[x + 1]) return --x;
                else return x;
            } else if (runsLen[x] <= runsLen[x + 1]) {
                return x;
            } else return -1;
        }
        return -1;
    }

    // 飛奔模式：二分查找邊界（簡易版用線性查找）
    private int gallopLeft(T[] a, int base, int len, T key) {
        int i = base;
        while (i <= base + len - 1) {
            if (key.compareTo(a[i]) >= 0) i++;
            else break;
        }
        return i;
    }

    private int gallopRight(T[] a, int base, int len, T key) {
        int i = base + len - 1;
        while (i >= base) {
            if (key.compareTo(a[i]) <= 0) i--;
            else break;
        }
        return i;
    }

    // 合併棧中位置 x 和 x+1 的片段
    public void mergeAt(int x) {
        int base1 = runsBase[x], len1 = runsLen[x];
        int base2 = runsBase[x + 1], len2 = runsLen[x + 1];
        
        runsLen[x] = len1 + len2;
        if (stackTop == x + 3) { // 棧頂下移，避免出棧入棧
            runsBase[x + 1] = runsBase[x + 2];
            runsLen[x + 1] = runsLen[x + 2];
        }
        stackTop--;
        
        // 飛奔模式縮小合併範圍
        int from = gallopLeft(a, base1, len1, a[base2]);
        if (from == base1 + len1) return;
        int to = gallopRight(a, base2, len2, a[base1 + len1 - 1]);
        
        System.arraycopy(a, from, aux, from, to - from + 1);
        int i = from, iend = base1 + len1 - 1;
        int j = base2, jend = to;
        int k = from, kend = to;
        
        while (k <= kend) {
            if (i > iend) a[k] = aux[j++];
            else if (j > jend) a[k] = aux[i++];
            else if (aux[i].compareTo(aux[j]) <= 0) a[k] = aux[i++]; // 穩定性
            else a[k] = aux[j++];
            k++;
        }
    }

    private void forceMerge() {
        while (stackTop > 1) mergeAt(stackTop - 2);
    }

    public void timSort() {
        int n = a.length;
        if (n < 2) return;
        if (n < MIN_MERGE) {
            insertSort(a, 0, 0, a.length - 1);
            return;
        }
        
        int base = 0;
        while (n > 0) {
            int len = maxAscendingLen(a, base);
            if (len < MIN_MERGE) {
                int abscent = n > MIN_MERGE ? MIN_MERGE - len : n - len;
                insertSort(a, base, base + len - 1, abscent);
                len += abscent;
            }
            pushRun(base, len);
            n -= len;
            base += len;
            int x;
            while ((x = needMerge()) >= 0) mergeAt(x);
        }
        forceMerge();
    }

    public static void main(String[] args) {
        Random rnd = new Random(System.currentTimeMillis());
        boolean flag = true;
        while (flag) {
            // 生成近乎有序的測試數據
            Integer[] arr1 = new Integer[1000];
            for (int i = 0; i < arr1.length; i++) arr1[i] = i;
            // 10% 隨機交換
            for (int i = 0; i < (int)(0.1 * arr1.length); i++) {
                int x = rnd.nextInt(arr1.length), y = rnd.nextInt(arr1.length);
                int tmp = arr1[x]; arr1[x] = arr1[y]; arr1[y] = tmp;
            }
            // 5% 逆序片段
            for (int i = 0; i < (int)(0.05 * arr1.length); i++) {
                int x = rnd.nextInt(arr1.length);
                int y = rnd.nextInt((int)(arr1.length * 0.01) + x);
                if (y >= arr1.length) continue;
                while (x < y) {
                    int tmp = arr1[x]; arr1[x] = arr1[y]; arr1[y] = tmp;
                    x++; y--;
                }
            }
            
            Integer[] arr2 = arr1.clone();
            Integer[] arr3 = arr1.clone();
            Arrays.sort(arr2);
            
            SimpleTimSort<Integer> sts = new SimpleTimSort<>(arr1);
            sts.timSort();
            
            if (!Arrays.deepEquals(arr1, arr2)) {
                for (int i = 0; i < arr1.length; i++) {
                    if (!arr1[i].equals(arr2[i])) {
                        System.out.printf("%d: arr1 %d arr2 %d\n", i, arr1[i], arr2[i]);
                    }
                }
                System.out.println(Arrays.deepToString(arr3));
                flag = false;
            }
        }
    }
}