近幾天復習了一下排序算法校读，以此總結加深印象擎厢。
首先定義兩種原子操作：
void exch(T[] array,int i,int j) ：將數組array中的i铝侵、j元素互換位置媚媒；
boolean less(T a,T b) ：比較元素a,b的大小。
原始數組：array
選擇排序：[空間復雜度O（1）对湃、時間復雜度O（N^2）]
循環(huán)操作崖叫，每次選定剩余數組中最小的元素填充到已排序部分的隊尾；算法交換次數總是N拍柒，比較次數大約是N2/2心傀。運行時間與輸入無關、數據移動是最少的拆讯。
插入排序：[空間復雜度O（1）脂男、時間復雜度O（N^2）]
循環(huán)操作，將下一位元素插入到已排序數組中的合適位置种呐；平均需要N2/4次交換和N2/4次移動宰翅；最壞情況N2/2次交換和N2/2次移動；最好情況下進行N-1次比較和0次移動爽室。運行時間取決于初始元素的順序汁讼。對于部分有序的數組的排序更好。
幾種常見的部分有序數組：
1.數組中每個與元素距離它的最終位置都不遠阔墩；
2.一個有序大數組接一個小數組嘿架；
3.數組中只有幾個元素的位置不確定；
改進點：將內循環(huán)中將較大元素向右移動而不總是交換兩個元素啸箫；
總體來說耸彪，插入排序對于部分有序的數組和小規(guī)模數字十分有效；一般情況下忘苛，插入排序的效率大概是選擇排序的兩倍蝉娜；
希爾排序：[空間復雜度O（1）、時間復雜度O（N^（3/2))]
是對于插入排序的改進扎唾；對于大規(guī)模亂序數組召川，由于插入排序只能交換相鄰兩個元素的位置，如果最小元素恰好在數組盡頭胸遇，就需要N-1此移動扮宠。希兒排序交換不相鄰元素以對數組的局部進行排序。
核心思想：任意相隔h的元素都是有序的狐榔，序列一般選擇h = 3h+1,h初始為1坛增，最大不大于N/3。內部使用插入排序變體：
//希爾排序
int N = test.length;
int h = 1;
while (h<N/3) h = 3h+1;
while (h>=1){
for(int i = h;i<test.length;i++){
for (int j = i;j>=h;j-=h){
compare++;
if(test[j] < test[j-h]){
int temp = test[j];
test[j] = test[j-h];
test[j-h] = temp;
swap++;
}else {
break;
}
}
}
h = h/3;
}
適用于中等規(guī)模的數組薄腻。
歸并排序：[空間復雜度O（N）收捣、時間復雜度O（NlogN)]
將兩個有序小數組歸并為大數組，并逐漸合并為大數組庵楷；
優(yōu)化：對于過小的數組使用插入排序
