3.归并排序
标签：归并排序 bit ons alt 排序 lse 时间 有一个 names
基本思想：分治。
归并排序是以数组的中间点来分。
时间复杂度确定是nlogn
1:确定分界点mid = (l + r) / 2，是下标的中间值。
2:递归排序左右两边。排完序后，左右两边都是有序的了。
3:归并。把两个有序的数组，归并成一个有序的数组。
1 #include 2 using namespace std;
3 const int N = 100010;
4 int a[N];
5 int tmp[N];
6 void merge_sort(int l, int r) {
7 if (l >= r) { //区间里没数或只有一个的话
8 return;
9 }
10 //int mid = (l + r) / 2;
11 int mid = (l + r) >> 1;
12 merge_sort(l, mid);
13 merge_sort(mid + 1, r);
14 int k = 0, i = l, j = mid + 1;
15 //k表示当前合并已经有了多少个数了
16 while (i r) {
17 if (a[i] a[j]) {
18 tmp[k++] = a[i++];
19 } else {
20 tmp[k++] = a[j++];
21 }
22 }
23 while (i mid) {
24 tmp[k++] = a[i++];
25 }
26 while (j r) {
27 tmp[k++] = a[j++];
28 }
29 for (int i = l, j = 0; i ) {
30 a[i] = tmp[j];
31 }
32 }
33 int main () {
34 int n;
35 cin >> n;
36 for (int i = 0; i ) {
37 cin >> a[i];
38 }
39 merge_sort(0, n - 1);
40 for (int i = 0; i ) {
41 cout " ";
42 }
43 return 0;
44 }
3.归并排序
标签：归并排序 bit ons alt 排序 lse 时间 有一个 names
原文地址：https://www.cnblogs.com/fx1998/p/12803906.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
3.归并排序
文章链接：http://soscw.com/essay/81809.html
评论