基数排序

来自计算思维百科
跳转至: 导航搜索

如果我们希望对很多数据按照从小到大或是从大到小的顺序重新放置,这就是排序。基数排序是一种简单的排序方法,它的基本思想是将待排序的数的个位、十位、百位分别进行排序,使其成为一个新的有序序列。

基本概念

基数排序是将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

应用范围

仅能对整数型数据进行排序。

使用方法及步骤

  1. 将所有待排序的数据统一为同样的数位长度;
  2. 对个位进行排序;
  3. 在个位排序好的基础上,再对十位进行排序;
  4. 在十位排序好的基础上,再对百位进行排序;
  5. 重复上面的步骤;直至所有位数都排序好。

应用案例

应用1- 三位数字排序

案例:一组元素序列的关键字为(334,285,21,467,821,562,342,45),如何用基数排序算法进行排序呢?

解决方法:

这组关键字的位数最多的是3位,在排序之前,首先将所有的关键字都看作一个三位数字组成的数,即(334,285,021,467,821,562,342,045)。

对这组关键字进行基数排序需要进行3趟分配和收集,首先需要对该关键字序列的最低位进行分配和收集,然后实现对十位数字进行分配和收集,最后是对最高位的数字进行分配和收集。

一般情况下,采用链表实现基数排序。对最低位进行分配和收集的过程如图:

(红色标记为当前比较的位数)

 初始状态: 334,  285,  21 ,  467,  821,  562,  342,  45

 

 第一趟: 021, 821, 562, 342, 334, 285, 045, 467

 

 第二趟: 021, 821, 334, 342, 045, 562, 467, 285

 

 第三趟: 021, 045, 285, 334, 342, 467, 562, 821

 

最终排序结果:021,  045, 285,  334, 342, 467,  562,  821

应用2-扑克牌排序

案例:在日常生活中,扑克牌是一种多关键字的排序问题。扑克牌有4种花色,即红桃,方块,梅花,和黑桃,每种花色从A到K共13帐牌,这四种花色就想当于4个关键字,而每种花色的A到K张牌就相当与对不同关键字进行排序。 解决步骤:先从52张牌中按花色分成四份,在每一份中分别按字母A到K进行排序。这就体现了基数排序的思想。

可以体现的计算思维

基数排序主要是利用不同的数位进行排序,每个数位的排序方法都是相同的,体现了计算思维的递归思想。