归并排序

Posted on Edited on In

题目描述
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

输入格式
输入共 2 行，第一行是一个整数 n，表示数组的长度。第二行包含 n 个整数，表示待排序的数组。

输出格式
输出共 1 行，包含 n 个整数，表示排序后的数组（升序排列）。

数据范围
1 ≤ n ≤ 10000
-10000 ≤ 数组元素 ≤ 10000

输入样例：

1
2
9
38 27 43 3 9 82 10 1 23

输出样例：

1
1 3 9 10 23 27 38 43 82

注意事项

  • 归并排序的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。
  • 归并排序是稳定的排序算法。
  • 归并排序特别适合于处理大规模数据，尤其是对于链表排序。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
using namespace std;

// 合并两个有序子数组
void merge(int a[], int temp[], int left, int mid, int right)
{
    int i = left; // 左子数组的起始索引
    int j = mid + 1; // 右子数组的起始索引
    int k = left; // 临时数组的起始索引
    
    // 合并两个子数组到临时数组
    while (i <= mid && j <= right)
    {
        if (a[i] <= a[j])
        {
            temp[k++] = a[i++];
        }
        else
        {
            temp[k++] = a[j++];
        }
    }
    
    // 处理左子数组中剩余的元素
    while (i <= mid)
    {
        temp[k++] = a[i++];
    }
    
    // 处理右子数组中剩余的元素
    while (j <= right)
    {
        temp[k++] = a[j++];
    }
    
    // 将临时数组中的元素复制回原数组
    for (i = left; i <= right; i++)
    {
        a[i] = temp[i];
    }
}

// 归并排序函数
void mergeSort(int a[], int temp[], int left, int right)
{
    if (left < right)
    {
        int mid = left + (right - left) / 2; // 计算中间位置，避免整数溢出
        mergeSort(a, temp, left, mid); // 递归排序左子数组
        mergeSort(a, temp, mid + 1, right); // 递归排序右子数组
        merge(a, temp, left, mid, right); // 合并两个有序子数组
    }
}

int main()
{
    int n;
    cin >> n;
    int a[n];
    int temp[n]; // 临时数组，用于合并操作
    
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    
    mergeSort(a, temp, 0, n - 1); // 对整个数组进行归并排序
    
    // 输出排序后的数组
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
    
    return 0;
}

时间复杂度

  • 时间复杂度：O(nlogn)，其中 n 为数组的长度。
  • 空间复杂度：O(n)（需要额外的临时数组来辅助合并操作）。

代码解释

  • 归并排序的核心思想是将数组分成两半，分别对它们进行排序，然后将两个有序的子数组合并成一个有序的数组。
  • 合并操作是归并排序的关键，它需要一个临时数组来存储合并后的结果。
  • 在合并过程中，我们比较两个子数组的元素，将较小的元素放入临时数组中，直到一个子数组的所有元素都被处理完毕。
  • 然后，我们将另一个子数组中剩余的元素直接复制到临时数组的末尾。
  • 最后，我们将临时数组中的元素复制回原数组。
  • 递归的终止条件是子数组的长度小于或等于1（即left >= right）。