紧接着上一篇的快速排序,本文主要来讲一下归并排序。快速排序,归并排序,以及堆排序,也就是我们排序里可能会经常用到的三种了。学会它们,也可以会不少的题目。先上Js和C的递归写法吧。

下面先上归并排序的排序过程:

归并排序

归并排序过程

JavaScript Solution

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
function MergeSort(data){
if(data.length === 1)
return data
else{
let middle = parseInt(data.length/2)
let left = data.slice(0,middle)
let right = data.slice(middle)
return Merge(MergeSort(left), MergeSort(right))
}
}

function Merge(left,right){
let arr = []
let l = 0 , r = 0
while( l < left.length && r < right.length ){
if( left[l] < right[r])
arr.push(left[l++])
else
arr.push(right[r++])
}

while(l < left.length)
arr.push(left[l++])

while(r < right.length)
arr.push(right[r++])

return arr
}

unsort = [1,0,2,9,3,8,4,7,5,6]
console.log(MergeSort(unsort))

C Solution

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
void merge(int arr[], int low, int mid, int high){
int i = low, j = mid + 1; //左右指针
int k = 0; //工作指针
int* temp = (int*) malloc (sizeof(int) * (high-low+1)); //暂存数组
for(;i<=mid && j <= high; k++){ // 比较两个指针所指向的元素
if(arr[i]<=arr[j])
temp[k] = arr[i++];
else
temp[k] = arr[j++];
}


while(i <= mid) temp[k++] = arr[i++]
while(j <= mid) temp[k++] = arr[j++]

for(k=0 ; k<high-low+1; k++)
arr[low+k] = temp[k];

return;
}

void MergeSort(int arr[], int left, int right){
if( left < right ){
int mid = left + (right - left) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid+1, right);
Merge(arr, left, mid, right);
}
return;
}

本文标题:归并排序(递归)

文章作者:JarryChen

发布时间:2019年10月24日 - 21:09

最后更新: 2019年11月26日 07:57

原始链接: https://jarrychen.xyz/archives/efa8ef13.html

× 请我喝奶茶~
打赏二维码