稳定排序nlogn之归并排序

稳定排序nlogn之归并排序_一维,二维

稳定排序：排序时间稳定的排序

稳定排序包括：归并排序(nlogn)，基数排序【设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix)) 】，冒泡排序(n^2)，插入排序(n^2)，交换排序(n^2)，计数排序【n为数字个数，k为数字范围，O(n+k)】等。

Problem：对n个数进行排序，n<=100000，1s以内

快速排序平均时间复杂度为nlogn，最坏时间复杂度为n^2。c,c++中的快速排序qsort(c),sort(c++)有优化(如随机化等)，基本上达到O(nlogn)，但是不是特别稳定。

Solution：

用归并排序，时间复杂度稳定在O(nlogn)。

n=10000 nlogn=132877

n=100000 nlogn=1660964

n=1000000 nlogn=19931568

其中2^10=1024,2^20=1024*1024约为1000000

Code：

一维和二维的区别在于数据类型的不同和比较方式的不同

一维：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define maxn 100000
 4 
 5 long a[maxn+1],b[maxn+1];
 6 
 7 void mergesort(long l,long r)
 8 {
 9     long mid;
10     mid=(l+r) >> 1;
11     if (l!=mid) mergesort(l,mid);
12     if (mid+1!=r) mergesort(mid+1,r);
13     long i,j,k;
14     for (i=l;i<=r;i++)
15         b[i]=a[i];
16     i=l;
17     j=mid+1;
18     k=l;
19     while (i<=mid && j<=r)
20     {
21         if (b[i]<b[j])
22         {
23             a[k]=b[i];
24             i++;
25             k++;
26         }
27         else
28         {
29             a[k]=b[j];
30             j++;
31             k++;
32         }
33     }
34     if (i<=mid)
35     {
36         while (i<=mid)
37         {
38             a[k]=b[i];
39             i++;
40             k++;
41         }
42     }
43     else
44     {
45         while (j<=r)
46         {
47             a[k]=b[j];
48             j++;
49             k++;
50         }
51     }
52 }
53 
54 int main()
55 {
56     long n,i;
57     scanf("%ld",&n);
58     for (i=1;i<=n;i++)
59         scanf("%ld",&a[i]);
60     mergesort(1,n);
61     printf("
");
62     for (i=1;i<=n;i++)
63         printf("%ld ",a[i]);
64     printf("
");
65     return 0;
66 }
67 /*
68 5
69 4 2 3 5 1
70 */

二维：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define maxn 100000
 4 
 5 struct node
 6 {
 7     long x,y;
 8 };
 9 
10 struct node a[maxn+1],b[maxn+1];
11 
12 void mergesort(long l,long r)
13 {
14     long mid;
15     mid=(l+r) >> 1;
16     if (l!=mid) mergesort(l,mid);
17     if (mid+1!=r) mergesort(mid+1,r);
18     long i,j,k;
19     for (i=l;i<=r;i++)
20         b[i]=a[i];
21     i=l;
22     j=mid+1;
23     k=l;
24     while (i<=mid && j<=r)
25     {
26         if (b[i].x<b[j].x || (b[i].x==b[j].x && b[i].y<b[j].y))
27         {
28             a[k]=b[i];
29             i++;
30             k++;
31         }
32         else
33         {
34             a[k]=b[j];
35             j++;
36             k++;
37         }
38     }
39     if (i<=mid)
40     {
41         while (i<=mid)
42         {
43             a[k]=b[i];
44             i++;
45             k++;
46         }
47     }
48     else
49     {
50         while (j<=r)
51         {
52             a[k]=b[j];
53             j++;
54             k++;
55         }
56     }
57 }
58 
59 int main()
60 {
61     long n,i;
62     scanf("%ld",&n);
63     for (i=1;i<=n;i++)
64         scanf("%ld%ld",&a[i].x,&a[i].y);
65     mergesort(1,n);
66     printf("
");
67     for (i=1;i<=n;i++)
68         printf("%ld %ld
",a[i].x,a[i].y);
69     printf("
");
70     return 0;
71 }
72 /*
73 5
74 1 2
75 5 5
76 4 4
77 2 3
78 2 2
79 */