1、归并排序介绍
归并排序（Merge Sort）是利归并的思想实现的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
2、归并排序原理
- 申请空间，使它的大小为两个已经排序序列的和，这个空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放到合并空间，并移动指针到下一个位置
- 重复第三步步骤直到某个指针超出序列尾部
- 另一个序列剩下的元素赋值合并到序列尾部
3、归并排序代码实现
public static void main(String[] args) {
int[] arr = {
8, 4, 5, 7, 1, 3, 6, 2}; // 合并的次数为 arr.length - 1
mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
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 k = 0; // 临时数组指针
// 循环条件为左边指针小于等于中间指针，右边指针小于等于最右边指针
while (i <= mid && j <= right) {
// 判断两个指针位置数据大小，存入临时数组中
if (arr[i] <= arr[j]) {
temp[k] = arr[i];
k++;
i++;
} else {
temp[k] = arr[j];
k++;
j++;
}
}
// 循环结束后分别判断如果还有剩余数据的填充到 temp
while (i <= mid) {
temp[k] = arr[i];
k++;
i++;
}
while (j <= right) {
temp[k] = arr[j];
k++;
j++;
}
// 将临时数组中的数据复制到 arr 原始数组中
k = 0;
while (left <= right) {
arr[left] = temp[k];
k++;
left++;
}
}