稳定排序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：

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

一维：

 #include <stdio.h>

 #include <stdlib.h>

 #define maxn 100000

 long a[maxn+],b[maxn+];

 void mergesort(long l,long r)

 {

     long mid;

     mid=(l+r) >> ;

     if (l!=mid) mergesort(l,mid);

     if (mid+!=r) mergesort(mid+,r);

     long i,j,k;

     for (i=l;i<=r;i++)

         b[i]=a[i];

     i=l;

     j=mid+;

     k=l;

     while (i<=mid && j<=r)

     {

         if (b[i]<b[j])

         {

             a[k]=b[i];

             i++;

             k++;

         }

         else

         {

             a[k]=b[j];

             j++;

             k++;

         }

     }

     if (i<=mid)

     {

         while (i<=mid)

         {

             a[k]=b[i];

             i++;

             k++;

         }

     }

     else

     {

         while (j<=r)

         {

             a[k]=b[j];

             j++;

             k++;

         }

     }

 }

 int main()

 {

     long n,i;

     scanf("%ld",&n);

     for (i=;i<=n;i++)

         scanf("%ld",&a[i]);

     mergesort(,n);

     printf("\n");

     for (i=;i<=n;i++)

         printf("%ld ",a[i]);

     printf("\n");

     return ;

 }

 /*

 5

 4 2 3 5 1

 */

二维：

 #include <stdio.h>

 #include <stdlib.h>

 #define maxn 100000

 struct node

 {

     long x,y;

 };

 struct node a[maxn+],b[maxn+];

 void mergesort(long l,long r)

 {

     long mid;

     mid=(l+r) >> ;

     if (l!=mid) mergesort(l,mid);

     if (mid+!=r) mergesort(mid+,r);

     long i,j,k;

     for (i=l;i<=r;i++)

         b[i]=a[i];

     i=l;

     j=mid+;

     k=l;

     while (i<=mid && j<=r)

     {

         if (b[i].x<b[j].x || (b[i].x==b[j].x && b[i].y<b[j].y))

         {

             a[k]=b[i];

             i++;

             k++;

         }

         else

         {

             a[k]=b[j];

             j++;

             k++;

         }

     }

     if (i<=mid)

     {

         while (i<=mid)

         {

             a[k]=b[i];

             i++;

             k++;

         }

     }

     else

     {

         while (j<=r)

         {

             a[k]=b[j];

             j++;

             k++;

         }

     }

 }

 int main()

 {

     long n,i;

     scanf("%ld",&n);

     for (i=;i<=n;i++)

         scanf("%ld%ld",&a[i].x,&a[i].y);

     mergesort(,n);

     printf("\n");

     for (i=;i<=n;i++)

         printf("%ld %ld\n",a[i].x,a[i].y);

     printf("\n");

     return ;

 }

 /*

 5

 1 2

 5 5

 4 4

 2 3

 2 2

 */

稳定排序nlogn之归并排序_一维,二维的相关教程结束。