归并排序(Merge sort)

归并算法(merge):指的是将两个已经排序的序列合并成一个序列的操作。

####归并操作的过程如下:

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

####java 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] MergeSort(int[] A, int[] B) {
int[] C = new int[A.length + B.length];
int k = 0;//三个数组的索引
int i = 0;
int j = 0;
while(i < A.length && j < B.length) {
if (A[i] < B[j])
C[k++] = A[i++];
else
C[k++] = B[j++];
}
while (i < A.length)
C[k++] = A[i++];
while (j < B.length)
C[k++] = B[j++];
return C;
}