词条 | 基数排序 |
释义 | (radix sort)则是属于“分配式排序”(distribution sort),基数排序法又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的比较性排序法。 解法基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。 以LSD为例,假设原来有一串数值如下所示: 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中: 0 1 81 2 22 3 73 93 43 4 14 5 55 65 6 7 8 28 9 39 接下来将这些桶子中的数值重新串接起来,成为以下的数列: 81, 22, 73, 93, 43, 14, 55, 65, 28, 39 接着再进行一次分配,这次是根据十位数来分配: 0 1 14 2 22 28 3 39 4 43 5 55 6 65 7 73 8 81 9 93 接下来将这些桶子中的数值重新串接起来,成为以下的数列: 14, 22, 28, 39, 43, 55, 65, 73, 81, 93 这时候整个数列已经排序完毕;如果排序的对象有三位数以上,则持续进行以上的动作直至最高位数为止。 LSD的基数排序适用于位数小的数列,如果位数多的话,使用MSD的效率会比较好。MSD的方式与LSD相反,是由高位数为基底开始进行分配,但在分配之后并不马上合并回一个数组中,而是在每个“桶子”中建立建立“子桶”,将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。 效率分析时间效率:设待排序列为n个记录,d个关键码,关键码的取值范围为radix,则进行链式基数排序的时间复杂度为O(d(n+radix)),其中,一趟分配时间复杂度为O(n),一趟收集时间复杂度为O(n),共进行d趟分配和收集。 空间效率:需要2*radix个指向队列的辅助空间,以及用于静态链表的n个指针。 实现的方法最高位优先(Most Significant Digit first)法,简称MSD法:先按k1排序分组,同一组中记录,关键码k1相等,再对各组按k2排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd对各子组排序后。再将各组连接起来,便得到一个有序序列。 最低位优先(Least Significant Digit first)法,简称LSD法:先从kd开始排序,再对kd-1进行排序,依次重复,直到对k1排序后便得到一个有序序列。 实现* C#include <stdio.h> #include <stdlib.h> int main(){ int data[10]={73,22,93,43,55,14,28,65,39,81}; int temp[10][10]={0};int order[10]={0}; int i,j,k,n,lsd; k=0;n=1; printf("\排序前: "); for (i=0;i<10;i++) printf("%d ",data[i]); putchar('\'); while (n<=10){ for (i=0;i<10;i++){ lsd=((data[i]/n)%10); temp[lsd][order[lsd]]=data[i]; order[lsd]++; } printf("\重新排列: "); for (i=0;i<10;i++){ if(order[i]!=0) for (j=0;j<order[i];j++){ data[k]=temp[i][j]; printf("%d ",data[k]); k++; } order[i]=0; } n*=10; k=0; } putchar('\'); printf("\排序后: "); for (i=0;i<10;i++) printf("%d ",data[i]); return 0; } * Javapublic class RadixSort { public static void sort(int[] number, int d) { int k=0; int n=1; int m=1;//控制键值排序依据在哪一位 int[][] temp = new int[number.length][number.length]; int[] order = new int[number.length]; while(m <= d) { for(int i = 0; i < number.length; i++) { int lsd = ((number[i] / n) % 10); temp[lsd][order[lsd]] = number[i]; order[lsd]++; } for(int i = 0; i < d; i++) { if(order[i] != 0) for(int j = 0; j < order[i]; j++) { number[k] = temp[i][j]; k++; } order[i] = 0; } n *= 10; k = 0; m++; } } public static void main(String[] args) { int[] data = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100}; RadixSort.sort(data, 2); //元素达到3位,参数为3,此处为2 for(int i = 0; i < data.length; i++) { System.out.print(data[i] + " "); } } * pascaltype link=^node; node=record data:integer; next:link; end; var i,j,l,m,k,n:integer; a:array[1..100] of integer; s:string; q,head:array[0..9] of link; p,p1:link; begin readln(n); writeln('Enter data:'); for i:=1 to n do read(a[i]); for i:=5 downto 1 do begin for j:=0 to 9 do begin new(head[j]); head[j]^.next:=nil; q[j]:=head[j] end; for j:=1 to n do begin str(a[j],s); for k:=1 to 5-length(s) do s:='0'+ s; m:=ord(s[i])-48; new(p); p^.data:=a[j]; p^.next:=nil; q[m]^.next:=p; q[m]:=p; end; l:=0; for j:=0 to 9 do begin p:=head[j]; while p^.next<>nil do begin l:=l+1;p1:=p;p:=p^.next;dispose(p1);a[l]:=p^.data; end; end; end; writeln('Sorted data:'); for i:= 1 to n do write(a[i]:6); end. c++实现基数排序int maxbit(int data[],int n) //辅助函数,求数据的最大位数 { int d = 1; //保存最大的位数 int p =10; for(int i = 0;i < n; ++i) { while(data[i] >= p) { p *= 10; ++d; } } return d; } void radixsort(int data[],int n) //基数排序 { int d = maxbit(data,n); int * tmp = new int[n]; int * count = new int[10]; //计数器 int i,j,k; int radix = 1; for(i = 1; i<= d;i++) //进行d次排序 { for(j = 0;j < 10;j++) count[j] = 0; //每次分配前清空计数器 for(j = 0;j < n; j++) { k = (data[j]/radix)%10; //统计每个桶中的记录数 count[k]++; } for(j = 1;j < 10;j++) count[j] = count[j-1] + count[j]; //将tmp中的位置依次分配给每个桶 for(j = n-1;j >= 0;j--) //将所有桶中记录依次收集到tmp中 { k = (data[j]/radix)%10; mp[count[k]] = data[j]; tcount[k]--; } for(j = 0;j < n;j++) //将临时数组的内容复制到data中 data[j] = tmp[j]; radix = radix*10; } delete [] tmp; delete [] count; } C# 实现基数排序 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace LearnSort { class Program { static void Main(string[] args) { int[] arr = CreateRandomArray(10);//产生随机数组 Print(arr);//输出数组 RadixSort(ref arr);//排序 Print(arr);//输出排序后的结果 Console.ReadKey(); } public static void RadixSort(ref int[] arr) { int iMaxLength = GetMaxLength(arr); RadixSort(ref arr, iMaxLength); } //排序 private static void RadixSort(ref int[] arr, int iMaxLength) { List<int> list = new List<int>();//存放每次排序后的元素 List<int>[] listArr = new List<int>[10];//十个桶 char currnetChar;//存放当前的字符 比如说 某个元素123 中的2 string currentItem;//存放当前的元素 比如说 某个元素123 for (int i = 0; i < listArr.Length; i++)//给十个桶分配内存初始化。 listArr[i] = new List<int>(); for (int i = 0; i < iMaxLength; i++)//一共执行iMaxLength次,iMaxLength是元素的最大位数。 { foreach (int number in arr)//分桶 { currentItem = number.ToString();//将当前元素转化成字符串 try { currnetChar = currentItem[currentItem.Length-i-1]; }//从个位向高位开始分桶 catch { listArr[0].Add(number); continue; }//如果发生异常,则将该数压入listArr[0]。比如说5 是没有十位数的,执行上面的操作肯定会发生越界异常的,这正是期望的行为,我们认为5的十位数是0,所以将它压入listArr[0]的桶里。 switch (currnetChar)//通过currnetChar的值,确定它压人哪个桶中。 { case '0': listArr[0].Add(number); break; case '1': listArr[1].Add(number); break; case '2': listArr[2].Add(number); break; case '3': listArr[3].Add(number); break; case '4': listArr[4].Add(number); break; case '5': listArr[5].Add(number); break; case '6': listArr[6].Add(number); break; case '7': listArr[7].Add(number); break; case '8': listArr[8].Add(number); break; case '9': listArr[9].Add(number); break; default: throw new Exception("unknow error"); } } for (int j = 0; j < listArr.Length; j++)//将十个桶里的数据重新排列,压入list foreach (int number in listArr[j].ToArray<int>()) { list.Add(number); listArr[j].Clear();//清空每个桶 } arr = list.ToArray<int>();//arr指向重新排列的元素 //Console.Write("{0} times:",i); Print(arr);//输出一次排列的结果 list.Clear();//清空list } } //得到最大元素的位数 private static int GetMaxLength(int[] arr) { int iMaxNumber = Int32.MinValue; foreach (int i in arr)//遍历得到最大值 { if (i > iMaxNumber) iMaxNumber = i; } return iMaxNumber.ToString().Length;//这样获得最大元素的位数是不是有点投机取巧了... } //输出数组元素 public static void Print(int[] arr) { foreach (int i in arr) System.Console.Write(i.ToString()+'\\t'); System.Console.WriteLine(); } //产生随机数组。随机数的范围是0到1000。 参数iLength指产生多少个随机数 public static int[] CreateRandomArray(int iLength) { int[] arr = new int[iLength]; Random random = new Random(); for (int i = 0; i < iLength; i++) arr[i] = random.Next(0,1001); return arr; } } } AAuto语言实现基数排序io.open();//打开控制台 /* *------------------------------------------------------- * 基数排序 **------------------------------------------------------ */ /* 基数排序从低位到高位进行,使得最后一次计数排序完成后,数组有序。 其原理在于对于待排序的数据,整体权重未知的情况下, 先按权重小的因子排序,然后按权重大的因子排序。 例如比较时间,先按日排序,再按月排序,最后按年排序,仅需排序三次。 但是如果先排序高位就没这么简单了。 基数排序源于老式穿孔机,排序器每次只能看到一个列, 很多教科书上的基数排序都是对数值排序,数值的大小是已知的,与老式穿孔机不同。 将数值按位拆分再排序,是无聊并自找麻烦的事。 算法的目的是找到最佳解决问题的方案,而不是把简单的事搞的更复杂。 基数排序更适合用于对时间、字符串等这些整体权值未知的数据进行排序。 这时候基数排序的思想才能体现出来,例如字符串,如果从高位(第一位)往后排就很麻烦。 而反过来,先对影响力较小,排序排重因子较小的低位(最后一位)进行排序就非常简单了。 这时候基数排序的思想就能体现出来。 又或者所有的数值都是以字符串形式存储,就象穿孔机一样,每次只能对一列进行排序。 这时候基数排序也适用,例如:对{"193";"229";"233";"215"}进行排序 下面我们使用基数排序对字符串进行排序。 对每个位循环调用计数排序。 */ //计数排序算法 radix_sort = function( array ,maxlen){ //AAuto在字符串索引越界时,会返回0,这使基数排序的实现更加简单。 //我们首先找出最大的排序长度,然后对于不足此长度的字符串,尾部都假定以0补齐。 //对于超出此长度的位在比较时忽略 if(!maxlen){ maxlen =0; for(i=1;#array;1){ maxlen = math.max(maxlen,#array[i] ) } } //else{ //最大排序长度也可以从参数中传过来,这样就不用遍历所有字符串了 //} //从字符串的最后一位开始,到第一位 for(pos=maxlen;1;-1){ //按当前位的字节码计数排序 var array_sorted ={}; var count = {}; for(i=0;256 ){ count[i] = 0; } var bytecode; for(i=1;#array;1){ //如果pos大于字符串长度,AAuto会返回0,这使基数排序的实现更容易 bytecode = array[i][pos] ; count[ bytecode ] ++; //count[n] 包含等于n的个数 } //统计位置 for(i=1;256;1){ count[i] += count[i-1]; //count[i] 包含小于等于i的个数 } var n; for(i=#array;1;-1){ n = array[i][pos] array_sorted[ count[n] ] = array[i]; count[n]--;//防止相同的元素n再次出现,将计数减一 } array = array_sorted; } return array } io.print("----------------") io.print("基数排序( 线性时间排序 )") io.print("----------------") array ={"AAuto is quicker and better,just try it!";"AAuto Quicker";"193";"229";"233";"215";"Hello Word";"abc";"abcd";"xd";"adcd";"eddd";"ah";"ai";"aj";"ajkk"}; //排序 array = radix_sort(array ) //输出结果 for(i=1;#array;1){ io.print( array[i] ) } execute("pause") //按任意键继续 io.close();//关闭控制台 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。