归并排序——内排序方式

引言

归并排序（Merge Sort）是一种分治法（Divide and Conquer）排序算法，它将一个大的数组分解为多个小的子数组，再通过合并操作将这些子数组有序地合并成一个最终的有序数组。

归并排序的实现原理

归并排序的核心思想是将一个数组分成两个子数组，分别排序后再将它们合并成一个有序数组。具体步骤如下：

1. 分解：将数组分成两半，分别对这两半进行归并排序。
2. 排序：递归地对两个子数组进行排序，直到子数组的长度为1（此时已经是有序的）。
3. 合并：合并两个有序子数组，得到一个更大的有序数组。合并的过程是将两个有序数组按顺序比较，将较小的元素放到结果数组中，直到某个数组的元素全部放入结果中，剩下的直接放入。

归并排序具有 O(n log n) 的时间复杂度，不论数据的初始状态如何，它的时间复杂度始终是 O(n log n)，因此是一种高效的排序算法。

归并排序的代码实现

#include <iostream>
using namespace std;

// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 使用动态内存分配来创建临时数组
    int* leftArr = new int[n1];
    int* rightArr = new int[n2];

    // 将数据复制到临时数组中
    for (int i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (int i = 0; i < n2; i++)
        rightArr[i] = arr[mid + 1 + i];

    // 合并两个有序数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    // 将剩余的元素拷贝到原数组
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }

    // 释放动态分配的内存
    delete[] leftArr;
    delete[] rightArr;
}

// 归并排序主函数
void mergeSort(int arr[], int left, int right) {
    if (left >= right)
        return;  // 递归终止条件

    // 找到中间点
    int mid = left + (right - left) / 2;

    // 递归地对两个子数组进行排序
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    // 合并排序后的两个子数组
    merge(arr, left, mid, right);
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    mergeSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

代码解析

1. merge 函数：
   • merge 是归并排序的核心部分。它负责将两个有序的子数组合并成一个有序数组。
   • leftArr 和 rightArr 是临时数组，用来存储左右两个子数组。
   • 然后通过三个指针 i, j, k 分别表示左右子数组和合并数组的位置，逐个比较两个子数组的元素，将较小的元素放入合并后的数组 arr[k] 中。
   • 最后如果某个子数组还剩下元素，直接将剩余的元素拷贝到合并数组中。
2. mergeSort 函数：
   • mergeSort 是递归函数，它通过不断地将数组分成两半，直到数组的大小为 1，然后调用 merge 函数将它们合并。
   • 每次递归时，先计算中间点 mid = left + (right - left) / 2，然后递归排序左半部分和右半部分。
   • 最终两个排序好的部分会在 merge 函数中合并。
3. printArray 函数：
   • 用于输出数组，帮助查看排序前后的结果。
4. main 函数：
   • 在 main 函数中，定义了一个待排序的数组 arr[]，并调用 mergeSort 对数组进行排序，最后打印排序后的数组。

归并排序的时间复杂度

• 时间复杂度：
  • 归并排序的时间复杂度为 O(n log n)，不论数据是否已经有序。
  • 这是因为每一层递归需要 O(n) 的时间来进行合并，而递归的深度是 O(log n)，因此总体的时间复杂度是 O(n log n)。
• 空间复杂度：
  • 归并排序的空间复杂度为 O(n)，因为我们需要额外的空间来存储临时数组 leftArr 和 rightArr。
  • 虽然归并排序是稳定排序，但它并不是原地排序算法，因此需要额外的空间。

归并排序的优缺点

优点：

• 稳定排序：相等的元素不会改变相对顺序。
• 时间复杂度保证：最坏情况下的时间复杂度为 O(n log n)，比许多其他算法（如插入排序、选择排序）更优。
• 适合大规模数据：归并排序尤其适用于大规模数据的排序。

缺点：

• 空间消耗大：由于需要额外的临时数组存储合并结果，归并排序的空间复杂度较高。
• 较慢的常数因子：对于小规模数据，归并排序的性能不如其他简单排序算法，如插入排序，因为它需要额外的内存和合并过程。

总结

归并排序是一种稳定、高效的排序算法，时间复杂度始终为 O(n log n)，在大规模数据集上的表现非常出色。它采用了分治法的思想，通过不断分割数组并合并子数组来完成排序。尽管它的空间复杂度较高，但在很多应用场景中仍然是首选算法。

归并排序的优化

在优化后的归并排序实现中，主要是保持了归并排序的时间复杂度 O(n log n)，同时在内存管理方面进行了优化，以提高程序的空间效率。接下来我将详细讲解优化后的实现思路。

优化实现思路

1. 递归结构的保持

归并排序的核心思想是通过递归将数组分割成两个子数组，直到每个子数组只有一个元素，然后再将这些有序子数组合并起来。递归结构本身没有被改变。我们通过 mergeSort 函数实现了这个递归过程。

void mergeSort(int arr[], int left, int right) {
    if (left >= right)
        return;  // 递归终止条件

    int mid = left + (right - left) / 2;  // 防止溢出
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);  // 合并两个有序子数组
}

