线性时间排序(计数排序、基数排序、桶排序)
转载:http://blog.****.net/luoshixian099/article/details/45043337
线性时间排序
前面介绍的几种排序，都是能够在复杂度nlog(n)时间内排序n个数的算法，这些算法都是通过比较来决定它们的顺序，这类算法叫做比较排序 。下面介绍的几种算法用运算去排序，且它们的复杂度是线性时间[线性时间指的就是O(n)]。
——————————————————————————————————————
1.计数排序
计数排序采用的方法是：对每个元素x，去确定小于x的元素的个数，从而就可以知道元素x在输出数组中的哪个位置了。
计数排序的一个重要性质是它是稳定的，即对于相同的两个数，排序后，还会保持它们在输入数组中的前后顺序，这也是下面基数排序的基础。
虽然复杂度比之间的算法减小了，但在算法实现过程中，它要求输入数组数据位于一个区间[0,k]内，因为要遍历数组，计算[0,k]间的每个数在输入数组中的个数，这也算是计数排序的缺点吧！
下面是调试的程序，可直接运行，详细过程看下《算法导论》
- #include<STDIO.H>
- #define K 10 //数据在[0,K]之间
- int A[]={2,7,3,5,3,2,9};
- int B[20]={0}; //输出数组
- int C[20]={0}; //计数数组
- int Length=sizeof(A)/sizeof(A[0])-1;
- void Count_Sort(int *A,int *B,int k)
- {
- int j;
- for (j=0;j<=Length;j++) //为每个数计个数
- {
- C[A[j]]=C[A[j]]+1;
- }
- for (j=1;j<=K;j++) //计算有多少元素小于等于j
- {
- C[j]=C[j]+C[j-1];
- }
- for (j=Length;j>=0;j--) //倒叙输出数组，保证了数据是稳定的
- {
- B[C[A[j]]]=A[j];
- C[A[j]]=C[A[j]]-1; //A[j]输出，对应计数数组元素减1。
- }
- }
- int main()
- {
- int i;
- Count_Sort(A,B,K);
- for (i=1;i<=Length+1;i++)
- {
- printf("%3d",B[i]);
- }
- printf("\n");
- return 0;
- }
———————————————————————————————————
2.基数排序
基本思想：对N个d位的数据排序，与传统的想法不同，它是先从最低有效位开始排。
这里必须保证每次排序是稳定的，即对相同的数据，输出的顺序必须与输入的顺序相同。
基数排序介绍
基数排序能达到线性的时间复杂度。基数排序的主要思路是,将所有待比较数值(注意,必须是正整数)
统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序
所以这里的排序可以使用计数排序。
这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.
为什么要从低位开始向高位排序?
如果要从高位排序, 那么次高位的排序会影响高位已经排好的大小关系. 在数学中, 数位越高,数位值对数的大小的影响就越大
为什么同一数位的排序子程序要使用稳定排序?
稳定排序能保证,上一次的排序成果被保留,十位数的排序过程能保留个位数的排序成果,百位数的排序过程能保留十位数的排序成果.
实现例程：
- #include <STDIO.H>
- #include <string.h>
- int A[]={329,457,657,839,436,720,355}; //要排序的数组
- int Length=sizeof(A)/sizeof(A[0])-1;
- void Count_Sort(int *A2,int *B) //计数排序
- {
- int j;
- int C[10]={0}; //计数数组,数字在[0,9]之间
- for (j=0;j<=Length;j++) //为每个数计个数
- {
- C[A2[j]]=C[A2[j]]+1;
- }
- for (j=1;j<=10;j++) //计算有多少元素小于等于j
- {
- C[j]=C[j]+C[j-1];
- }
- for (j=Length;j>=0;j--) //倒叙输出数组，保证了数据是稳定的
- {
- B[C[A2[j]]]=A[j]; //参照C[A2[j]]的大小，对数组A[j]输出
- C[A2[j]]=C[A2[j]]-1;
- }
- }
- void Radix_Sort(int *A,int d)
- {
- int i,j,k,temp;
- int A2[10]={0}; //存放各个位
- int B[20]={0}; //输出数组
- for(i=1;i<=d;i++)
- {
- for (j=0;j<=Length;j++)
- {
- temp=A[j];
- k=i;
- while(k>1)
- {
- temp=temp/10;
- k--;
- }
- A2[j]=temp%10; //取指定的位存到A2[j]，等待排序
- }
- Count_Sort(A2,B);
- memcpy(A,&B[1],(Length+1)*4);
- }
- }
- int main()
- {
- int j;
- Radix_Sort(A,3);
- for (j=0;j<=Length;j++)
- {
- printf("%5d\n",A[j]);
- }
- }
———————————————————————————————————————————————————————————————————————————
3.桶排序
桶排序是假设输入数据服从均匀分布，平均情况下也是线性时间。假设输入数据是由一个随机过程产生，该过程将元素均匀，独立地分布在[0,1）区间上。
它将[0,1)区间划分为n个相同大小的子区间，称为“桶”，然后遍历输入的数据，分别放入到指定的桶中（放入桶中的同时，有个链表插入排序的过程）。最后依次把各个桶中数据输出即可。
例程：
- #include <STDIO.H>
- #include <STDLIB.H>
- int A[]={78,17,39,26,72,94,21,12,23,68};//假如输入数据平均分布在[0,99]区间内
- int Length = sizeof(A)/sizeof(A[0])-1;
- typedef struct Node //链表单元结构
- {
- int num;
- struct Node *next;
- }Node;
- Node *Bucket[10]={0}; //分成10个桶，即10个小区间
- void Bucket_Sort(int *A)
- {
- int i;
- int a;
- Node * temp=NULL,*Pre_temp=NULL;
- for (i=0;i<=Length;i++) //遍历输入数组，放入到指定的桶中
- {
- a = (int)(A[i]/10);
- if(Bucket[a] == 0)
- {
- Bucket[a]=(Node *)malloc(sizeof(Node));
- Bucket[a]->num=A[i];
- Bucket[a]->next=NULL;
- }
- else //对非空链表插入排序
- {
- temp=Pre_temp=Bucket[a];
- while(A[i] > temp->num)
- {
- Pre_temp=temp;
- temp=temp->next;
- if (temp==NULL)
- break;
- }
- if (temp == NULL) // 插入到最后一个位置
- {
- temp=(Node *)malloc(sizeof(Node));
- temp->num=A[i];
- temp->next=NULL;
- Pre_temp->next=temp;
- }
- else if (temp == Bucket[a]) //插入到第一个位置
- {
- temp=(Node *)malloc(sizeof(Node));
- temp->num=A[i];
- temp->next=Bucket[a];
- Bucket[a]=temp;
- }
- else //插入到中间位置
- {
- temp=(Node *)malloc(sizeof(Node));
- temp->num=A[i];
- temp->next=Pre_temp->next;
- Pre_temp->next=temp;
- }
- }
- }
- }
- void Free_List(Node * head) //释放链表结构内存
- {
- Node *N=head;
- while (head!=NULL)
- {
- N=head->next;
- free(head);
- head=N;
- }
- }
- int main()
- {
- Node * temp=NULL;
- int i=1;
- Bucket_Sort(A);
- for(i=0;i<=9;i++) //依次输出各个桶中的数据
- {
- temp=Bucket[i];
- while(temp!=NULL)
- {
- printf("%3d\n",temp->num);
- temp=temp->next;
- }
- Free_List(Bucket[i]); //释放第i个桶的内存
- }
- return 0;
- }