当前位置： 代码迷 >> 综合 >> 线性时间排序(计数排序、基数排序、桶排序)
  详细解决方案

线性时间排序(计数排序、基数排序、桶排序)

热度：45   发布时间：2023-12-16 05:52:30.0

转载:http://blog.csdn.net/luoshixian099/article/details/45043337

线性时间排序

  前面介绍的几种排序，都是能够在复杂度nlog(n)时间内排序n个数的算法，这些算法都是通过比较来决定它们的顺序，这类算法叫做比较排序 。下面介绍的几种算法用运算去排序，且它们的复杂度是线性时间[线性时间指的就是O(n)]。

——————————————————————————————————————


1.计数排序

    计数排序采用的方法是：对每个元素x，去确定小于x的元素的个数，从而就可以知道元素x在输出数组中的哪个位置了。

  计数排序的一个重要性质是它是稳定的，即对于相同的两个数，排序后，还会保持它们在输入数组中的前后顺序，这也是下面基数排序的基础。

  虽然复杂度比之间的算法减小了，但在算法实现过程中，它要求输入数组数据位于一个区间[0,k]内，因为要遍历数组，计算[0,k]间的每个数在输入数组中的个数，这也算是计数排序的缺点吧！
  下面是调试的程序，可直接运行，详细过程看下《算法导论》

[cpp]  view plain copy
print ?
  1. #include<STDIO.H>  
  2. #define  K 10                   //数据在[0,K]之间    
  3. int A[]={2,7,3,5,3,2,9};  
  4. int B[20]={0};                  //输出数组  
  5. int C[20]={0};                  //计数数组  
  6. int Length=sizeof(A)/sizeof(A[0])-1;           
  7. void Count_Sort(int *A,int *B,int k)  
  8. {  
  9.    int j;  
  10.    for (j=0;j<=Length;j++)       //为每个数计个数  
  11.    {  
  12.        C[A[j]]=C[A[j]]+1;  
  13.    }  
  14.   
  15.    for (j=1;j<=K;j++)           //计算有多少元素小于等于j  
  16.    {  
  17.        C[j]=C[j]+C[j-1];  
  18.    }  
  19.   
  20.    for (j=Length;j>=0;j--)      //倒叙输出数组，保证了数据是稳定的    
  21.    {  
  22.        B[C[A[j]]]=A[j];  
  23.        C[A[j]]=C[A[j]]-1;     //A[j]输出，对应计数数组元素减1。  
  24.    }  
  25. }  
  26. int main()  
  27. {      
  28.     int i;  
  29.     Count_Sort(A,B,K);  
  30.     for (i=1;i<=Length+1;i++)  
  31.     {  
  32.         printf("%3d",B[i]);  
  33.     }  
  34.     printf("\n");  
  35.     return 0;  
  36. }  

———————————————————————————————————

2.基数排序

   基本思想：对N个d位的数据排序，与传统的想法不同，它是先从最低有效位开始排。
    

  这里必须保证每次排序是稳定的，即对相同的数据，输出的顺序必须与输入的顺序相同。

基数排序介绍

基数排序能达到线性的时间复杂度。
基数排序的主要思路是,将所有待比较数值( 注意,必须是正整数)

统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序
所以这里的排序可以使用计数排序。
这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.

为什么要从低位开始向高位排序?

如果要从高位排序, 那么次高位的排序会影响高位已经排好的大小关系. 在数学中, 数位越高,数位值对数的大小的影响就越大

为什么同一数位的排序子程序要使用稳定排序?

稳定排序能保证,上一次的排序成果被保留,十位数的排序过程能保留个位数的排序成果,百位数的排序过程能保留十位数的排序成果.


实现例程：
[cpp]  view plain copy
print ?
  1. #include <STDIO.H>  
  2. #include <string.h>  
  3. int A[]={329,457,657,839,436,720,355};    //要排序的数组  
  4. int Length=sizeof(A)/sizeof(A[0])-1;  
  5. void Count_Sort(int *A2,int *B)    //计数排序  
  6. {  
  7.     int j;  
  8.     int C[10]={0};                 //计数数组,数字在[0,9]之间  
  9.     for (j=0;j<=Length;j++)       //为每个数计个数  
  10.     {  
  11.         C[A2[j]]=C[A2[j]]+1;  
  12.     }  
  13.       
  14.     for (j=1;j<=10;j++)           //计算有多少元素小于等于j  
  15.     {  
  16.         C[j]=C[j]+C[j-1];  
  17.     }  
  18.       
  19.     for (j=Length;j>=0;j--)      //倒叙输出数组，保证了数据是稳定的    
  20.     {  
  21.         B[C[A2[j]]]=A[j];       //参照C[A2[j]]的大小，对数组A[j]输出  
  22.         C[A2[j]]=C[A2[j]]-1;  
  23.     }  
  24. }  
  25.   
  26. void Radix_Sort(int *A,int d)  
  27. {   
  28.     int i,j,k,temp;  
  29.     int A2[10]={0};               //存放各个位  
  30.     int B[20]={0};                  //输出数组  
  31.    for(i=1;i<=d;i++)  
  32.    {  
  33.          
  34.        for (j=0;j<=Length;j++)  
  35.        {  
  36.            temp=A[j];  
  37.            k=i;  
  38.             while(k>1)  
  39.             {  
  40.                 temp=temp/10;  
  41.                 k--;  
  42.             }  
  43.             A2[j]=temp%10;      //取指定的位存到A2[j]，等待排序  
  44.        }  
  45.        Count_Sort(A2,B);  
  46.        memcpy(A,&B[1],(Length+1)*4);     
  47.    }        
  48. }  
  49. int main()  
  50. {  
  51.    int j;  
  52.    Radix_Sort(A,3);  
  53.    for (j=0;j<=Length;j++)  
  54.    {  
  55.        printf("%5d\n",A[j]);  
  56.    }  
  57.   
  58. }  

