常见排序算法总结(归并排序)——Java语言(二)

前言

归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为 O(NlogN)(大O符号)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

归并排序的图示:

Merge_sort_animation2-2018913

算法讲解

归并排序算法是采用经典的分治策略,将问题divide成一些小问题,然后在conquer阶段将分的阶段得到的答案修补在一起,即为分而治之。

QQ截图20180914111850-2018914

任何的递归都可以采用迭代来实现,递归行为实质上是压栈和出栈的过程。

算法实例

算法流程:

  • 对待排序数组array进行拆分,即分治思想中的分。
  • 将array分为两组之后进行排序,保证子序列有序。在保证子序列有序的过程中还会递归上一步骤,直到left==right的时候。
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
/**
* 传入参数合法性校验,然后调用归并排序的方法
*
* @param array 目标数组
*/
public static void mergeSort(int array[]) {
if (array == null || array.length < 2) {
return;
}
sort(array, 0, array.length - 1);
}

/**
* 归并排序的实现,这里用到的是分治的思想
*
* @param array
* @param left
* @param right
*/
private static void sort(int[] array, int left, int right) {
//递归终止条件
if (left == right) {
return;
}
int mid = left + ((right - left) >> 1);
sort(array, left, mid);
sort(array, mid + 1, right);
//归并
merge(array, left, right);
}

/**
* 归并算法
*
* @param array
* @param left
* @param right
*/
private static void merge(int[] array, int left, int right) {
int mid = left + ((right - left) >> 1);//防止因为left和right太大导致的integer越界,相当于left+(right-left)/2
int[] help = new int[right - left + 1];//建立辅助数组
int i = 0;
int p1 = left;//p1指向left的数组第一个
int p2 = mid + 1;//p2指向right数组的第一个
while (p1 <= mid && p2 <= right) {
//比较,谁小填入辅助数组
help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
}
//上面的while循环结束,当且只当p1和p2有一个越界,下面的两个while是将剩下的数组数据填到辅助数组
while (p1 <= mid) {
help[i++] = array[p1++];
}
while (p2 <= right) {
help[i++] = array[p2++];
}
//数据回填,将辅助数组的数据回填到原数组
for (i = 0; i < help.length; i++) {
array[left + i] = help[i];
}
}

总结

时间复杂度分析:

递归行为可以采用master公式:

T(N)=a*T(N/b)+O(N^d)

以上算法针对的是对于一个数据,可以分为b个部分进行处理。

1
2
3
4

1) log(b,a) > d -> 复杂度为O(N^log(b,a))
2) log(b,a) = d -> 复杂度为O(N^d * logN)
3) log(b,a) < d -> 复杂度为O(N^d)

对于归并来说,可以看做是将一个数据分为两部分来进行处理。

这里的公式为:

1
2
3
4

```d=1,log(b,a)=1```,那么这个时间复杂度为

```T(N)=NlogN

关于master公式:www.gocalf.com/blog/algorithm-complexity-and-mastertheorem.html

-------------The End-------------

本文标题:常见排序算法总结(归并排序)——Java语言(二)

文章作者:Dimple

发布时间:2018年09月13日 - 16:09

最后更新:2018年09月28日 - 17:09

原始链接:http://www.bianxiaofeng.com/2018/09/13/2018-9-13-16-36-10/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

na,给我一个棒棒糖!
0%