1. 簡易版本TimSort排序演算法原理與實(shí)作

TimSort排序演算法是Python和Java針對物件陣列的預(yù)設(shè)排序演算法。 TimSort排序演算法的本質(zhì)是歸併排序演算法，只是在歸併排序演算法上進(jìn)行了大量的最佳化。對於日常生活中我們需要排序的資料通常不是完全隨機(jī)的，而是部分有序的，或者部分逆序的，所以TimSort充分利用已有序的部分進(jìn)行歸併排序?，F(xiàn)在我們提供一個(gè)簡易版本TimSort排序演算法，它主要做了以下最佳化:

1.1利用原本已有序的片段

首先規(guī)定一個(gè)最小歸併長度。檢查數(shù)組中原本有序的片段，如果已有序的長度小於規(guī)定的最小歸併長度，則通過插入排序?qū)σ延行虻钠芜M(jìn)行進(jìn)行擴(kuò)充（這樣做的原因避免歸併長度較小的片段，因?yàn)檫@樣的效率比較低）。將有序片段的起始索引位置和已有序的長度入堆疊。

1.2避免一個(gè)較長的有序片段和一個(gè)較小的有序片段進(jìn)行歸併，因?yàn)檫@樣的效率比較低：

（1）如果棧中存在已有序的至少三個(gè)序列，我們用X ，Y，Z依序表示從棧頂向下的三個(gè)已有序列片段，當(dāng)三者的長度滿足X+Y>=Z時(shí)進(jìn)行歸併。

?? （1.1）如果X是三者中長度最大的，先將X，Y，Z出棧，應(yīng)該先歸併Y和Z，然後將Y和Z歸併的結(jié)果入棧，最後X入棧

?? （ 1.2）否則將X和Y出棧，歸併後結(jié)果入棧。注意，實(shí)際上我們不會真正的出棧，寫程式碼中有一些技巧可以達(dá)到相同的效果，而且效率更高。

（2）如果不滿足X+Y>=Z的條件或堆疊中僅存在兩個(gè)序列，我們用X，Y依序表示從棧頂向下的兩個(gè)已有序列的長度，如果X>= Y則進(jìn)行歸併，然後將歸併後的有序片段結(jié)果入棧。

1.3在歸併兩個(gè)已有序的片段時(shí)，採用了所謂的飛奔（gallop）模式，這樣可以減少參與歸併的數(shù)據(jù)長度

假設(shè)需要?dú)w併的兩個(gè)已有序片段分別為X和Y ，如果X片段的前m個(gè)元素都比Y片段的首元素小，那麼這m個(gè)元素其實(shí)是不需要參與歸併的，因?yàn)闅w併後這m個(gè)元素仍然位於原來的位置。同理如果Y片段的最後n個(gè)元素都比X的最後一個(gè)元素大，那麼Y的最後n個(gè)元素也不必參與歸併。這樣就減少了歸併數(shù)組的長度(簡易版沒有這麼做)，也較少了待排序數(shù)組與輔助數(shù)組之間資料來回復(fù)制的長度，進(jìn)而提高了歸併的效率。

