C++ 实现归并排序

归并排序的基本概念

什么是归并排序

归并排序（Merge Sort）是建立在归并操作上的一种高效、稳定的排序算法，属于分治算法的典型应用。其基本思想是将一个序列逐步拆分成较小的子序列，分别对这些子序列进行排序，然后再将排序好的子序列合并起来，最终得到一个完整的、有序的序列。

分治思想在归并排序中的体现

1. 分解（Divide）：将待排序的序列不断地分成两个大致相等的子序列。例如，对于一个长度为 n 的序列，每次将其从中间位置划分，得到两个长度约为 n/2 的子序列。这个过程递归地进行，直到子序列的长度为 1（因为长度为 1 的序列本身就是有序的）。
2. 解决（Conquer）：对每个划分得到的子序列进行排序。由于子序列已经足够小，排序相对容易。在这里，当子序列长度为 1 时无需额外排序，对于长度大于 1 的子序列，可以继续使用归并排序的方法进行排序。
3. 合并（Merge）：将排序好的子序列按照顺序合并成一个更大的有序序列。这个过程是归并排序的核心操作，通过比较两个子序列的元素，将较小的元素依次放入一个新的临时序列中，最终将临时序列的内容复制回原序列，完成一次合并。

C++ 实现归并排序的步骤

分解步骤的实现

在 C++ 中，我们可以通过递归函数来实现分解步骤。以下是一个简单的递归函数框架，用于将序列不断分解：

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);
    }
}

在这个函数中，left 和 right 分别表示当前要处理的序列的起始和结束索引。首先计算中间位置 mid，然后递归调用 mergeSort 对左半部分 [left, mid] 和右半部分 [mid + 1, right] 进行排序，最后调用 merge 函数进行合并。

合并步骤的实现

合并步骤是将两个已排序的子序列合并成一个更大的有序序列。下面是 merge 函数的实现：

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

    // 创建临时数组
    int L[n1], R[n2];

    // 复制数据到临时数组 L[] 和 R[]
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;

    // 合并临时数组回到原数组
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 复制 L[] 中剩余的元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 复制 R[] 中剩余的元素
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

在 merge 函数中，首先计算两个子序列的长度 n1 和 n2，然后创建两个临时数组 L 和 R 分别存储这两个子序列。接着通过两个指针 i 和 j 分别遍历 L 和 R，比较对应位置的元素，将较小的元素放入原数组 arr 中。当其中一个临时数组遍历完后，将另一个临时数组中剩余的元素直接复制到原数组。

完整的 C++ 代码示例

#include <iostream>

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

    // 创建临时数组
    int L[n1], R[n2];

    // 复制数据到临时数组 L[] 和 R[]
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;

    // 合并临时数组回到原数组
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 复制 L[] 中剩余的元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 复制 R[] 中剩余的元素
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序主函数
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);
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arrSize = sizeof(arr) / sizeof(arr[0]);

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

    mergeSort(arr, 0, arrSize - 1);

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

    return 0;
}

在 main 函数中，我们定义了一个数组 arr 并初始化了一些数据。首先调用 printArray 函数打印原始数组，然后调用 mergeSort 函数对数组进行排序，最后再次调用 printArray 函数打印排序后的数组。

归并排序的性能分析

时间复杂度

1. 平均情况：归并排序的平均时间复杂度为 $O(n \log n)$。在分解阶段，每次将序列大致分成两半，共需要 $\log n$ 层递归。在每一层递归中，合并操作需要线性时间 $O(n)$，因为要遍历所有元素。所以总的时间复杂度是 $O(n \log n)$。
2. 最坏情况：最坏情况发生在序列完全逆序时，归并排序的时间复杂度依然是 $O(n \log n)$。因为归并排序的性能不受序列初始顺序的影响，始终按照固定的分治策略进行排序。

空间复杂度

1. 辅助空间：归并排序的空间复杂度主要来自于合并过程中使用的临时数组。在合并两个子序列时，需要额外的空间来存储临时数据。因此，归并排序的空间复杂度为 $O(n)$，其中 n 是序列的长度。这是因为在最底层的合并操作中，需要同时存储两个长度之和为 n 的子序列。
2. 递归栈空间：由于归并排序是递归实现的，递归调用会占用栈空间。递归深度为 $\log n$，每层递归需要的额外空间为常数级，所以递归栈空间复杂度为 $O(\log n)$。综合辅助空间和递归栈空间，归并排序总的空间复杂度在最坏情况下为 $O(n + \log n)$，通常简化为 $O(n)$。