• mergeSort 中使用了递归来处理左右子数组的排序。
• 递归会一直分割数组，直到每个子数组只包含一个元素（这时的子数组是有序的）。
• 一旦递归的基准条件满足（即 left >= right），递归就会停止。

2. 合并过程的优化

合并两个有序子数组是归并排序的关键步骤。对于每一轮递归，两个子数组被合并成一个更大的有序数组。在优化后的代码中，使用了临时数组来存储中间结果，避免了每次合并时对原数组的多次访问，提升了效率。

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 动态内存分配临时数组
    int* leftArr = new int[n1];
    int* rightArr = new int[n2];

    // 将数据复制到临时数组中
    for (int i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (int i = 0; i < n2; i++)
        rightArr[i] = arr[mid + 1 + i];

    // 合并两个有序数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    // 将剩余的元素拷贝到原数组
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }

    // 释放动态分配的内存
    delete[] leftArr;
    delete[] rightArr;
}

这里的优化包括：

• 动态内存分配：通过 new 动态分配了临时数组 leftArr 和 rightArr 来存储左、右子数组的元素。这样每次合并时不会重复使用原数组，从而避免了额外的访问和复制。
• 合并操作：合并两个子数组时，通过一个循环来对比左右子数组的元素，将较小的元素放到原数组中。合并操作保证了每一轮都尽量高效地执行。
• 释放内存：使用 delete[] 释放了动态分配的内存，防止内存泄漏。

3. 递归深度的控制

在大多数情况下，递归的深度等于 log n，每次递归调用会将数组分为两个子数组。因为每次分割都会消耗一定的栈空间，所以递归的深度不能太深。幸运的是，归并排序的递归深度是对数级的，因此归并排序对于大规模数据集也比较合适。

4. 合并的空间复杂度

• 空间复杂度 O(n)：由于我们需要使用临时数组来存储每个子数组的元素，空间复杂度为 O(n)。
• 优化：虽然归并排序通常需要额外的空间，但在这段代码中，我们通过动态分配内存使得每次合并都仅分配与当前子数组大小相同的临时数组，从而避免了多余的内存浪费。

5. 递归基准条件

• 当子数组的大小为 1 时，递归会停止，这是一种最基本的排序单元。
• 当递归到达这一点时，不需要进一步处理，因此终止递归。

6. 打印结果

最后通过 printArray 函数输出排序结果，验证归并排序的正确性。

总结

优化后的归并排序实现的思路是：

• 递归划分数组：每次将数组划分成两个子数组，直到每个子数组只含一个元素。
• 合并操作：合并有序子数组时，使用动态内存分配的临时数组来存储每次合并的结果，确保每个合并步骤高效执行。
• 内存管理：通过 new 和 delete[] 动态管理内存，避免了不必要的内存泄漏和浪费。

这使得代码在保持最优时间复杂度 O(n log n) 的同时，在内存使用上也进行了优化。