内部排序和外部排序全景剖析：聚焦归并排序

内部排序和外部排序全景剖析：聚焦归并排序

引用

CSDN

1.

https://blog.csdn.net/weixin_62785232/article/details/143457348

一、归并排序概述

归并排序是一种基于分治思想的高效排序算法，在计算机科学领域有着广泛的应用。它的时间复杂度为 O(n log n)，在处理大规模数据时表现出较高的效率。归并排序不仅可以用于对整数数组进行排序，还可以用于对其他数据类型的序列进行排序，如字符串、结构体等。此外，归并排序的思想还可以应用于其他算法和数据结构中，如数据库的排序操作、外部排序等。

二、归并排序原理

2.1 分治策略

归并排序完美地体现了分治策略的思想。它首先将待排序的大问题分解成若干个较小规模的子问题。具体来说，归并排序把一个包含多个元素的数组不断地进行二等分，将其分割成越来越小的子数组。这样一直持续下去，直到每个子数组中只有一个元素为止。此时，单个元素的子数组天然就是有序的。

接着，归并排序开始分别解决这些子问题。对于单个元素的子数组，无需进行实际的排序操作，因为它本身就是有序的。然后，归并排序进入合并阶段，将这些已经处理好的有序子数组合并起来，逐步构建出更大的有序数组。最终，通过不断地合并子数组，得到完全有序的原始数组。

2.2 分解与合并过程

2.2.1 分解

归并排序的分解过程非常直观。从原始数组开始，每次将其划分为大致相等的两部分。例如，对于一个长度为 8 的数组，首先将其分为两个长度为 4 的子数组。然后，对这两个子数组继续进行分解，得到四个长度为 2 的子数组。再进一步分解，就得到了八个长度为 1 的子数组。在这个过程中，通过不断地二等分，将问题规模逐渐缩小，直到每个子数组中只有一个元素，无法再继续分解。

2.2.2 合并

合并过程采用双指针归并法。假设我们有两个已排序的子数组，分别用指针 i 和 j 指向它们的第一个元素。同时，创建一个新的数组用于存储合并后的结果，并使用指针 k 指向新数组的第一个位置。比较指针 i 和 j 所指的元素大小，将较小的元素放入新数组中，并将对应的指针向后移动一位。重复这个过程，直到其中一个子数组的所有元素都被放入新数组中。此时，将另一个子数组中剩余的元素直接依次全部放入新数组中。例如，有两个子数组 [2, 4, 6] 和 [1, 3, 5]，首先比较 2 和 1，将 1 放入新数组，指针 j 后移一位。接着比较 2 和 3，将 2 放入新数组，指针 i 后移一位。以此类推，最终得到有序数组 [1, 2, 3, 4, 5, 6]。

三、内部排序和外部排序

3.1 内部排序

内部排序是指待排序的数据全部存放在计算机内存中进行的排序过程。常见的内部排序算法有冒泡排序、插入排序、选择排序、希尔排序、快速排序、归并排序、堆排序等。这些算法的时间复杂度和空间复杂度各不相同，适用于不同的场景。

3.2 外部排序

外部排序是指待排序的数据量很大，不能一次全部装入内存，而需要在内存和外部存储器（如磁盘）之间进行多次数据交换的排序过程。外部排序通常采用归并排序的方法。

以文件通常按块存储在磁盘上为例，操作系统也是按块对磁盘上的信息进行读写。外部排序过程中的时间代价主要考虑访问磁盘的次数，即 I/O 次数。外部排序通常包括两个相对独立的阶段：

• 根据内存缓冲区大小，将外存上的文件分成若干长度的子文件，依次读入内存并利用内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串。
• 对这些归并段进行逐趟归并，使归并段（有序子文件）逐渐由小到大，直至得到整个有序文件为止。

3.3 内部排序与外部排序的差别

• 数据存储位置：内部排序的数据全部在内存中，而外部排序的数据量很大，不能一次全部装入内存，需要在内存和外部存储器之间进行多次数据交换。
• 衡量效率的方法：内部排序通常比较次数，即时间复杂度来衡量效率；外部排序主要考虑访问磁盘的次数，即 I/O 次数。
• 适用场景：内部排序适用于数据量较小的情况，而外部排序适用于数据量很大的情况。

例如，对于一个包含 10000 个记录的文件，内部排序可能无法一次性处理这么多数据，而需要采用外部排序的方法。首先将文件分成若干个长度为 L 的子文件，进行内部排序后得到归并段，然后对这些归并段进行逐趟归并，最终得到整个有序文件。

四、内部归并排序实现

归并排序的实现通常分为两个主要部分：分治和合并。以下是对内部归并排序代码的详细注释讲解。

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

package mergesort;
import static java.util.Arrays.stream;

/**
 * 归并排序
 */
