首页　>　文章列表　>　逐步分解Java代码实现归并排序

逐步分解Java代码实现归并排序

305 2024-02-19

逐步解析Java归并排序代码的实现过程

引言：
归并排序是一种经典的分而治之算法，将一个数组分成两个较小的数组，然后分别对这两个数组进行排序，最后将两个排序后的数组合并成一个有序的数组。在本文中，我们将逐步解析Java中归并排序的实现过程，并提供具体代码示例。

基本思路：
归并排序的基本思路是通过递归地将待排序数组拆分成两个更小的子数组，然后再将这两个子数组排序，并合并为一个有序数组。这个过程会一直递归下去，直到最小的子数组只有一个元素，然后通过合并这些有序子数组，完成排序。
实现过程：
以下是Java中归并排序的实现过程：

class MergeSort {
    // 归并排序函数
    public void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            // 找出中点
            int mid = (left + right) / 2;

            // 递归排序左半部分和右半部分
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);

            // 合并排序好的左半部分和右半部分
            merge(array, left, mid, right);
        }
    }

    // 合并函数
    public void merge(int[] array, int left, int mid, int right) {
        // 定义临时数组来存储合并后的数组
        int[] temp = new int[right - left + 1];

        int i = left;
        int j = mid + 1;
        int k = 0;

        // 将左半部分和右半部分按顺序合并到临时数组中
        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        // 将剩余的元素复制到临时数组中
        while (i <= mid) {
            temp[k++] = array[i++];
        }

        while (j <= right) {
            temp[k++] = array[j++];
        }

        // 将临时数组中的元素复制回原数组
        for (int m = 0; m < temp.length; m++) {
            array[left + m] = temp[m];
        }
    }

    // 测试
    public static void main(String[] args) {
        int[] array = {8, 5, 2, 9, 5, 6, 3};
        int n = array.length;

        MergeSort mergeSort = new MergeSort();
        mergeSort.mergeSort(array, 0, n - 1);

        System.out.println("归并排序结果：");
        for (int i = 0; i < n; i++) {
            System.out.print(array[i] + " ");
        }
    }
}

示例说明：
上述代码中，mergeSort方法是归并排序的入口函数，它接收一个待排序的数组以及数组的左右边界。在该函数中，我们首先判断左右边界是否满足拆分的条件（即left < right），如果满足，则找出数组的中点，并递归调用mergeSort函数对左半部分和右半部分进行排序。最后，调用merge函数将两个有序的子数组合并为一个有序的数组。

merge函数中，我们创建一个临时数组来存储合并后的子数组，然后定义三个指针i、j、k分别指向左半部分的起始位置、右半部分的起始位置以及临时数组的起始位置。我们比较左半部分和右半部分的元素大小，将较小的元素放入临时数组中，并将对应指针后移一位。如果某一个子数组的所有元素都放入了临时数组中，那么我们将剩下子数组中的元素复制到临时数组的末尾。最后，我们将临时数组中的元素复制回原数组。