2. 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;
    //待排序數(shù)組
    private final T[] a;
    //輔助數(shù)組
    private T[] aux;
    //用兩個(gè)數(shù)組表示棧
    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);
    }
     
    //T[from, to]已有序，T[to]以后的n元素插入到有序的序列中
    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--;
        }
    }
     
    //返回從a[from]開始，的最長有序片段的個(gè)數(shù)
    private int maxAscendingLen(T[] a, int from){
        int n = 1;
        int i = from;
         
        if(i >= a.length){//超出范圍
            return 0;
        }
         
        if(i == a.length-1){//只有一個(gè)元素
            return 1;
        }
         
        //至少兩個(gè)元素
        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{//降序片段，這里是嚴(yán)格的降序，不能有>=的情況，否則不能保證穩(wěn)定性
            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表示不需要?dú)w并棧中的有序片段
    public int needMerge(){
        if(stackTop > 1){//至少兩個(gè)run序列
            int x = stackTop - 2;
            //x > 0 表示至少三個(gè)run序列
            if(x > 0 && runsLen[x-1] <= runsLen[x] + runsLen[x+1]){
                if(runsLen[x-1] < runsLen[x+1]){
                    //說明 runsLen[x+1]是runsLen[x]和runsLen[x-1]中最大的值
                    //應(yīng)該先合并runsLen[x]和runsLen[x-1]這兩段run
                    return --x;
                }else{
                    return x;
                }
            }else
            if(runsLen[x] <= runsLen[x+1]){
                return x;
            }else{
                return -1;
            }
        }
        return -1;
    }
     
    //返回后一個(gè)片段的首元素在前一個(gè)片段應(yīng)該位于的位置
    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;
    }
     
    //返回前一個(gè)片段的末元素在后一個(gè)片段應(yīng)該位于的位置
    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;
    }
     
    public void mergeAt(int x){
        int base1 = runsBase[x];
        int len1 = runsLen[x];
         
        int base2 = runsBase[x+1];
        int len2 = runsLen[x+1];
         
        //合并run[x]和run[x+1],合并后base不用變,長度需要發(fā)生變化
        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]);
         
        //對兩個(gè)需要?dú)w并的片段長度進(jìn)行歸并
        System.arraycopy(a, from, aux, from, to - from + 1);
        int i = from;
        int iend = base1 + len1 - 1;
         
        int j = base2;
        int jend = to;
         
        int k = from;
        int 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){//等號保證排序的穩(wěn)定性
                a[k] = aux[i++];
            }else{
                a[k] = aux[j++];
            }
            k++;
        }
    }
     
    //強(qiáng)制歸并已入棧的序列
    private void forceMerge(){
        while(stackTop > 1){
            mergeAt(stackTop-2);
        }
    }
     
    //timSort的主方法
    public void timSort(){
        //n表示剩余長度
        int n = a.length; 
         
        if(n < 2){
            return;
        }
         
        //待排序的長度小于MIN_MERGE,直接采用插入排序完成
        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 = len + abscent;
            }
            pushRun(base, len);
            n = n - len;
            base = base + len;
             
            int x;
            while((x  = needMerge()) >= 0 ){
                mergeAt(x);
            }
        }
        forceMerge();
    }
     
    public static void main(String[] args){
         
        //隨機(jī)產(chǎn)生測試用例
        Random rnd = new Random(System.currentTimeMillis());
        boolean flag = true;
        while(flag){
             
            //首先產(chǎn)生一個(gè)全部有序的數(shù)組
            Integer[] arr1 = new Integer[1000];
            for(int i = 0; i < arr1.length; i++){
                arr1[i] = i;
            }
             
            //有序的基礎(chǔ)上隨機(jī)交換一些值
            for(int i = 0; i < (int)(0.1*arr1.length); i++){
                int x,y,tmp;
                x = rnd.nextInt(arr1.length);
                y = rnd.nextInt(arr1.length);
                tmp = arr1[x];
                arr1[x] = arr1[y];
                arr1[y] = tmp;
            }
             
            //逆序部分?jǐn)?shù)據(jù)
            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;
                    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<Integer>(arr1);
            sts.timSort();
             
            //比較SimpleTimSort排序和庫函數(shù)提供的排序結(jié)果比較是否一致
            //如果沒有打印任何結(jié)果，說明排序結(jié)果正確
            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;
            }
        }
    }
}

3.TimSort演算法應(yīng)注意的問題

TimSort演算法只會對連續(xù)的兩個(gè)片段進(jìn)行歸併，這樣才能保證演算法的穩(wěn)定性。

最小歸併長度和棧的長度存在一定的關(guān)係，如果增大最小歸併長度，則棧的長度也應(yīng)該增大，否則可能引起棧越界的風(fēng)險(xiǎn)（代碼中棧是透過長度為40的數(shù)組來實(shí)現(xiàn)的）。

4.完整版的TimSort演算法

實(shí)際上，完整版的TimSort演算法會在上述簡易TimSort演算法上還有大量的最佳化。例如有序序列小於最小歸併長度時(shí)，我們可以利用類似二分查找的方式來找出應(yīng)該插入的位置來對陣列進(jìn)行長度擴(kuò)充。再例如飛奔模式中採用二分查找的方式查找第二個(gè)序列的首元素在第一個(gè)序列的位置，同時(shí)還可以使用較小的輔助空間完成歸併，有興趣的同學(xué)可以查看Java中的源代碼來學(xué)習(xí)。