java排序算法：归并排序_java归并排序算法

归并排序

它基于分治策略，将待排序的数组不断拆分成较小的子序列，直到每个子序列只有一个元素，然后再将这些子序列合并起来，从而得到一个有序的序列。归并排序的基本思想是：将两个已经排好序的子序列合并成一个有序序列，而两个子序列的合并可以采用类似于“归并”的方式进行。

具体来说，归并排序的过程可以分为三个步骤：

分割阶段：将待排序的数组递归地分成两半，直到分割出的子数组只有一个元素为止。
合并阶段：将两个有序的子数组合并成一个有序的数组。
递归结束阶段：当分割出的子数组只有一个元素时，递归结束，排序完成。

废话不多说，上代码！

public static void mergeSort(int[] arr, int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        mergeSort(arr, low, mid); // 对左侧子序列进行归并排序
        mergeSort(arr, mid + 1, high); // 对右侧子序列进行归并排序
        merge(arr, low, mid, high); // 合并左右两个子序列
    }
}

public static void merge(int[] arr, int low, int mid, int high) {
    int[] temp = new int[high - low + 1]; // 创建临时数组
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= high) {
        temp[k++] = arr[j++];
    }
    for (int x = 0; x < temp.length; x++) {
        arr[low + x] = temp[x]; // 将临时数组中的元素复制回原数组
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

mergeSort方法是归并排序的入口方法，它接收待排序数组arr、数组最小下标low和最大下标high作为参数。当low小于high时，表示待排序的数组还可以继续分解，这时候将数组分成两半，分别对左半部分和右半部分进行递归排序，最后再将排好序的左半部分和右半部分进行合并。merge方法是归并排序中的合并操作，它接收待排序数组arr、数组最小下标low、数组中间下标mid和数组最大下标high作为参数。在合并操作中，我们需要创建一个临时数组temp，大小为high - low + 1，用来存放合并后的有序序列。然后用两个指针i和j分别指向左半部分和右半部分的第一个元素，比较两个指针指向的元素的大小，将较小的元素放入临时数组中。如果左半部分或右半部分已经遍历完了，就将剩余部分的所有元素放入临时数组中。最后将临时数组中的元素复制回原数组中。