思想:
将待排序序列分为两个子序列,再将两个子序列递归的继续分下去,直到序列有序,即序列中只有一个元素,再把所有有序子序列逐层合并为一个整体有序序列。(每次合并是将两个有序表合并成一个有序表)。
图示:
具体实现:
- 把待排序序列分为两个子序列,然后让子序列继续分子序列。
- 把由同一个序列分出来的两个子序列合并。
- 申请内存空间,空间大小是两个已排序序列的和,用来暂时存放合并后的序列;
- 设置两个指针变量,分别指向两个已排序列数组的起始位置;
- 重复上一步骤直到某一指针到达序列尾;
- 当一个指针到达序列尾的时候,将另一个序列中的元素直接复制到合并序列的尾部;
- 将合并序列中的元素复制到原数组合适的位置。
代码实现:
package www.sort;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] array = {9,2,5,7,3,8,3,6,1};
mergeSort(array,0,array.length-1);
System.out.println(Arrays.toString(array));
}
public static void mergeSort(int[] array,int left,int right){
if (left >= right){
return;
}
int mid = left+(right-left)/2;
mergeSort(array,left,mid);
mergeSort(array,mid+1,right);
merge(array,left,right,mid);
}
public static void merge(int[] array,int left,int right,int mid){
int[] extra = new int[array.length];
int m = mid+1;
int l = left;
int x = left;
while (left <= mid && m <= right){
if (array[left] <= array[m]){
extra[x++] = array[left++];
}else {
extra[x++] = array[m++];
}
}
while (left <= mid){
extra[x++] = array[left++];
}
while (m <= right){
extra[x++] = array[m++];
}
while (l <= right){
array[l] = extra[l++];
}
}
}