歸并排序是分治算法的一種荔仁，它的思想比較多個(gè)小的有序集合育特，然后合并成一些集合，然后再兩兩合并合并成一些大的集合疫萤，最終合并成一個(gè)集合趁矾，這個(gè)大集合就是最終的結(jié)果了。
歸并排序分為兩大類(lèi)给僵，分為自底向上的歸并排序，和自頂向下的兩大類(lèi)详拙，自頂向下的算法一般我們用遞歸算法來(lái)實(shí)現(xiàn)帝际，自底向上的算法我們一般通過(guò)，where循環(huán)來(lái)實(shí)現(xiàn)饶辙。
歸并排序的時(shí)間復(fù)雜度是O(n*logn)蹲诀，當(dāng)然歸并算法也有很多可以優(yōu)化的地方，例如我們已經(jīng)有序的兩個(gè)數(shù)組弃揽，并且可以直接連接起來(lái)的話脯爪，就不需要merage了，還有就是當(dāng)歸并排序后期矿微，我們的數(shù)組已經(jīng)可以稱為局部有序了痕慢，我們可以在后期調(diào)用插入排序，這樣雖然不能在時(shí)間復(fù)雜度級(jí)別上優(yōu)化我們的算法涌矢，但是也可以優(yōu)化很多的掖举。
自頂向下的算法：
/**
* Created by linSir on 17/2/9.
*/
function merge(data, left, center, right) {
var tmpArr = new Array();
var mid = center + 1;
var third = left;
var tmp = left;
while (left <= center && mid <= right) {
if (data[left] <= data[mid]) {
tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
while (tmp <= right) {
data[tmp] = tmpArr[tmp++];
}
console.log(data);
console.log(tmpArr);
return data;
}
function sort(data, left, right) {
if (left >= right)
return;
var center = parseInt((left + right) / 2);
sort(data, left, center);
sort(data, center + 1, right);
merge(data, left, center, right);
}
var data = [1, 1000, 4, 40, 2, 5, 100, 88];
sort(data, 0, data.length - 1);
結(jié)果：
Paste_Image.png
//TODO
