归并排序

归并排序

归并排序(Merge Sort)是建立在归并操作上的一种有效且稳定的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。基本思路是将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。由约翰·冯·诺伊曼在1945年提出。

参考链接

算法描述

1、首先把长度为n的输入序列分成两个长度为n/2的子序列。
2、再对这两个子序列分别采用归并排序。
3、最后将两个排序好的子序列合并成一个最终的排序序列。

动图演示

在这里插入图片描述

代码实现

Java

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
package com.test;

import java.util.Arrays;

public class MergeSort {
//临时数组
private static int[] tmp;

public static void main(String[] args) {
int[] arr = {23, 20, 32, 5, 45, 6, 8, 9, 15, 1};
tmp = new int[arr.length]; // 不需要用户初始化会更友好(需要再写一个接口传入mergeSort和merge)
mergeSort(arr, 0, arr.length - 1);
System.out.println("排序结果:" + Arrays.toString(arr));
}

public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}

/**
* 归并方法
* 先将arr[]的所有元素复制到临时数组tmp[]中,然后再归并到arr[]
*
* @param arr 待排序数组
* @param left 左指针
* @param mid 中间指针
* @param right 右指针
*/
public static void merge(int[] arr, int left, int mid, int right) {
int i = left;
int j = mid + 1;
for (int k = left; k <= right; k++) {
tmp[k] = arr[k];
}

for (int k = left; k <= right; k++) {
if (i > mid) {//左半边元素用完,取右半边
arr[k] = tmp[j++];
} else if (j > right) {//右半边元素用完,取左半边
arr[k] = tmp[i++];
} else if (tmp[j] < tmp[i]) {//右半边的当前元素小于左半边的当前元素,取右半边的元素
arr[k] = tmp[j++];
} else {//右半边的当前元素大于左半边的当前元素,取左半边的元素
arr[k] = tmp[i++];
}
}
}
}

排序结果:[1, 5, 6, 8, 9, 15, 20, 23, 32, 45]

JavaScript

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
function mergeSort(arr,left,right) {
if (left < right) {
var mid = Math.floor((left + right) / 2);//注意js的/不是取整的 需要用Math函数
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}

/**
* 归并方法
* 先将arr[]的所有元素复制到临时数组tmp[]中,然后再归并到arr[]
*/
function merge(arr,left,mid,right) {
var i = left;
var j = mid + 1;
for (var k = left; k <= right; k++) {
tmp[k] = arr[k];
}

for (var k = left; k <= right; k++) {
if (i > mid) {//左半边元素用完,取右半边
arr[k] = tmp[j++];
} else if (j > right) {//右半边元素用完,取左半边
arr[k] = tmp[i++];
} else if (tmp[j] < tmp[i]) {//右半边的当前元素小于左半边的当前元素,取右半边的元素
arr[k] = tmp[j++];
} else {//右半边的当前元素大于左半边的当前元素,取左半边的元素
arr[k] = tmp[i++];
}
}
}

var arr = [23,20,32,5,45,6,8,9,15,1];
var tmp = new Array(arr.length);// 不需要用户初始化会更友好(需要再写一个接口传入mergeSort和merge)
mergeSort(arr,0,arr.length-1);
console.log(arr);

(10) [1, 5, 6, 8, 9, 15, 20, 23, 32, 45]