gpt4 book ai didi

深入解析Radix Sort基数排序算法思想及C语言实现示例

转载 作者:qq735679552 更新时间:2022-09-27 22:32:09 30 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章深入解析Radix Sort基数排序算法思想及C语言实现示例由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.

基本思想:

将待排数据中的每组关键字依次进行桶分配。 具体示例:

?
1
278、109、063、930、589、184、505、269、008、083

我们将每个数值的个位,十位,百位分成三个关键字: 278 -> k1(个位)=8,k2(十位)=7,k3=(百位)=2.

然后从最低位个位开始(从最次关键字开始),对所有数据的k1关键字进行桶分配(因为,每个数字都是 0-9的,因此桶大小为10),再依次输出桶中的数据得到下面的序列.

?
1
930、063、083、184、505、278、008、109、589、269

再对上面的序列接着进行针对k2的桶分配,输出序列为:

?
1
505、008、109、930、063、269、278、083、184、589

最后针对k3的桶分配,输出序列为:

?
1
008、063、083、109、184、269、278、505、589、930

效率分析:

基数排序的性能比桶排序要略差。每一次关键字的桶分配都需要O(N)的时间复杂度,而且分配之后得到新的关键字序列又需要O(N)的时间复杂度。假如待排数据可以分为d个关键字,则基数排序的时间复杂度将是O(d*2N) ,当然d要远远小于N,因此基本上还是线性级别的。基数排序的空间复杂度为O(N+M),其中M为桶的数量。一般来说N>>M,因此额外空间需要大概N个左右.

但是,对比桶排序,基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作,而桶排序在桶相对较少的情况下,桶内多个数据必须进行基于比较操作的排序。因此,在实际应用中,基数排序的应用范围更加广泛.

举例: 假设我们有一些二元组(a,b),要对它们进行以a为首要关键字,b的次要关键字的排序。我们可以先把它们先按照首要关键字排序,分成首要关键字相同的若干堆。然后,在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起,使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序.

第二种方式是从最低有效关键字开始排序,称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序,然后对所有的数据按照首要关键字排序。要注意的是,使用的排序算法必须是稳定的,否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序,LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的.

通常,基数排序要用到计数排序或者桶排序。使用计数排序时,需要的是Order数组。使用桶排序时,可以用链表的方法直接求出排序后的顺序。下面是一段用桶排序对二元组基数排序的程序:

  。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
struct data
{
   int key[2];
};
struct linklist
{
   linklist *next;
   data value;
   linklist(data v,linklist *n):value(v),next(n){}
   ~linklist() { if (next) delete next;}
};
void BucketSort(data *A, int N, int K, int y)
{
   linklist *Bucket[101],*p; //建立桶
   int i,j,k,M;
   M=K/100+1;
   memset (Bucket,0, sizeof (Bucket));
   for (i=1;i<=N;i++)
   {
     k=A[i].key[y]/M; //把A中的每个元素按照的范围值放入对应桶中
     Bucket[k]= new linklist(A[i],Bucket[k]);
   }
   for (k=j=0;k<=100;k++)
   {
     for (p=Bucket[k];p;p=p->next) j++;
     for (p=Bucket[k],i=1;p;p=p->next,i++)
       A[j-i+1]=p->value; //把桶中每个元素取出
     delete Bucket[k];
   }
}
void RadixSort(data *A, int N, int K)
{
   for ( int j=1;j>=0;j--) //从低优先到高优先 LSD
     BucketSort(A,N,K,j);
}
int main()
{
   int N=100,K=1000,i;
   data *A= new data[N+1];
   for (i=1;i<=N;i++)
   {
     A[i].key[0]= rand ()%K+1;
     A[i].key[1]= rand ()%K+1;
   }
   RadixSort(A,N,K);
   for (i=1;i<=N;i++)
     printf ( "(%d,%d) " ,A[i].key[0],A[i].key[1]);
   printf ( "\n" );
   return 0;
}

基数排序是一种用在老式穿卡机上的算法。一张卡片有80列,每列可在12个位置中的任一处穿孔。排序器可被机械地"程序化"以检查每一迭卡片中的某一列,再根据穿孔的位置将它们分放12个盒子里。这样,操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面,第二个位置穿孔的其次,等等.

对于一个位数有限的十进制数,我们可以把它看作一个多元组,从高位到低位关键字重要程度依次递减。可以使用基数排序对一些位数有限的十进制数排序.

最后此篇关于深入解析Radix Sort基数排序算法思想及C语言实现示例的文章就讲到这里了,如果你想了解更多关于深入解析Radix Sort基数排序算法思想及C语言实现示例的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com