mergesort
Babel + JSX
function mergerSort(arr) {
let step = 1,
len = arr.length;
// 如果数组为1|0则直接返回
if (len < 2) return arr;
let left_start, right_start;
while (step < len) {
left_start = 0;
right_start = step;
//当数组长度为偶数时,并且小于数组总长度,执行循环
while (right_start + step <= len) {
// 分开对数组进行相关排序
sortArr(arr,left_start,left_start+step,right_start,right_start+step);
left_start = right_start+step;
right_start = left_start+step;
}
// 当数组长度为奇数时, 再进行一次排序
if(right_start < len){
sortArr(arr,left_start,left_start+step,right_start,len);
}
step *= 2;
}
return arr;
}
/**
* 对指定两个子数组数组进行排序
*/
function sortArr(arr, left_start, left_end, right_start, right_end) {
// 生成左右两个数组
let left_len = left_end - left_start,
right_len = right_end - right_start,
left_arr = new Array(left_len+1),
right_arr = new Array(right_len+1);
// 添加两个数组的数据
let k = left_start;
for(var i=0;i<left_len;i++){
left_arr[i] = arr[k+i];
}
k = right_start;
for(var i=0;i<right_len;i++){
right_arr[i] = arr[k+i];
}
// 放入一个无限大的数Infinity 方便下面比较
left_arr[left_len] = right_arr[right_len] = Infinity;
// 排序比较两个数组
// 已知,两个数组都是左边小右边大.
let left_index = 0,
right_index = 0;
for(var i=left_start;i<right_end;i++){
if(left_arr[left_index]<=right_arr[right_index]){
arr[i] = left_arr[left_index];
left_index++;
}else{
arr[i] = right_arr[right_index];
right_index++;
}
}
}
function randomArr() {
let arr = [];
for (var i = 0; i < 500; i++) {
arr.push(i);
}
arr.sort(() => Math.random() - 0.5);
return arr;
}
let arr = randomArr();
console.log(mergerSort(arr));