———————————————————————————————————————————————————————————————————————————

3.桶排序

  桶排序是假设输入数据服从均匀分布，平均情况下也是线性时间。假设输入数据是由一个随机过程产生，该过程将元素均匀，独立地分布在[0,1）区间上。
  它将[0,1)区间划分为n个相同大小的子区间，称为“桶”，然后遍历输入的数据，分别放入到指定的桶中（放入桶中的同时，有个链表插入排序的过程）。最后依次把各个桶中数据输出即可。


例程：
[cpp]  view plain copy
print ?
  1. #include <STDIO.H>  
  2. #include <STDLIB.H>  
  3. int A[]={78,17,39,26,72,94,21,12,23,68};//假如输入数据平均分布在[0,99]区间内  
  4. int Length = sizeof(A)/sizeof(A[0])-1;  
  5. typedef struct Node      //链表单元结构  
  6. {  
  7.    int num;  
  8.    struct Node *next;  
  9. }Node;   
  10. Node *Bucket[10]={0};       //分成10个桶，即10个小区间  
  11. void Bucket_Sort(int *A)  
  12. {  
  13.    int i;  
  14.    int a;  
  15.    Node * temp=NULL,*Pre_temp=NULL;  
  16.    for (i=0;i<=Length;i++)               //遍历输入数组，放入到指定的桶中  
  17.    {  
  18.        a = (int)(A[i]/10);  
  19.        if(Bucket[a] == 0)                 
  20.        {  
  21.           Bucket[a]=(Node *)malloc(sizeof(Node));  
  22.           Bucket[a]->num=A[i];  
  23.           Bucket[a]->next=NULL;  
  24.        }  
  25.        else                                 //对非空链表插入排序  
  26.        {     
  27.            temp=Pre_temp=Bucket[a];  
  28.            while(A[i] > temp->num)  
  29.            {    
  30.               Pre_temp=temp;  
  31.               temp=temp->next;  
  32.               if (temp==NULL)  
  33.                 break;  
  34.            }  
  35.   
  36.            if (temp == NULL)            // 插入到最后一个位置  
  37.            {  
  38.                temp=(Node *)malloc(sizeof(Node));  
  39.                temp->num=A[i];  
  40.                temp->next=NULL;  
  41.                Pre_temp->next=temp;  
  42.            }  
  43.            else if (temp == Bucket[a])  //插入到第一个位置  
  44.            {  
  45.                temp=(Node *)malloc(sizeof(Node));  
  46.                temp->num=A[i];  
  47.                temp->next=Bucket[a];  
  48.                Bucket[a]=temp;  
  49.            }  
  50.            else                         //插入到中间位置  
  51.            {  
  52.                temp=(Node *)malloc(sizeof(Node));  
  53.                temp->num=A[i];  
  54.                temp->next=Pre_temp->next;  
  55.                Pre_temp->next=temp;      
  56.            }  
  57.        }  
  58.          
  59.    }  
  60.      
  61.      
  62. }  
  63. void Free_List(Node * head)      //释放链表结构内存  
  64. {  
  65.     Node *N=head;  
  66.      while (head!=NULL)  
  67.      {  
  68.          N=head->next;  
  69.          free(head);  
  70.          head=N;  
  71.      }  
  72. }  
  73. int main()  
  74. {  
  75.     Node * temp=NULL;  
  76.     int i=1;  
  77.     Bucket_Sort(A);  
  78.     for(i=0;i<=9;i++)   //依次输出各个桶中的数据  
  79.     {   
  80.         temp=Bucket[i];  
  81.         while(temp!=NULL)  
  82.         {  
  83.             printf("%3d\n",temp->num);  
  84.             temp=temp->next;  
  85.         }  
  86.         Free_List(Bucket[i]);  //释放第i个桶的内存  
  87.     }  
  88.     return 0;  
  89. }  
  相关解决方案

代码迷 - 您身边的软件异常，代码异常，编程异常助手（发现，解决，分享）
Copyright © 2009-2013 DAIMAMI.COM. All rights reserved.