归并排序的稳定性

稳定性的概念

排序算法的稳定性是指在排序过程中，相等元素的相对顺序是否保持不变。如果相等元素在排序前后的相对顺序不变，则称该排序算法是稳定的；否则就是不稳定的。

归并排序的稳定性分析

归并排序是一种稳定的排序算法。在合并步骤中，当比较两个子序列中相等的元素时，总是先将左边子序列中的元素放入结果数组。例如，在 merge 函数中，当 L[i] 和 R[j] 相等时，会先将 L[i] 放入 arr[k]，这就保证了相等元素的相对顺序不变。这种稳定性使得归并排序在一些对元素相对顺序有要求的场景中具有优势，比如对结构体数组按照多个字段排序时，如果先按某个字段排序后，再按另一个字段排序，稳定的排序算法可以保证第一个字段相同的元素在第二个字段排序后相对顺序不变。

归并排序在实际应用中的场景

外部排序

1. 问题背景：在处理大规模数据时，由于内存容量有限，无法将所有数据一次性读入内存进行排序。此时就需要外部排序算法，而归并排序是一种常用的外部排序方法。
2. 实现方式：将大规模数据分成多个较小的块，每个块可以读入内存进行排序（例如使用内存中的归并排序）。然后将这些已排序的块逐步合并，最终得到整个有序的数据集合。在合并过程中，每次从各个块中读取一部分数据到内存进行合并，再将合并结果写回外存，直到所有块都合并完成。

链表排序

1. 链表特点：链表与数组不同，链表的元素在内存中不是连续存储的，随机访问的时间复杂度为 $O(n)$。这使得一些基于数组的排序算法（如快速排序在平均情况下利用随机访问的优势）在链表上性能不佳。
2. 归并排序优势：归并排序在链表上的实现具有较好的性能。它不需要随机访问元素，只需要通过指针顺序遍历链表。分解链表时，可以通过快慢指针找到链表的中间位置，然后递归地对两个子链表进行排序，最后合并两个已排序的子链表。这种方式避免了链表随机访问的劣势，使得归并排序成为链表排序的常用算法之一。

与其他排序算法的比较

与冒泡排序比较

1. 时间复杂度：冒泡排序的平均和最坏时间复杂度为 $O(n^2)$，而归并排序的平均和最坏时间复杂度为 $O(n \log n)$。在数据规模较大时，归并排序的性能远远优于冒泡排序。例如，对于一个长度为 10000 的数组，冒泡排序的执行时间会随着数据规模的增加而急剧增长，而归并排序的增长速度相对较慢。
2. 稳定性：冒泡排序和归并排序都是稳定的排序算法。这意味着在处理包含相等元素的序列时，它们都能保证相等元素的相对顺序不变。

与快速排序比较

1. 时间复杂度：快速排序的平均时间复杂度为 $O(n \log n)$，与归并排序相同。但在最坏情况下，快速排序的时间复杂度会退化到 $O(n^2)$，例如当每次选择的枢轴都是序列中的最大或最小元素时。而归并排序的时间复杂度始终稳定在 $O(n \log n)$。
2. 空间复杂度：快速排序的空间复杂度在平均情况下为 $O(\log n)$，主要来自递归栈空间。但在最坏情况下，空间复杂度可能达到 $O(n)$。而归并排序的空间复杂度为 $O(n)$，主要是合并过程中使用的临时数组。
3. 稳定性：快速排序是不稳定的排序算法，而归并排序是稳定的。这使得在对稳定性有要求的场景下，归并排序更适用。

与堆排序比较

1. 时间复杂度：堆排序的平均和最坏时间复杂度也为 $O(n \log n)$，与归并排序在时间复杂度上相当。
2. 空间复杂度：堆排序的空间复杂度为 $O(1)$，因为它是原地排序算法，不需要额外的辅助数组。而归并排序的空间复杂度为 $O(n)$。这使得在空间有限的情况下，堆排序更具优势。
3. 稳定性：堆排序是不稳定的排序算法，而归并排序是稳定的。所以在需要保持元素相对顺序的场景中，归并排序更合适。

