文章目录
- 1、概述
- 2、测试代码
- 3、小案例
1、概述
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。
归并排序可以分为两部分，一部分用来分解数组（使用递归的方式），一部分用来合并数组
2、测试代码
核心思想：将这个算法分为分（分解）和治（合并）两部分。将我们最初的数组就不断地递归分解：一分二，二分四，四分八…直到我们数组中的元素变成一个一个的。然后在分（分解）完成的时候，再进行一个治（合并），…八个合并为四个，四个合并为两个，两个合并为一个，每次合并完成时，对应的新数组都是按照顺序排列好的，直到合并为一个已经排好序的数组位置。
public class MergetSortTest01 {
public static void main(String[] args) {
int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
int[] temp = new int[arr.length];
//调用我们的分解、合并的方法
mergeSort(arr, 0, arr.length - 1, temp);
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);
}
}
//二：合并的方法
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left;
int j = mid + 1;
int t = 0;
//这里有两个不同数组：第一个为被合并的数组（不同的位置上的数据），第二个为合并后的新数组
//1.将我们两个数组的数字进行比较，并且按照一定的顺序放入到我们的新的数组里面
while (i <= mid && j <= right) {
//2.将我们被合并的数组的i位置上的值和j位置上的值进行比较，谁小就放谁
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t++;
i++;
} else {
temp[t] = arr[j];
t++;
j++;
}
}
//3.上面的方式的补充部分
//左边的有序序列还有剩余的数字，填充到temp数组中
while (i <= mid) {
//不断的将元数组的index和临时数组的index后移，用于填充数值
temp[t] = arr[i];
t++;
i++;
}
//4.右边的有序序列还有剩余的数字，填充到temp数组中
while (j <= right) {
//不断的将元数组的index和临时数组的index后移，用于填充数值
temp[t] = arr[j];
t++;
j++;
}
//5.将(left~right的)temp数组的元素拷贝到arr中
t = 0;
int tempLeft = left;
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
}3、小案例
利用我们以有的条件，进行一个小案例的测试：计算将数组长度为80000的乱序数组排序所花费的时间
public class MergetSortTest02 {
public static void main(String[] args) {
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random()*80000);
}
long start = System.currentTimeMillis();
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
long end= System.currentTimeMillis();
System.out.println("归并排序的时间为:"+(end-start));
}
//一：分解+合并的方法
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);
}
}
//二：合并的方法
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left;
int j = mid + 1;
int t = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t++;
i++;
} else {
temp[t] = arr[j];
t++;
j++;
}
}
//补充没有赋值到的数据
while (i <= mid) {
temp[t] = arr[i];
t++;
i++;
}
while (j <= right) {
temp[t] = arr[j];
t++;
j++;
}
//完成数组值的交换
t = 0;
int tempLeft = left;
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
}我们的归并排序，递归的次数是指数形式增加的。所以该排序方式，更适合于数据较多的时候使用