归并排序介绍
归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治策略(分治法就是将问题分解为小的问题然后递归求解),而治的阶段则将分的阶段得到的答案"修补"在一起,即分而治之.
归并排序思路
归并排序通过不断将原数组进行拆分(通常拆成左右两项),一直到剩下一项,然后分别将拆分的子数组进行合并,此时,两个子数组已经是排好序的,所以合并排序只需要一趟排序就可以完成,所以此类排序需要两个步骤:
-
- 拆分原数组
- 2.合并子数组
拆分原数组
利用递归,不断地寻找左子数组和右子数组,知道数组长度为1.
合并算法的思想
每次合并需要子数组A,B，并新创建一个临时数组C，同时需要三个计数器Actr，Bctr和Cctr[数组C计数器]，其中Actr和Bctr用来判断数组是否用完，如果用完，则将剩余的数组元素按顺序放入临时数组中。全部放完后，将临时数组中的已经排好顺序的元素更新到原数组中。
比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤
代码实现
public class MergeSort {
public static void main(String[] args) {
int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
//定义一个中间数组
int[] temp = new int[arr.length];
System.out.println("排序前的结果为:");
System.out.println(Arrays.toString(arr));
mergeSort(arr, 0, arr.length - 1, temp);
System.out.println("排序后的结果为:");
System.out.println(Arrays.toString(arr));
}
/**
* @param arr 待排序的数组
* @param left 待排序序列的left指针
* @param right 待排序序列的right指针
* @param temp 中间数组
*/
private static void mergeSort(int[] arr, int left, int right, int[] temp) {
//分解
int mid = (left + right) / 2;
if (left < right) {
//左边递归
mergeSort(arr, left, mid, temp);
//右边递归
mergeSort(arr, mid + 1, right, temp);
//合并
merge(arr, left, mid, right, temp);
}
}
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
//左边序列的第一个索引
int i = left;
//右边序列的第一个索引
int j = mid + 1;
//temp 数组的下标,用于存值时自增
int index = 0;
//还没一个序列遍历到最后,即需要比较两个序列找出最小的,添加到temp数组中
while (i <= mid && j <= right) {
if (arr[i] > arr[j]) {
temp[index] = arr[j];
j++;
index++;
} else {
temp[index] = arr[i];
i++;
index++;
}
}
//有一方已经遍历完了,只需要将剩下一方的所有元素,添加到数组中
while (i <= mid) {
temp[index] = arr[i];
i++;
index++;
}
while (j <= right) {
temp[index] = arr[j];
j++;
index++;
}
//将temp数组中的元素拷贝到arr中,并不是没有都需要进行arr.length次拷贝,而是需要进行right - left次即可
int tempLeft = left;
index = 0; // 重置索引为0
while (tempLeft <= right) {
arr[tempLeft] = temp[index];
tempLeft++;
index++;
}
}
}
排序前的结果为:
[8, 4, 5, 7, 1, 3, 6, 2]
排序后的结果为:
[1, 2, 3, 4, 5, 6, 7, 8]