JS实现归并排序
归并排序是---将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。⼀般采⽤⼆路归并。
归并排序其实要做两件事：
（1）“分解”——将序列每次折半划分。
（2）“合并”——将划分后的序列段两两合并后排序。
这两个有序序列段分别为 R[low, mid] 和 R[mid+1, high]。
<!DOCTYPE html>
<html>
<head>
<title>mergeSort</title>
<script type="text/javascript">
function Merge(arr,low,mid,high){
var i=low;//第⼀段序列的下标
var j=mid+1;//第⼆短序列的⼩标
var k=0;//临时存放组数的下标
var arr2=[];//临时存放数组
while(i<=mid && j<=high){
/
/判断第⼀段和第⼆段取出的数哪个更⼩，将其合并，并继续扫描
//本段的实质是：讲两个有序数组合并
if(arr[i] <= arr[j]){
arr2[k] = arr[i];
i++;
k++;
} else {
arr2[k] = arr[j];
j++;
k++;
}
}
//如果第⼀段序列还没扫描完，将其全部复制到合并序列
while(i<=mid){
arr2[k] = arr[i];
i++;
i++;
k++;
}
//如果第⼆段序列还没扫描完，将其全部复制到合并序列
while(j<=high){
arr2[k]= arr[j];
k++;
j++;
}
// console.log("arr:"+arr);
// console.log("arr2:"+arr2);
//arr = arr2;
//将合并序列复制到原始序列中
for(k=0,i=low;i<=high;i++,k++){
arr[i]=arr2[k];
}
// console.log("arr:"+arr);
/
/ console.log("arr2:"+arr2);
}
//
function MergePass(arr,gap,length){
var i=0;
//归并gap长度的两个相邻⼦表
for(i=0;i+2*gap-1<length;i=i+2*gap){
Merge(arr,i,i+gap-1,i+2*gap-1);
}
//如果有余下的数组不够gap的长度，就把他直接和前⾯的有序数组进⾏合并
if(i+gap-1<length){
Merge(arr,i,i+gap-1,length-1);
}
}
function sort(arr){
//控制gap，每次让他跳跃两个gap的距离。因为在内层循环中，是⽐较合并两个相邻gap的数组。    for(var gap = 1; gap<arr.length; gap=2*gap){
MergePass(arr,gap,arr.length);
console.log("gap:"+gap);
console.log(arr);
}
return arr;
}
var arr=[4,2,1,9,7];
var newarr = sort(arr);
console.log(newarr);
//输出[1, 2, 4, 7, 9]
</script>
</head>
<body>
</body>
sort函数 js</html>

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。