C++归并排序

归并排序:

目录

一、归并排序

二、基本算法

    1、分离

    2、合并
1
2
3

三、C++代码实现

    1、分离函数

    2、合并函数 

    3、C++完整代码 

    4、样例
1
2
3
4
5
6
7

四、总结

一 归并排序

归并排序(Merge Sort)是建立在归并操作上的一种既有效又稳定的排序算法，该算法是采用的一个非常典型的应用。

二 基本算法

1.分离：
这个排序会从中间先分离成两个小方阵(不是方阵)，然后一直分裂，一直分裂到每个方阵只剩下一个数。

2.合并：
每个方阵都有一个数，现在就要合并。先定义两个哨兵，看这两个数谁更小，谁就在方阵前面。最后会变成一个大数组。

三 C++代码实现

分离：

 //当[l...r]中只有一个数时或没有数时，递归结束
  if(l >= r) return;
  int mid = (l + r) / 2; //找到中间位置
  //分成两个部分，对这两个部分分别进行归并排序
  mergeSort(l, mid); mergeSort(mid + 1, r);
1
2
3
4
5

合并：

//i是第一部分左边的哨兵，j是第二部分左边的哨兵
  int i = l, j = mid + 1, k = l; //k表示合并后放入b数组的位置
  //哨兵没有走到头
  while(i <= mid && j <= r)
  {
    if(a[i] <= a[j]) b[k ++] = a[i ++]; //将较小的a[i]合并到b数组中
   	else b[k ++] = a[j ++];//将较小的a[j]合并到b数组中
  }
  while(i <= mid) b[k ++] = a[i ++]; //将左边剩余元素合并到b数组
  while(j <= r) b[k ++] = a[j ++]; //将右边剩余元素合并到b数组
  //将b数组拷贝回a数组
  for(int i = l; i <= r; i ++) 
    a[i] = b[i];  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

C++完整代码

#include <iostream>
using namespace std;
int a[100010], b[100010];
//将数组a[]从l到r的位置进行归并排序
void mergeSort(int l, int r)
{
  //当[l...r]中只有一个数时或没有数时，递归结束
  if(l >= r) return;
  int mid = (l + r) / 2; //找到中间位置
  //分成两个部分，对这两个部分分别进行归并排序
  mergeSort(l, mid); mergeSort(mid + 1, r);
  //i是第一部分左边的哨兵，j是第二部分左边的哨兵
  int i = l, j = mid + 1, k = l; //k表示合并后放入b数组的位置
  //哨兵没有走到头
  while(i <= mid && j <= r)
  {
    if(a[i] <= a[j]) b[k ++] = a[i ++]; //将较小的a[i]合并到b数组中
   	else b[k ++] = a[j ++];//将较小的a[j]合并到b数组中
  }
  while(i <= mid) b[k ++] = a[i ++]; //将左边剩余元素合并到b数组
  while(j <= r) b[k ++] = a[j ++]; //将右边剩余元素合并到b数组
  //将b数组拷贝回a数组
  for(int i = l; i <= r; i ++) 
    a[i] = b[i];  
}

int main()
{
  int n;
  cin >> n;
  for(int i = 1; i <= n; i ++)
    cin >> a[i];
  //将数组a[]从1到n的位置进行归并排序
  mergeSort(1, n);  
  for(int i = 1; i <= n; i ++)
    cout << a[i] << " ";
  return 0;
}
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

四 总结

今天我们学习了排序中又快又稳定的算法：归并排序，时间复杂度为 O(nlogn)。代码很简洁，很容易懂。