排序算法之归并排序

发表于 | 分类于 ，

算法思想

归并排序利于分治法的思想，在待排序序列选取位于中间位置的元素将序列一分为二，然后再对这两部分分别排序，最后将两部分合并，合并后的序列为已排序序列。

分的过程：设序列长度为N,则以(N-1)/2位置的元素为分界线，将队列分为两部分：位置从0到(N-1)/2的元素为一部分、位置从((N-1)/2)+1到N-1的元素为一部分（或者0到((N-1)/2-1)为一部分，(N-1)/2到N-1为一部分）。

合的过程：比较两个队列（两个队列已各自排好序）的队首元素，将小的从该队列中移除并插入到新队列的第一个位置，然后在比较两队列的首元素大小，将小的从该队列移除并将其添加到新队列上次添加的元素的后面，重复上述步骤直到有一个队列为空。最后将不为空的队列剩下所有的元素依次添加到新队列的最后，新队列则为一个已排序的队列。

排序示例

对序列｛3, 4, 63, 2, -9, 0, 1, 32, -2｝进行排序。

首先，将序列分为两个序列：{3, 4, 63, 2, -9}、{0, 1, 32, -2}，然后分别对两个序列排序。

对序列{3, 4, 63, 2, -9}排序过程为：

  1. 分割序列，得到两个序列{3, 4, 63}、{2, -9}。
  2. 分割序列 {3, 4, 63}，得到两个待排序序列{3, 4}、{63}。
    1. 分割序列 {3, 4}，得到两个待排序序列 {3}、{4}。
      1. 两个待排序序列只有一个元素，分割结束。
      2. 合并序列 {3}、{4}，得到已排序序列 {3, 4}。
    2. 序列 {63} 只有一个元素，分割介绍。
    3. 合并序列 {3, 4}、{63}，得到已排序序列 {3, 4, 63}。
  3. 分割序列 {2, -9}，得到两个待排序序列 {2}、{-9}。
    1. 两个待排序序列只有一个元素，分割结束。
    2. 合并序列 {2}、{-9}，得到已排序序列 {-9, 2}。
  4. 合并序列 {3，4，63}、{-9, 2}，得到已排序序列 {-9, 2, 3, 4, 63}。

对序列 {0, 1, 32, -2}排序过程不再展示。

最后将得到的两个已排序序列{-9, 2, 3, 4, 63}、{-2, 0, 1, 32}合并后得到最终排序序列{-9, -2, 0, 1, 2, 3, 4, 32, 63}

代码

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
public int[] sort(int[] array) {
	mergeSort(array, 0, array.length-1);
	return array;
}

private void mergeSort(int[] array, int start, int end) {
	if(start == end) {
		return;
	}
	int middle = (start + end)/2;
	mergeSort(array, start, middle); //对分割后的序列排序
	mergeSort(array, middle+1, end);
	merge(array, start, middle, end); //合并两个序列
}

private void merge(int[] array, int start, int middle, int end) {
	int[] newArray = new int[end-start+1];
	
	int newIndex =0;
	int index1 = start;
	int index2 = middle+1;
	
	//依次比较两个序列中的首元素，将小的赋值到新的序列中
	while(index1<=middle && index2<=end) {
		if(array[index1]<=array[index2]) {
			newArray[newIndex] = array[index1];
			index1++;
		} else {
			newArray[newIndex] = array[index2];
			index2++;
		}
		newIndex++;
	}
	
	//将两个序列中剩余的元素一次赋值到新序列中
	while(index1<=middle) {
		newArray[newIndex] = array[index1];
		index1++;
		newIndex++;
	}
	
	while(index2<=end) {
		newArray[newIndex] = array[index2];
		index2++;
		newIndex++;
	}
	
	for(int i=start, j=0; i<=end; i++,j++) {
		array[i] = newArray[j];
	}
}

代码地址：github