姍姍來(lái)遲的排序算法的第四篇宽堆，本介紹歸并排序算法瓦哎，是不是有人會(huì)問(wèn)這樣的問(wèn)題，現(xiàn)在書本上學(xué)習(xí)到的排序算法都太經(jīng)典了陶珠，在實(shí)際生產(chǎn)環(huán)境中基本上不會(huì)直接拿來(lái)使用挟裂，如果你的上司讓你實(shí)現(xiàn)一個(gè)歸并或者快排在生成環(huán)境中使用，那他一定是瘋了揍诽，基于此诀蓉，我介紹一種在歸并排序算法基礎(chǔ)上改進(jìn)而來(lái)的Timsort算法栗竖，后者是在實(shí)際排序中經(jīng)常用到的排序算法，與之詳情渠啤，請(qǐng)往下看狐肢。
歸并排序
歸并排序的核心思想就是，將一個(gè)排序數(shù)組不斷的劃分沥曹，劃分到足夠的小的粒度份名，那就是長(zhǎng)度為1了，然后開始1/1合并為2妓美，然后再2/2合并為4僵腺，依次類推，在合并的過(guò)程中壶栋，讓數(shù)據(jù)有序辰如，最后完成排序。
代碼如下：
public static void sort(int[] nums, int start, int end) {
Arrays.nonBlank(nums);
if (start >= end) return;
int mid = (start + end) / 2;
sort(nums, start, mid);
sort(nums, mid + 1, end);
merge(nums, start, mid, end);
}
private static void merge(int[] nums, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int k = 0;
int i = start;
int j = mid + 1;
while (i <= mid && j <= end) {
if (nums[i] <= nums[j]) temp[k++] = nums[i++];
else temp[k++] = nums[j++];
}
while (i <= mid) temp[k++] = nums[i++];
while (j <= end) temp[k++] = nums[j++];
for (int l = 0; l < temp.length; l++) {
nums[start + l] = temp[l];
}
}
歸并算法的主要方法還是分治法委刘，然后合并分開的元素丧没，直至最后有序鹰椒，最好/最壞時(shí)間復(fù)雜度為O(nlgn)锡移，毋庸置疑，歸并排序是穩(wěn)定的排序漆际，為什么有序淆珊，因?yàn)樗鼪](méi)有跳躍，所以是有序的奸汇。
歸并的時(shí)間復(fù)雜度提升了很多施符，那問(wèn)題來(lái)了，歸并排序有沒(méi)有不足擂找？是存在的戳吝，首先很容易想到的一個(gè)特例就是如果一個(gè)數(shù)組是有序的，那排定有序數(shù)組的時(shí)間復(fù)雜度也是O(nlgn)贯涎，而如果用我們之前介紹的冒泡的改進(jìn)算法只需要O(n)就搞定了听哭，那下面分析一下如何改進(jìn)歸并排序算法。
已經(jīng)看過(guò)歸并排序的實(shí)現(xiàn)塘雳，會(huì)發(fā)現(xiàn)其實(shí)所有的工作都是在合并（merge）的過(guò)程當(dāng)中完成的陆盘。所以歸并的優(yōu)化也就是對(duì)合并過(guò)程的優(yōu)化，以下三點(diǎn)可能的優(yōu)化途徑：
1败明、能否使合并過(guò)程運(yùn)行的更快隘马？
2、能否執(zhí)行更少的合并過(guò)程妻顶？
3酸员、是否存在一些與其使用歸并排序不如使用其他排序的情況蜒车？
基于以上三個(gè)問(wèn)題，思考十分鐘（這十分鐘估計(jì)也想不出個(gè)啥）沸呐，開始介紹下一種TimSort的自適應(yīng)歸并排序算法醇王；
自適應(yīng)歸并排序算法——TimSort
TimSort算法基于歸并算法改進(jìn)而來(lái)的算法，其主要改進(jìn)是：
- 在應(yīng)用歸并排序時(shí)崭添，會(huì)尋找數(shù)組中的自增分區(qū)或者自減分區(qū)寓娩，已分區(qū)為合并的基礎(chǔ)長(zhǎng)度，而不是將其劃分單個(gè)的元素呼渣；
- 針對(duì)自減分區(qū)直接進(jìn)行翻轉(zhuǎn)而不是直接合并棘伴，自減分區(qū)識(shí)別中必須嚴(yán)格降序，要不然無(wú)法保證算法的穩(wěn)定性屁置；
- 在分區(qū)合并時(shí)焊夸，采用二分插入算法，即使用二分查找找到數(shù)據(jù)插入的位置蓝角，然后插入阱穗；
- 當(dāng)部分分區(qū)（TimSort中把分區(qū)成為run）長(zhǎng)度小于分區(qū)最小長(zhǎng)度時(shí)，從數(shù)組中選擇合適的長(zhǎng)度插入使鹅；
- 當(dāng)數(shù)組的長(zhǎng)度小于某一特定值時(shí)揪阶，其直接采用插入排序來(lái)排序
- 算法采用棧來(lái)存放有序分區(qū)，其合并時(shí)機(jī)要符合一定規(guī)則患朱，假設(shè)從棧頂?shù)綏５茁沉牛謩e有x/y/z三個(gè)元素（分區(qū)），當(dāng)
x>y+z && y>z時(shí)裁厅，合并結(jié)束冰沙，否則進(jìn)行合并操作； - 合并過(guò)程中执虹，采用二分插入算法提高效率拓挥；
基于以上所有的改進(jìn)策略，TimSort排序算法誕生袋励，其使用場(chǎng)景是序列連續(xù)部分有序侥啤，當(dāng)然其最壞的表現(xiàn)也不過(guò)就是普通歸并，不能比這個(gè)更壞了插龄，其最好時(shí)間復(fù)雜度O(n)愿棋，其平均/最壞時(shí)間復(fù)雜度O(nlgn)，并且該算法為穩(wěn)定排序均牢。具體實(shí)現(xiàn)參見 java1.7+版本中的Arrays.sort方法糠雨，另外python中的排序算法也是這個(gè)。
總結(jié)
歸并算法其時(shí)間復(fù)雜度很穩(wěn)定徘跪，其最好/平均/最壞時(shí)間復(fù)雜度是一樣甘邀，這樣給出了改進(jìn)的空間琅攘，映射到生活中好像也是如此，我們也得根據(jù)某些特殊情況去制定一些特殊的規(guī)則松邪，必須不是所有的人都想走大路坞琴，有時(shí)候符合條件的小路也未嘗不是一種很好的選擇。
