算法渣-排序-归并排序

没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法

定义

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

算法

归并排序(Merge Sort)就是利用归并思想对数列进行排序。根据具体的实现,归并排序包括”从上往下“和”从下往上“2种方式

从上往下的归并排序:

  1. 分解 – 将当前区间一分为二,即求分裂点 mid = (low + high)/2
  2. 求解 – 递归地对两个子区间a[low…mid] 和 a[mid+1…high]进行归并排序。递归的终结条件是子区间长度为1
  3. 合并 – 将已排序的两个子区间a[low…mid]和 a[mid+1…high]归并为一个有序的区间a[low…high]

从下往上的归并排序:

  1. 将待排序的数列分成若干个长度为1的子数列,然后将这些数列两两合并;
  2. 得到若干个长度为2的有序数列,再将这些数列两两合并;得到若干个长度为4的有序数列,再将它们两两合并;
  3. 直接合并成一个数列为止。这样就得到了我们想要的排序结果。

归并步骤

  • 第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  • 第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置
  • 第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  • 重复步骤3直到某一指针超出序列尾,将另一序列剩下的所有元素直接复制到合并序列尾

比如合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤

演示

image

实现

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
/**
* 归并排序
* @param array
* @param left
* @param right
*/
private static void mergeSort(int []array,int left,int right){
if(left < right) {
//分解
int mid = (left + right) / 2;
mergeSort(array,left,mid);
mergeSort(array,mid + 1,right);
//合并
merge(array,left,mid,right);
}
}

static void merge(int []array,int left,int mid,int right) {
System.out.println("merge->left:"+left+" mid:"+mid+" rgiht:"+right);
int i = left;
int j = mid +1;
int tmp[] = new int[right-left+1];//构建tmp数组
int t = 0;//tmp数组索引
//填充tmp数组
for (;i<=mid && j<=right;) {
if(array[i] < array[j]) {
tmp[t++] = array[i++];
} else {
tmp[t++] = array[j++];
}
}
while (i<=mid) {
tmp[t++] = array[i++];
}
while (j<=right) {
tmp[t++] = array[j++];
}

//再把tmp复制到array
t = 0;
while (left<=right) {
array[left++] = tmp[t++];
}
System.out.println(" tmp:"+ Arrays.toString(tmp));
System.out.println("merge:"+ Arrays.toString(array));
}

复杂度

归并排序的时间复杂度是O(N*lgN)

假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N),需要遍历多少次呢?

归并排序的形式就是一棵二叉树,它需要遍历的次数就是二叉树的深度,而根据完全二叉树的可以得出它的时间复杂度是O(N*lgN)

Best Average Worst Memory Stable
n log(n) n log(n) n log(n) n Yes

VS 快速排序

归并排序(MergeSort)和快速排序(QuickSort)都是用了分治算法思想。

所谓分治算法,顾名思义,就是分而治之,就是将原问题分割成同等结构的子问题,之后将子问题逐一解决后,原问题也就得到了解决。

同时,归并排序(MergeSort)和快速排序(QuickSort)也代表了两类分治算法的思想。

对于归并排序,我们对于待处理序列怎么分的问题上并没有太多关注,仅仅是简单地一刀切,将整个序列分成近乎均匀的两份,然后将子序列进行同样处理。但是,我们更多的关注点在于怎么把分开的部分合起来,也就是merge的过程。

对于快速排序来说,我们则是花了很大的功夫放在了怎么分这个问题上,我们设定了枢轴(标定点),然后通过partition的过程将这个枢轴放在合适的位置,这样我们就不用特别关心合起来的过程,只需要一步一步地递归下去即可。

归并排序是由下向上的,先处理子数组然后再合并。而快速排序正好相反,它的过程是由上向下的,先分出两个子区间,再对子区间进行排序。归并排序是稳定的时间复杂度为 O(n)O(n),但它是非原地算法,在进行子数组合并的时候,我们需要临时申请一个数组来暂时存放排好序的数据。因为这个临时空间是可以重复利用的,因此归并排序的空间复杂度为 O(n),最多需要存放 n 个数据;
而快排则是原地排序算法

朱兴生 wechat
最新文章尽在微信公众号『码农戏码』