重庆网站建设技术支持重庆互联网/求几个微信推广平台

归并排序思路

1) 归并

从两个有序表R[low...mid]和R[mid+1...high]，每次从左边依次取出一个数进行比较，将较小者放入tmp数组中，最后将两段中剩下的部分直接复制到tmp中。

这样tmp是一个有序表，再将它复制加R中。(其中要考虑最后一个子表的长度不足length的情况)

2) 排序

自底向上的归并，第一回：length=1；第二回：length=2*length ...

 

代码实现

Function.prototype.method = function(name, func){this.prototype[name] = func;return this;
};Array.method('merge', function(low, mid, high){var tmp = new Array(), i = low, j=mid+1, k=0;while(i<=mid && j<=high){if(this[i] <= this[j]){//比较第一部分和第二部分，取较小者tmp[k] = this[i];i++;k++;}else{tmp[k] = this[j];j++;k++;}}while(i<=mid){tmp[k] = this[i];i++;k++;}while(j<=high){tmp[k] = this[j];j++;k++;}for(k=0,i=low; i<=high; k++,i++) this[i] = tmp[k];return this;
});
Array.method('mergePass', function(length, n){var i;for(i=0; i+2*length-1<n; i=i+2*length) this.merge(i, i+length-1, i+2*length-1);if(i+length-1 < n) this.merge(i, i+length-1, n-1); //考虑到最后一个子表的长度可能小于length，所以要特殊处理一下return this;
});Array.method('mergeSort', function(){var len = this.length,length;for(length=1; length<len; length=2*length) this.mergePass(length, len);return this;
});