当前位置：首页 > article >正文

【稳定且高效的分治排序 —— 归并排序算法】

article 2024/9/27 9:09:29

【稳定且高效的分治排序 —— 归并排序算法】

归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法，采用分治法的典型应用。将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。

归并排序的主要步骤包括分割和合并。分割是将待排序的数组不断分成较小的子数组，直到每个子数组只有一个元素，此时每个子数组都是有序的。合并则是将两个有序的子数组合并成一个更大的有序数组。
在这里插入图片描述

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

public class MergeSort {
    // 将 arr(l...mid) 和 arr(mid+1...r) 两部分进行归并
    private static void merge(Comparable[] arr, int l, int mid, int r) {
        Comparable[] temp = new Comparable[r - l + 1];
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            temp[k++] = (arr[i].compareTo(arr[j]) <= 0)? arr[i++] : arr[j++];
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= r) temp[k++] = arr[j++];
        for (i = l; i <= r; i++) arr[i] = temp[i - l];
    }
}

在 Python 中，归并排序可以这样实现：

def mergeSort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        mergeSort(lefthalf)
        mergeSort(righthalf)
        i = j = k = 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i += 1
            else:
                alist[k] = righthalf[j]
                j += 1
            k += 1
        while i < len(lefthalf):
            alist[k] = lefthalf[i]
            i += 1
            k += 1
        while j < len(righthalf):
            alist[k] = righthalf[j]
            j += 1
            k += 1
    return alist

归并排序的时间复杂度为 O(n log n)，空间复杂度为 O(n)。它的优点是稳定，适用于对稳定性有要求的排序场景。但缺点是需要额外的存储空间。归并排序在处理大规模数据时表现出色，尤其对于数据量较大且对稳定性有要求的情况，是一种可靠的排序算法选择。

归并排序算法步骤

归并排序是一种典型的分治算法应用。其步骤如下：
首先是分解阶段，将待排序的序列不断地分成两个部分，直到每个子序列只包含一个元素，此时认为子序列已经有序。例如对于序列{8, 6, 9, 5, 7}，第一次分解为{8, 6, 9}和{5, 7}，再进一步分解为{8, 6}、{9}、{5}、{7}等。
接着是解决问题阶段，因为单个元素的子序列本身就是有序的，所以这个阶段在分解到最小子序列时自动完成。
最后是合并阶段，将两个有序的子序列合并成一个有序序列。比如将{8, 6}合并为{6, 8}，将{5, 7}合并为{5, 7}，再将{6, 8}和{9}合并为{6, 8, 9}，最后将{6, 8, 9}和{5, 7}合并为{5, 6, 7, 8, 9}。

在合并过程中，通常会创建一个临时数组来存储合并后的结果。比如有两个有序子序列 A 和 B，定义两个指针分别指向 A 和 B 的起始位置，同时创建一个辅助指针指向临时数组的起始位置。比较两个指针所指向的元素，较小的元素放入临时数组，对应的指针和辅助指针均向后移动一位。重复这个过程，直到某一指针到达序列尾。此时将另一序列剩下的所有元素直接复制到临时数组。最后，将临时数组中的元素填充回原数组。

归并排序算法优点

归并排序算法具有以下优点：

稳定性：归并排序保证了相等元素的相对顺序不变，适合于需要维持原有顺序的应用场景。例如在对包含多个相同元素的序列进行排序时，归并排序能够确保相同元素的先后顺序不发生改变。
时间复杂度稳定：无论输入数据是否已经部分有序，归并排序都能确保最坏、最好和平均时间复杂度均为 O(n log n)，具有较好的平均和最坏情况下的性能表现。这使得归并排序在处理各种不同类型的数据时都能保持较为高效的性能。
适用大规模数据：尽管归并排序由于需要额外空间进行合并可能不适合内存受限的情况，但在处理大文件或流式数据时，可通过外部存储辅助完成排序（外排序）。例如在处理大规模数据集时，可以将数据分成小块进行排序，然后再逐步合并，从而有效地处理大规模数据。
逻辑清晰：归并排序算法思路简洁明了，易于理解和实现，有助于初学者掌握分治策略的核心思想。其分解、解决和合并的步骤明确，使得程序员在实现该算法时能够清晰地把握整个过程。

归并排序算法缺点

归并排序算法存在以下缺点：

空间复杂度高：归并排序需要额外的空间来存储临时数组，其空间复杂度为 O(n)。在处理大规模数据时，这可能会占用大量的内存空间，特别是在内存受限的环境下，可能会导致性能问题。
不是原地排序：与一些原地排序算法相比，归并排序需要额外的空间来完成排序过程，不能在原数组上直接进行排序操作。这在一些对内存空间要求严格的场景下可能不太适用。