深入了解归并排序：原理、性能分析与 Java 实现

冷不防 2023-10-16 18:27 8阅读 0赞

归并排序（Merge Sort）是一种高效且稳定的排序算法，其优雅的分治策略使它成为排序领域的一颗明珠。它的核心思想是将一个未排序的数组分割成两个子数组，然后递归地对子数组进行排序，最后将这些排好序的子数组合并起来。

![mergesort.jpg][]

#### 什么是归并排序？ ####

归并排序是一种分治策略的排序算法，它的核心思想是将数组分成两个子数组，递归地对子数组进行排序，然后将排序好的子数组合并起来，最终得到有序的数组。归并排序的关键步骤包括：

1.  分割阶段： 将数组分成两个子数组，通常是平均分割。
2.  递归排序： 递归地对左右两个子数组进行排序。
3.  合并阶段： 将排好序的子数组合并成一个新的有序数组。

![mergesort.png][]

#### 归并排序的性能分析 ####

归并排序在性能方面有以下特点：

*  时间复杂度： 归并排序的平均、最好和最坏情况下时间复杂度均为  O ( n l o g n ) O(n log n) O(nlogn)，这使它成为高效的排序算法。
 *  空间复杂度： 归并排序通常需要额外的内存空间来存储临时数据，因此其空间复杂度为  O ( n ) O(n) O(n)。
 *  稳定性： 归并排序是稳定的排序算法，相等元素的相对顺序在排序后不会改变。
 *  适用场景： 归并排序适用于各种数据规模和数据类型，特别适用于外部排序，如大文件的排序。

#### Java 代码实现 ####

以下是使用 Java 实现归并排序的示例代码：

public class Test {
    
        public static void main(String[] args) {
            int[] arr = new int[]{7,5,2,3,6,4};
            System.out.println("原始数组："+ Arrays.toString(arr));
            mergeSort(arr);
            System.out.println("排序后的数组："+ Arrays.toString(arr));
        }
    
        // 归并排序的入口方法
        public static void mergeSort(int[] arr) {
            // 针对特殊情况，数组为空或只有一个元素时，无需排序
            if(arr == null || arr.length <= 1  ){
                return;
            }
            // 创建一个临时数组用于归并操作
            int[] temp = new int[arr.length];
    
            // 调用实际的排序方法，传入数组、左边界、右边界和临时数组
            sort(arr, 0, arr.length - 1, temp);
        }
    
        // 归并排序的核心排序方法(递归调用的方法)
        public static void sort(int[] arr,int left,int right,int[] temp) {
            //递归终止的条件
            if(left < right){
                //计算中间位置分割的下标
                int mid = (right + left) / 2;
                // 递归对左半部分进行排序
                sort(arr, left, mid, temp);
                // 递归对右半部分进行排序
                sort(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 = left;
    
            // 比较左右两部分的元素，并将较小的元素放入临时数组
            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 (int l = left; l <= right; l++) {
                arr[l] = temp[l];
            }
        }
    
    }

输出结果：

原始数组：[7, 5, 2, 3, 6, 4]
    排序后的数组：[2, 3, 4, 5, 6, 7]

这段代码演示了如何使用 Java 实现归并排序算法。它通过递归将数组分割为子数组，然后合并这些子数组，最终得到排序完成的数组。

#### 总结 ####

总之，归并排序是一种高效、稳定的排序算法，适用于各种规模和类型的数据。虽然它的空间复杂度较高，但在实际应用中，它的性能通常非常出色。这使得它成为排序算法家族中的重要一员。

[mergesort.jpg]: https://img-blog.csdnimg.cn/img_convert/c5cbf6afccfa5833d32cd74cb820fcba.jpeg
[mergesort.png]: https://img-blog.csdnimg.cn/img_convert/057919ffd683de599acf78aec461e22e.png