通过对以上几种常见排序算法的比较，可以看出归并排序在时间复杂度稳定性和稳定性方面具有独特的优势，在不同的应用场景中，我们可以根据具体需求选择合适的排序算法。

优化归并排序的一些方法

减少临时数组的分配和释放

1. 方法原理：在标准的归并排序实现中，每次合并都需要分配和释放临时数组，这会带来额外的时间开销。一种优化方法是预先分配一个足够大的全局临时数组，在所有的合并操作中都复用这个数组，避免频繁的内存分配和释放。
2. 代码实现示例：

int *tempArray;

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

    // 使用全局临时数组
    int *L = tempArray + left;
    int *R = tempArray + mid + 1;

    // 复制数据到临时数组 L[] 和 R[]
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;

    // 合并临时数组回到原数组
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 复制 L[] 中剩余的元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 复制 R[] 中剩余的元素
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

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);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arrSize = sizeof(arr) / sizeof(arr[0]);

    // 预先分配全局临时数组
    tempArray = new int[arrSize];

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

    mergeSort(arr, 0, arrSize - 1);

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

    // 释放全局临时数组
    delete[] tempArray;

    return 0;
}

在这个实现中，我们预先分配了一个全局的 tempArray，在 merge 函数中通过指针运算复用这个数组，避免了每次合并都进行内存分配和释放。

优化小数组的排序方式

1. 方法原理：当子数组的规模较小时，递归调用归并排序的开销可能会大于直接使用简单排序算法（如插入排序）的开销。因此，可以在子数组规模小于某个阈值时，切换到插入排序。
2. 代码实现示例：

void insertionSort(int arr[], int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

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

    int L[n1], R[n2];

    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

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

void mergeSort(int arr[], int left, int right) {
    const int threshold = 16;
    if (left < right) {
        if (right - left + 1 <= threshold) {
            insertionSort(arr, left, right);
        } else {
            int mid = left + (right - left) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);
        }
    }
}

在这个实现中，我们定义了一个 insertionSort 函数用于对小数组进行插入排序。在 mergeSort 函数中，当子数组的长度小于 threshold（这里设为 16，可以根据实际情况调整）时，调用 insertionSort 进行排序，否则继续使用归并排序。这种优化方式可以在一定程度上提高归并排序的性能，特别是对于包含大量小数组的情况。

总结归并排序的优缺点

优点

1. 高效性：归并排序的平均和最坏时间复杂度均为 $O(n \log n)$，在处理大规模数据时表现出色，相比一些时间复杂度为 $O(n^2)$ 的排序算法（如冒泡排序、选择排序）具有明显的性能优势。
2. 稳定性：归并排序是稳定的排序算法，这使得它在对稳定性有要求的场景中非常适用，例如对具有相同关键字的记录进行排序时，能保持其原来的相对顺序。
3. 适应性：适用于各种数据类型，无论是基本数据类型还是复杂的结构体类型，只要定义了合适的比较函数，都可以使用归并排序进行排序。

缺点

1. 空间复杂度较高：归并排序的空间复杂度为 $O(n)$，主要是因为在合并过程中需要额外的临时数组来存储数据。这在内存资源有限的情况下可能会成为一个问题，相比一些原地排序算法（如堆排序，空间复杂度为 $O(1)$），归并排序在空间使用上不够高效。
2. 递归实现的开销：归并排序通常采用递归实现，递归调用会带来额外的栈空间开销和函数调用开销。虽然可以通过一些优化方法（如使用迭代代替递归）来减少这种开销，但在某些情况下，递归实现仍然可能导致性能问题，特别是在处理非常深的递归层次时。

综上所述，归并排序在很多场景下是一种非常优秀的排序算法，但在实际应用中，需要根据具体的需求和数据特点来权衡其优缺点，选择最合适的排序算法。在对稳定性有要求、数据规模较大且内存空间充足的情况下，归并排序是一个很好的选择；而在内存空间紧张或对空间复杂度有严格要求的场景中，则需要考虑其他空间复杂度较低的排序算法。