JavaScriptAlgorithms/Sort/MergeSort.html at master · biaodigit/JavaScriptAlgorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
<!DOCTYPE html>
<htmllang="en">
<head>
<metacharset="UTF-8">
<title>Title</title>
</head>
<body>
<script>
functionmergeSort(arr){
letlen=arr.length
_mergeSort(arr,0,len-1)
console.log(arr)
}

function_merge(arr,l,mid,r){
letaux=[];
for(leti=l;i<=r;i++){
aux[i-l]=arr[i]
}
leti=l,
j=mid+1;
//i=6,mid=7,j=8,l=6,r=9
//[1,6,5,7]
for(letk=l;k<=r;k++){
if(i>mid){
arr[k]=aux[j-l];
j++
}elseif(j>r){
arr[k]=aux[i-l];
i++
}elseif(aux[i-l]>aux[j-l]){
arr[k]=aux[j-l];
j++
}else{
arr[k]=aux[i-l];
i++
}
}
}

/**
 * 递归方式
 * @param arr
 * @param l
 * @param r
 * @private
 */
function_mergeSort(arr,l,r){
if(l>=r){
return
}
letmid=(l+r)>>1;
_mergeSort(arr,l,mid);
_mergeSort(arr,mid+1,r);
if(arr[mid]>arr[mid+1])
_merge(arr,l,mid,r)
}

/**
 * 非递归方式
 * @param arr
 * @param l
 * @param r
 * @private
 */
functionnonRecMergeSort(arr){
varstack=[],
res=[],
start=0,
end=arr.length-1;
if(start<end){
stack.push(end)
stack.push(start)
res.push(end)
res.push(start)
while(stack.length){
varl=stack.pop()
varr=stack.pop()
varmid=l+Math.floor((r-l)/2)
if(mid+1<r){
stack.push(r)
res.push(r)
stack.push(mid+1)
res.push(mid+1)
}
if(l<mid){
stack.push(mid)
res.push(mid)
stack.push(l)
res.push(l)

}
}
}
while(res.length){
varls=res.pop()
varrs=res.pop()
varmids=ls+Math.floor((rs-ls)/2)
_merge(arr,ls,mids,rs)
}
console.log(arr)
}


mergeSort([3,1,5,7,2,4,9,6,10,8])
nonRecMergeSort([3,1,5,7,2,4,9,11,6,12,10,8])
</script>
</body>
</html>