歸并排序
這個(gè)排序算法是建立在歸并操作上的一種有效的排序算法栋豫，算法主要采用分治法，歸并排序的算法復(fù)雜度為O（n*logn）谚殊，需要一個(gè)與數(shù)組的長(zhǎng)度n一樣的額外空間笼才，實(shí)現(xiàn)歸并排序通常對(duì)于一個(gè)數(shù)組我們對(duì)前半部分進(jìn)行排序，然后進(jìn)行后半部分進(jìn)行排序络凿，實(shí)現(xiàn)原地歸并操作骡送，不過(guò)需要額外的空間存儲(chǔ)數(shù)組。歸并排序分為兩種絮记，一種是自頂向下的歸并排序摔踱，一種是自底向上的歸并排序。
一怨愤、自頂向下的歸并排序
把數(shù)組元素不斷的二分派敷，直到子數(shù)組的元素個(gè)數(shù)為一個(gè)，這時(shí)子數(shù)組必然是有序的撰洗，然后將兩個(gè)有序的序列合并成一個(gè)新的有序的序列篮愉，兩個(gè)新的有序序列又可以合并成另一個(gè)新的有序序列，以此類(lèi)推差导，直到合并成一個(gè)有序的數(shù)組试躏。
var data=[1,5,3,23,4,67,8];
function merge(data, left, center, right) {
var tmpArr = [];
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++];
}
}
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);
console.log(data);
}
sort(data,0,6);
console.log(data);
二、自底向上的歸并排序
其實(shí)邏輯跟上一個(gè)一樣设褐，只有sort函數(shù)有差別颠蕴，不過(guò)這個(gè)不需要遞歸到最后，直接從一開(kāi)始就進(jìn)行比較助析，通過(guò)控制增量解決合并的問(wèn)題犀被，如果有8個(gè)元素，增量為1時(shí)有四組合并外冀，增量為2時(shí)候寡键，兩組合并，最后進(jìn)行全部合并雪隧。
function sort2(data,left,right)
{
var len=data.length;
for (var sz = 1; sz < len; sz *= 2)
{
for (var lo = 0; lo < len; lo += 2 * sz)
{
merge(data, lo, lo+sz-1, min(lo+2*sz-1, len-1));
}
}
}
function min(m,n) {
if(m<=n){
return m;
}else {
return n;
}
}
結(jié)果數(shù)組
