归并排序

归并排序（Merge Sort）

工作原理

归并排序是一种基于合并操作的比较排序算法，它利用了分治策略来有效地排序列表。具体步骤如下：

1. 分解：递归地将当前数组分成两个子数组，直到每个子数组只有一个元素。
2. 解决：对每一个子数组进行排序。
3. 合并：将排序好的子数组合并起来形成一个有序的数组。

Java实现

public class MergeSort {

    /**
     * 归并排序算法
     * @param arr 要排序的数组
     */
    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        mergeSort(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid); // 排序左半部分
            mergeSort(arr, mid + 1, right); // 排序右半部分
            merge(arr, left, mid, right); // 合并两个有序部分
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        // 合并两个子数组
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 处理左边剩余的元素
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        // 处理右边剩余的元素
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        // 将临时数组复制回原数组
        for (k = 0; k < temp.length; k++) {
            arr[left + k] = temp[k];
        }
    }

    /**
     * 打印数组中的元素
     * @param arr 数组
     */
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    /**
     * 主函数
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        int[] sampleArray = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Original array:");
        printArray(sampleArray);

        sort(sampleArray);

        System.out.println("Sorted array:");
        printArray(sampleArray);
    }
}

代码解析

1. sort() 方法：这是归并排序的入口方法，它检查数组的有效性，并调用 mergeSort() 方法。
2. mergeSort() 方法：这是一个递归方法，用于分割数组并递归地调用自身。
3. 计算中间点：mid 计算出分割点。
4. 递归调用：分别对左侧和右侧的子数组进行排序。
5. 合并操作：调用 merge() 方法将两个有序的子数组合并。
6. merge() 方法：负责合并两个已排序的子数组，创建一个新的临时数组，将两个子数组合并成一个有序数组，然后复制回原始数组。
7. printArray() 方法：用于打印数组中的元素。
8. main() 方法：测试排序功能的方法。

注意事项

• 时间复杂度：归并排序的时间复杂度在最坏、平均和最好的情况下都是 O(n log n)，其中 n 是数组长度。
• 空间复杂度：由于归并排序需要额外的空间来存储临时数组，因此其空间复杂度为 O(n)。
• 稳定性：归并排序是一种稳定的排序算法，因为相等的元素在排序后保持原来的相对顺序。

适用场景

归并排序非常适合大规模数据的排序任务，尤其是在内存不是主要限制因素的情况下。由于其稳定的性质，归并排序在需要保持元素相对顺序的情况下也非常有用。

希望这段代码及其说明能够帮助您更好地理解和实现归并排序算法。如果您有任何疑问或需要进一步的帮助，请随时告诉我。