public class MergeSort {
    public static void main(String[] args) {
        //初始数组
        int[] a = new int[] { 9, 8, 4, 6, 5, 7, 3, 2, 10 };
        //中间数组
        int[] t = new int[a.length];
        //开始排序
        mergeSort(a, 0, a.length - 1, t);
        //遍历输出
        stream(a).forEach(s -> System.out.print(s + " "));
    }

    /**
     * 分治 合并
     * @param a 待排序数组
     * @param left 最左下标
     * @param right 最右下标
     * @param t 中间数组
     */
    public static void mergeSort(int[] a, int left, int right, int[] t) {
        if (left < right) {
            //中间下标
            int mid = (left + right) / 2;
            mergeSort(a, left, mid, t); //左
            mergeSort(a, mid + 1, right, t); //右
            merge(a, left, mid, right, t); //合并
        }
    }

    // 合并的方法
    public static void merge(int[] a, int left, int mid, int right, int[] temp) {
        // i 表示左边有序序列的初始下标
        int i = left;
        // j 表示右边有序序列的初始下标
        int j = mid + 1;
        // k 表示 t 临时数组的当前下标
        // ①先把左右两边(已经有序)的数据按照规则填充到 t 数组
        // 直到左右两边的有序序列，有一边处理完毕为止
        int k = 0;
        while (i <= mid && j <= right) {
            // 如果左边的有序序列的当前元素，小于等于右边序列的当前元素
            // 那么就把左边的有序序列的当前元素拷贝到 t 数组中
            if (a[i] <= a[j]) {
                temp[k] = a[i];
                i++;
                k++;
            } else if (a[j] < a[i]) {
                temp[k] = a[j];
                j++;
                k++;
            }
        }
        // ②把有剩余数据的一边的数据一次全部填充到 t
        while (i <= mid) {
            temp[k] = a[i];
            i++;
            k++;
        }
        while (j <= right) {
            temp[k] = a[j];
            j++;
            k++;
        }
        // ③将 t 数组的元素拷贝到 a
        // 注意：并不是每次都拷贝所有！！！
        k = 0;
        int tempLeft = left;
        // 其实直接用 left 就可以
        while (tempLeft <= right) {
            a[tempLeft] = temp[k];
            k++;
            tempLeft++;
        }
    }
}

在这个实现中，mergeSort方法首先将数组不断地分割为较小的子数组，直到每个子数组只有一个或零个元素。然后，它调用merge方法将这些子数组合并起来。

merge方法使用三个指针i、j和t分别指向左边子数组、右边子数组和临时数组temp的当前位置。它比较左右子数组的元素，并将较小的元素放入临时数组中。最后，将临时数组中的元素拷贝回原始数组。

例如，对于数组[4, 1, 3, 2]，首先将其分割为[4, 1]和[3, 2]，然后继续分割为[4]、[1]、[3]和[2]。接着，合并[4]和[1]得到[1, 4]，合并[3]和[2]得到[2, 3]。最后，合并[1, 4]和[2, 3]得到[1, 2, 3, 4]。

五、外部归并排序

外部归并排序实现对一个超长字符串文本文件进行字典序排列。

外部归并排序通常将大文件分割成多个小文件进行处理，然后逐步合并这些小文件以得到最终的有序结果。以下是一个实现外部归并排序对超长字符串文本文件进行字典序排列的步骤：

5.1 分割大文件

首先，确定一个合适的块大小。例如，根据可用内存大小，我们可以选择将大文件分割成每个大小为 100MB 的小文件。假设我们有一个 1GB 的文本文件，那么这个文件将被分割成 10 个小文件。

5.2 局部排序小文件

由于小文件的大小适中，可以将其全部加载到内存中进行排序。可以使用快速排序、归并排序或其他高效的内部排序算法。在上述代码中，直接在读取文件内容后进行了排序，这样每个小文件都是有序的。

5.3 归并小文件

归并小文件是外部归并排序的关键步骤。可以使用类似于内部归并排序中的双指针归并法，但需要考虑文件的读取和写入操作。具体实现可以参考内部归并排序的合并过程，但需要将数组操作替换为文件读写操作。

例如，假设我们有 10 个已排序的小文件，每次从每个文件中读取一个元素进行比较，将最小的元素写入新的输出文件中。当某个文件的所有元素都被读取完毕后，就不再从该文件中读取元素。重复这个过程，直到所有小文件中的元素都被处理完毕，最终得到一个完全有序的大文件。

总结来说，外部归并排序通过将大文件分割成小文件进行局部排序，然后逐步归并这些小文件，最终实现对大规模数据的排序。这种方法特别适用于数据量远大于内存容量的情况，通过减少内存使用和优化磁盘 I/O 操作，能够有效地处理大规模数据排序问题。