归并排序介绍:
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
归并排序示意图
归并排序示意图
说明:
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程。
归并排序思想示意图-合并相邻有序子序列:
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤
归并
归并
代码实现
package cn.icanci.datastructure.sort;
import javax.swing.*;
import java.util.Arrays;
/**
* @Author: icanci
* @ProjectName: AlgorithmAndDataStructure
* @PackageName: cn.icanci.datastructure.sort
* @Date: Created in 2020/3/7 10:47
* @ClassAction: 归并排序
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = {8, 4, 5, 7, 1, 3, 6, 2,123,324,546,457,234,1234,534,12,313,1345,346,3};
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
System.out.println("归并排序之后");
System.out.println(Arrays.toString(arr));
}
//分+合的方法
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;
//向左递归分解
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
//合并
merge(arr,left,mid,right,temp);
}
}
/**
* 合并的方法
*
* @param arr 排序的原始数组
* @param left 左边
* @param mid 中间
* @param right 右边
* @param temp 临时数组
*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
//初始化 i ,左边有序序列的索引
int i = left;
//初始化节点 j 右边有序序列的初始索引
int j = mid + 1;
//指向 temp的当前索引
int t = 0;
//先把所有的两边(有序)的数据 填充到temp数组
//知道有一方处理完毕则结束
while (i <= mid && j <= right) {
//继续
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t++;
i++;
} else {
temp[t] = arr[j];
t++;
j++;
}
}
//再把剩余数据的一般的数据依次填充到temp
while (i <= mid) {
//左边有剩余 全部填充到temp
temp[t] = arr[i];
t++;
i++;
}
while (j <= right) {
//左边有剩余 全部填充到temp
temp[t] = arr[j];
t++;
j++;
}
//最有把temp的数组元素拷贝到arr
//最后一次拷贝
t = 0;
int tempLeft = left;
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t++;
tempLeft++;
}
}
}
测试8000000条数据
package cn.icanci.datastructure.sort;
import cn.icanci.datastructure.utils.GetNumberArray;
import javax.swing.*;
import java.util.Arrays;
/**
* @Author: icanci
* @ProjectName: AlgorithmAndDataStructure
* @PackageName: cn.icanci.datastructure.sort
* @Date: Created in 2020/3/7 10:47
* @ClassAction: 归并排序
*/
public class MergeSort {
public static void main(String[] args) {
// int[] arr = {8, 4, 5, 7, 1, 3, 6, 2,123,324,546,457,234,1234,534,12,313,1345,346,3};
System.out.println("排序之前");
int[] numberArray = GetNumberArray.getNumberArray(8000000);
int[] temp = new int[numberArray.length];
long start = System.currentTimeMillis();
mergeSort(numberArray, 0, numberArray.length - 1, temp);
System.out.println(System.currentTimeMillis() - start + ":ms");
System.out.println("归并排序之后");
}
//分+合的方法
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;
//向左递归分解
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
//合并
merge(arr,left,mid,right,temp);
}
}
/**
* 合并的方法
*
* @param arr 排序的原始数组
* @param left 左边
* @param mid 中间
* @param right 右边
* @param temp 临时数组
*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
//初始化 i ,左边有序序列的索引
int i = left;
//初始化节点 j 右边有序序列的初始索引
int j = mid + 1;
//指向 temp的当前索引
int t = 0;
//先把所有的两边(有序)的数据 填充到temp数组
//知道有一方处理完毕则结束
while (i <= mid && j <= right) {
//继续
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t++;
i++;
} else {
temp[t] = arr[j];
t++;
j++;
}
}
//再把剩余数据的一般的数据依次填充到temp
while (i <= mid) {
//左边有剩余 全部填充到temp
temp[t] = arr[i];
t++;
i++;
}
while (j <= right) {
//左边有剩余 全部填充到temp
temp[t] = arr[j];
t++;
j++;
}
//最有把temp的数组元素拷贝到arr
//最后一次拷贝
t = 0;
int tempLeft = left;
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t++;
tempLeft++;
}
}
}
打印
排序之前
1424:ms
归并排序之后
