一、定义
归并排序，英文称Merge sort 或 mergesort, 是创建在归并操作上的一种排序算法。是1945年有约翰逊·冯·诺依曼首次提出，是分治算法的典型应用
归并操作：也称归并算法，是将两个已经排序的序列合并成一个有序序列的操作。
二、思想
从归并排序的定义来看，其主要是归并操作，而归并操作的前提是两个已经排序的序列，所以首先需要将一个序列划分一个个有序的的序列，然后再进行归并。
它的核心思想是：先分后归（先拆分为一个个有序的子序列，再将一个个有序子序列进行归并操作最后合并为一个有序的序列）
三、实现方式
分为递归（也就自顶而下）和迭代实现（自下而上）方式
想一想：为什么会分为两种实现方式；它们各自有什么优势？
四、递归方式
原理图：
一个序列{4,2,32,56,1,77}
图1
原理：
1、申请空间，大小为待排序序列的大小，用来存放合并后的序列
2、设定两个下标，最初位置为两个已排序序列的起始位置
3、比较两个下标所指向的元素，选择较小的元素放入合并空间，并将下标置为下一个位置
4、重复3操作，知道某一下标到达序列尾部
5、将另一个序列剩下的所有元素直接复制并合并到序列尾部
代码实现：
/**
* @author: yongxiang.wei
* @version: 1.2.0, 2018/12/19 9:24
* @since: 1.2.0
*/
public class MergeSort {
public static void main(String[] args){
startMergeSort();
}
public static void startMergeSort(){
//随机生成待排序的序列
int[] unSorted = makeRandomArray(0, 1000, 20);//new int[]{4, 2, 32, 56, 1, 77};
mergeSort(unSorted);
}
/**
* 归并排序
* @param unSorted 待排序序列
*/
private static void mergeSort(int[] unSorted){
int len = unSorted == null ? 0 : unSorted.length;
//打印排序前的序列
System.out.println("Befort merge sorted:");
printArray(unSorted);
if(len > 1){
int[] sorted = new int[len];//先建一个等长于原数组的临时数组，避免递归中频繁开辟空间
mergeSort(unSorted, 0, len - 1, sorted);
}
//打印排序后的序列
System.out.println("\nAfter merge sorted:");
printArray(unSorted);
}
/**
* 归并排序
* @param unSorted 待排序序列
* @param left 序列的起始位置
* @param right 序列的结束位置
* @param sorted 两个已排序序列合并后存放的临时序列
*/
private static void mergeSort(int[] unSorted, int left, int right, int[] sorted){
if(left >= right){
return;
}
int mid = (left + right) / 2;
//左递归归并排序，使得左序列有序
mergeSort(unSorted, left, mid, sorted);
//右递归归并排序，使得右序列有序
mergeSort(unSorted, mid + 1, right, sorted);
//将两个有序序列归并操作
merge(unSorted, left, mid, right, sorted);
}
/**
* 归并操作
* @param unSorted 待排序序列
* @param left 第一个序列的起始位置
* @param mid 第二个序列的起始位置
* @param right 序列的结束位置
* @param sorted 两个已排序序列合并后存放的临时序列
*/
private static void merge(int[] unSorted, int left, int mid, int right, int[] sorted){
int i = left; // 左序列的起始下标
int j = mid + 1; //右序列的起始下标
int t = 0; // 临时下标，表示合并后存放的位置
while(i <= mid && j <= right){
if(unSorted[i] < unSorted[j]){
sorted[t++] = unSorted[i++];
}else{
sorted[t++] = unSorted[j++];
}
}
//将左序列剩余的元素填充如临时序列
if(i <= mid){
int len = mid - i + 1;
System.arraycopy(unSorted, i, sorted, t, len);
t += len;
}
//将右序列剩余的元素填充如临时序列
if(j <= right){
int len = right - j + 1;
System.arraycopy(unSorted, j, sorted, t, len);
t += len;
}
//将临时序列中元素拷贝到原序列
System.arraycopy(sorted, 0, unSorted, left, t);
}
/**
* 生成随机序列
* @param min 最小值
* @param max 最大值
* @param len 长度
* @return
*/
private static int[] makeRandomArray(int min, int max, int len){
if(min < 0){
min = 0;
}
if(max > Integer.MAX_VALUE){
max = Integer.MAX_VALUE;
}
if(min > max){
int temp = max;
max = min;
min = temp;
}
if(len < 0){
len = 0;
}
int[] arrays = new int[len];
Random random = new Random();
for(int i = 0; i < len; i++){
arrays[i] = random.nextInt(max) + min;
}
return arrays;
}
/**
* 打印数组
* @param arrays
*/
private static void printArray(int[] arrays){
int len = arrays == null ? 0 : arrays.length;
for(int i = 0; i < len; i++){
System.out.print(arrays[i] + " ");
}
}
}
五、迭代方式
原理图：
图2
原理：
1、将序列的每相邻两个元素进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含一个或两个元素
2、若此时序列数不是1，那么将上面的序列进行归并，形成ceil(n/4)个序列，排序后每个序列包含三个或者四个元素
3、重复步骤2，知道排序完成，即序列上为1
代码实现：
/**
* @author: yongxiang.wei
* @version: 1.2.0, 2018/12/19 9:24
* @since: 1.2.0
*/
public class MergeSort {
public static void main(String[] args){
startInteratorMergeSort();
System.out.println("\n merge sort finished");
}
public static void startInteratorMergeSort(){
//随机生成待排序的序列
// makeRandomArray(0, 30000000, 30000000);
int[] unSorted = makeRandomArray(0, 1000, 10);
System.out.println("Befort merge sorted:");
printArray(unSorted);
iteratorMergeSort(unSorted);
System.out.println("\nAfter merge sorted:");
printArray(unSorted);
}
public static void iteratorMergeSort(int[] arr) {
int len = arr == null ? 0 : arr.length;
if(len < 2){
return;
}
//建一个等长于原数组的临时数组，用于存放合并后的序列
int[] orderedArr = new int[len];
for (int i = 2; i < len * 2; i *= 2) {
for (int j = 0; j < (len + i - 1) / i; j++) {
// 左序列起始位置
int left = i * j;
// 左序列结束位置、右序列的起始位置
int mid = left + i / 2 >= len ? (len - 1) : (left + i / 2);
// 右序列结束位置
int right = i * (j + 1) - 1 >= len ? (len - 1) : (i * (j + 1) - 1);
// 用于存放合并后的序列的起始下标
int start = left;
// 左序列的起始下标
int l = left;
// 左序列的结束下标、右序列的起始下标
int m = mid;
while (l < mid && m <= right) {
if (arr[l] < arr[m]) {
orderedArr[start++] = arr[l++];
} else {
orderedArr[start++] = arr[m++];
}
}
//将左序列剩余的元素填充如临时序列
int mergeLen = mid - l;
if(l < mid){
System.arraycopy(arr, l, orderedArr, start, mergeLen);
start += len;
}
//将右序列剩余的元素填充如临时序列
mergeLen = right - m + 1;
if(m <= right){
System.arraycopy(arr, m, orderedArr, start, mergeLen);
start += len;
}
mergeLen = right - left + 1;
//将临时序列中元素拷贝到原序列
System.arraycopy(orderedArr, left, arr, left, mergeLen);
}
}
}
/**
* 生成随机序列
* @param min 最小值
* @param max 最大值
* @param len 长度
* @return
*/
private static int[] makeRandomArray(int min, int max, int len){
if(min < 0){
min = 0;
}
if(max > Integer.MAX_VALUE){
max = Integer.MAX_VALUE;
}
if(min > max){
int temp = max;
max = min;
min = temp;
}
if(len < 0){
len = 0;
}
int[] arrays = new int[len];
Random random = new Random();
for(int i = 0; i < len; i++){
arrays[i] = random.nextInt(max) + min;
}
return arrays;
}
/**
* 打印数组
* @param arrays
*/
private static void printArray(int[] arrays){
int len = arrays == null ? 0 : arrays.length;
for(int i = 0; i < len; i++){
System.out.print(arrays[i] + " ");
}
}
}
六、结语
1、时间复杂度：最好、最坏、平均均是O(nlogn)
2、空间复杂度：递归：O(n + logn)；迭代：O(n)
3、稳定性： 稳定
3、两种不同实现方式的比较：
a、递归方式：实现上简单易懂，但是会造成时间、空间（需额外的O(logn)）上的损耗
b、迭代方式：实现上相对递归比较没那么清晰易懂，但是不会像递归方式造成额外的时间、空间损耗
ps: 为什么递归方式会造成时间、空间的损耗？因为递归使用了调用自身函数的方式，在jvm中函数就对应的是一个栈帧，对函数的操作除了函数自身内部逻辑实现外，还包括栈帧的入栈和出栈。
其中栈帧是会占用额外的空间，入栈、出栈操作会占用一定的时间
网友评论