簡易版的TimSort排序算法
1. 簡易版本TimSort排序算法原理與實現
TimSort排序算法是Python和Java針對對象數組的默認排序算法。TimSort排序算法的本質是歸并排序算法，只是在歸并排序算法上進行了大量的優化。對于日常生活中我們需要排序的數據通常不是完全隨機的，而是部分有序的，或者部分逆序的，所以TimSort充分利用已有序的部分進行歸并排序。現在我們提供一個簡易版本TimSort排序算法，它主要做了以下優化:
1.1 利用原本已有序的片段
首先規定一個最小歸并長度 。 檢查數組中原本有序的片段，如果已有序的長度小于規定的最小歸并長度，則通過插入排序對已有序的片段進行進行擴充（這樣做的原因避免歸并長度較小的片段，因為這樣的效率比較低）。將有序片段的起始索引位置和已有序的長度入棧。
1.2 避免一個較長的有序片段和一個較小的有序片段進行歸并，因為這樣的效率比較低：
（1）如果棧中存在已有序的至少三個序列，我們用X，Y，Z依次表示從棧頂向下的三個已有序列片段，當三者的長度滿足X+Y>=Z時進行歸并。
（1.1）如果X是三者中長度最大的，先將X，Y，Z出棧，應該先歸并Y和Z，然后將Y和Z歸并的結果入棧，最后X入棧
（1.2）否則將X和Y出棧，歸并后結果入棧。注意，實際上我們不會真正的出棧，寫代碼中有一些技巧可以達到相同的效果，而且效率更高。
（2）如果不滿足X+Y>=Z的條件或者棧中僅存在兩個序列，我們用X，Y依次表示從棧頂向下的兩個已有序列的長度，如果X>=Y則進行歸并，然后將歸并后的有序片段結果入棧。
1.3 在歸并兩個已有序的片段時，采用了所謂的飛奔（gallop ）模式，這樣可以減少參與歸并的數據長度
假設需要歸并的兩個已有序片段分別為X和Y，如果X片段的前m個元素都比Y片段的首元素小，那么這m個元素實際上是不需要參與歸并的，因為歸并后這m個元素仍然位于原來的位置。同理如果Y片段的最后n個元素都比X的最后一個元素大，那么Y的最后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;
//待排序數組
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);
}
//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]開始，的最長有序片段的個數
private int maxAscendingLen(T[] a, int from){
int n = 1;
int 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){//至少兩個run序列
int x = stackTop - 2;
//x > 0 表示至少三個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]中最大的值
//應該先合并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;
}
//返回后一個片段的首元素在前一個片段應該位于的位置
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;
}
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不用變,長度需要發生變化
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;
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){//等號保證排序的穩定性
a[k] = aux[i++];
}else{
a[k] = aux[j++];
}
k++;
}
}
//強制歸并已入棧的序列
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){
//隨機產生測試用例
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;
}
//有序的基礎上隨機交換一些值
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;
}
//逆序部分數據
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排序和庫函數提供的排序結果比較是否一致
//如果沒有打印任何結果，說明排序結果正確
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;
}
}
}
}</code></pre>
3.TimSort算法應當注意的問題
TimSort算法只會對連續的兩個片段進行歸并，這樣才能保證算法的穩定性。
最小歸并長度和棧的長度存在一定的關系，如果增大最小歸并長度，則棧的長度也應該增大，否則可能引起棧越界的風險（代碼中棧是通過長度為40的數組來實現的）。
4.完整版的TimSort算法
實際上，完整版的TimSort算法會在上述簡易TimSort算法上還有大量的優化。比如有序序列小于最小歸并長度時，我們可以利用類似二分查找的方式來找到應該插入的位置來對數組進行長度擴充。再比如飛奔模式中采用二分查找的方式查找第二個序列的首元素在第一個序列的位置，同時還可以使用較小的輔助空間完成歸并，有興趣的同學可以查看Java中的源代碼來學習。
來自：http://www.cnblogs.com/nullzx/p/6014471.html