之前的文章講解了三種時(shí)間復(fù)雜度為O(n^2)的簡(jiǎn)單排序算法训桶，本篇介紹另外兩種經(jīng)典排序算法希爾排序和歸并排序午笛。這兩種算法中渣刷，希爾排序理解起來不太容易鱼辙，歸并排序比較容易理解但代碼量偏多。在面試的過程中被問到的幾率比較小玫镐。
希爾排序
希爾排序是插入排序的一種倒戏，是對(duì)前一篇所講直接插入排序的優(yōu)化方法，又稱縮小增量排序恐似。
基本思想：將無序數(shù)組分割為若干個(gè)子序列杜跷，子序列不是逐段分割的，而是相隔特定的增量的子序列蹂喻，對(duì)各個(gè)子序列進(jìn)行插入排序葱椭；然后再選擇一個(gè)更小的增量，再將數(shù)組分割為多個(gè)子序列進(jìn)行排序直到選擇增量為1口四，即使用直接插入排序孵运，使最終數(shù)組成為有序。
增量的選擇：在每趟的排序過程都有一個(gè)增量蔓彩，至少滿足一個(gè)規(guī)則 增量關(guān)系 d[1] > d[2] > d[3] >..> d[n] = 1 (n趟排序)治笨。
增量的大小對(duì)排序算法性能也有影響，一般而言赤嚼，增量的初始值設(shè)為(數(shù)組長(zhǎng)度 / 2)之后的每趟排序中旷赖，數(shù)組長(zhǎng)度變?yōu)橹暗?/2，直到 增量為1時(shí)結(jié)束排序更卒。
希爾排序過程比較復(fù)雜等孵，這里有個(gè)短視頻，可以幫助理解：http://v.youku.com/v_show/id_XMjU4NTcwMDIw.html
還是直接上代碼吧：
public void shellSort(int[] nums){
int increment = nums.length;
int temp;
while(true){
increment = (int)Math.ceil(increment / 2);
for(int i = 0; i < increment; i += increment){
for(int j =i + increment; j < nums.length; j++){
int k = j - increment;
temp = nums[j];
for(; k >= 0 && nums[k] > temp; k -= increment){
nums[k + increment] = nums[k];
}
nums[k + increment] = temp;
}
}
if(increment == 1){
break;
}
}
}
歸并排序
歸并排序運(yùn)用了基礎(chǔ)算法中的分治思想蹂空，將數(shù)先對(duì)半拆分為兩個(gè)數(shù)組俯萌，在對(duì)分開的數(shù)組做拆分，以此類推直到拆分出的數(shù)組的長(zhǎng)度為1時(shí)停止拆分開始?xì)w并上枕。
歸并的方式也很簡(jiǎn)單咐熙，就是創(chuàng)建一個(gè)大小為兩個(gè)數(shù)組長(zhǎng)度之和的新數(shù)組，然后兩個(gè)數(shù)組都從頭開始遍歷辨萍，按順序加入新數(shù)組棋恼，新產(chǎn)生的數(shù)組必定是排好序的，再將其與其他數(shù)組進(jìn)行歸并锈玉，直至整個(gè)數(shù)組排序完成爪飘。
思路很簡(jiǎn)單，但是代碼量還是挺大的拉背，雖然比不上堆排序悦施，但畢竟堆排序相較于歸并而言顯得更加高級(jí)，相同的時(shí)間復(fù)雜度但空間復(fù)雜度堆排序優(yōu)于歸并排序去团。
為了方便理解，減少代碼量，本文給出歸并排序的遞歸實(shí)現(xiàn)方式：
//歸并的主方法
public int[] mergeSort(int[] nums, int low, int high){
int mid = (low + high) / 2;
if(low < high){
mergeSort(nums, low, mid);
mergeSort(nums, mid + 1, high);
merge(nums, low, mid, high);
}
return nums;
}
//數(shù)組合并
public void merge(int[] nums, int low, int mid, int high){
int[] temp = new int[high - low + 1];
int i = low;
int j = mid + 1;
int cnt = 0;
while(i <= mid && j <= high){
if(nums[i] < nums[j]){
temp[cnt++] = nums[i++];
}else{
temp[cnt++] = nums[j++];
}
}
while(i <= mid){
temp[cnt++] = nums[i++];
}
while(j <= high){
temp[cnt++] = nums[j++];
}
for(i = 0; i < temp.length; i++){
nums[i + low] = temp[i];
}
}
本篇介紹的兩種排序算法在面試中不常被問到土陪，可能還沒有在筆試中考到的頻率高昼汗，但也希望理解其思想，不會(huì)寫也得會(huì)說吧鬼雀。
