当前位置: 主页 > 论文下载 > 管理学论文 >

改进的基数排序算法在资料整理中的应用

作者：唐洪林日期：2013-12-17 10:55 来源：《电子制作》

万源市就业局四川达州 636350
【文章摘要】
在培训工作中，资料的收集和整理是一项复杂的工作，培训资料所需的身份证复印件，合格证，结业花名册，培训考试试卷。都要按统一的顺序来排列，才能做到资料的一致性。便于资料的查找和审核。因此，在实际工作中，结合了基数排序算法，提出了一种改进的基数排序算法，来提高资料整理的效率。
【关键词】
排序；资料整理；培训
近年来，在培训工作中，从身份证复印件这样的基础资料的收集，到培训结束时所产生的考试试卷，合格证书的打印，复印等。这些资料必须按照一个统一的编号进行管理，形成一致性的档案，以便于资料在审核过程中查找。因此，做好资料整理工作变显得非常必要了, 而面对大量的资料，我们该如何来快速、有效地进行资料整理？在实际工作中，主要是通过查找，编号，排序来实现资料整理的。选用一种快速高效的排序方法能提高资料整理的效率。在平时的工作中，发现基数排序算法是一种切实可行的方法。
1 基数排序算法
基数排序的思想类似于扑克牌排队的方法。一般地，记录r[i] 的关键字为r[i].key，r[i].key 是由d 位数字组成，即Ki1Ki2 ∧ Kid ，每一个数字表示关键字的一位，其中K1 为最高位，Kd 是最低位，每一位的值都在0 ≤ Ki ＜ rd 范围内，rd 称为基数。排序时，先按最低位的值对记录进行排序。在此基础上，再按次低位进行排序。依次类推，由低位向高位，每趟都是根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最高位，则完成了基数排序的整个过程。基数排序算法的时间复杂度O(d*(rd+n)) ；其中rd 是基数， d 是关键字的位数，n 是元素个数。它是一种稳定的排序方法。
在实际的工作中，如果先按最低位对整个记录进行排序，排序后再按次低位对整个记录进行排序，以此类推，直到最高位为止。但在用手工进行资料排序中，此方法操作不是很方便，因此，我们对算法加以改动。采用先对最高位进行排序，排序完成后；再对次高位对记录进行排序；以此类推，直到个位进行排序，这种方法具有可操作性，且方便快捷。根据此思想，我们提出了改进的基数排序算法。
2 改进的基数排序算法
一般地，记录r[i] 的关键字为r[i].key， r[i].key 是由d 位数字组成，即Ki1Ki2 ∧ Kid ，每一个数字表示关键字的一位，其中K1 为最高位，Kd 是最低位，每一位的值都在0 ≤ Ki ＜ rd 范围内，rd 称为基数。排序时，先按最高位的值对记录进行排序，排序完成后生成rd 个块，然后，分别对rd 个块按次高位的值对记录进行排序，排序后，再分别产生rd 个块，以此类推，直到最低位为止，进行排序后，则完成了整个记录的排序过程。
3 改进的基数排序算法在资料整理过程中的实现
在培训过程中，资料的收集整理一般要经过以下几个步骤：以下是资料整理流程。
①首先，在培训开始前收集身份证复印件。
②根据身份证复印件的次序进行编号，制作报名登记表电子文档。报名登记表包括编号，姓名，身份证号，培训专业，联系电话等关键字。
③培训结束前的准考证制作就根据报名登记表的编号来进行准考证编号，并确保其编号与身份证编号一致。
④考试结束后，经过试卷评阅后，试卷的顺序可能已打乱了。这时就需要手工排序了。
根据改进的基数排序算法来进行试卷排序。
⑤ 合格证的打印顺序则应与报名登记表的顺序一致，并进行编号。合格证复印之后，若合格证复印件顺序与编号不一致，则按改进的基数排序算法对合格证进行排序。所有经过排序的资料便可以归档了。以下是培训资料整理流程图。
4 排序效果分析
我们通常采用的排序方法有：直接插入排序；快速排序；基数排序等几钟，我们对直接插入排序，快速排序，基数排序和改进的基数排序进行分析和实验比较。
①直接插入排序的基本思想是：每一趟将一个待排序的记录，按其关键字值的大小插入到已经排序的部分文件中适当的位置上，直到全部插入完成。插入排序算法的时间复杂度是O(n2)。
②快速排序的基本思想是：在待排序的n 个记录中任取一个记录（通常取第一个记录），把该记录放入最终位置后，数据序列被此记录分割成两部分。所有关键字比该记录关键字小的位置在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一趟快速排序。之后对所有的两部分分别重复上述过程，直到每部分内只有一个记录为止。快速排序算法的时间复杂度为O(nlog2n)。
③基数排序的思想类似于扑克牌排队的方法。其算法在前面已论述了的，基数排序算法的时间复杂度O(d*(rd+n) 。
④改进的基数排序法。其算法的时间复杂度O(2n) 。
通过对n 个记录进行分析；算法的时间复杂度反映了算法执行的时间，从上面几种方法的时间复杂度可以看出，O(n2) ＞ O(nlog2n) ＞ O(d*(rd+n) ＞ O(2n)。则改进的基数排序算法所用时间最少，其次是基数排序算法，再次是快速排序算法，最慢的是直接插入排序算法。我们用三组无序的数据，分别采用以上四种排序算法对这三组数据进行手工排序，则数据移动的次数来反映排序所用时间的快慢。则实验数据如下表：
由上表实验数据可以看出，采用改进的基数排序对无序的数据进行排序，其移动数据的次数最少，所用时间最短，则说明该算法在实际的工作中是可行的，有效的。
5 结束语
在资料的整理过程中，要求对众多的资料做到一致性，并且要快速，高效地进行整理。没有好的排序方法就不能快速地整理资料。特别是资料超过100 份后，那操作方法对效果来说将是非常明显的。本文提到的改进的基数排序算法来进行数据排序，手工操作非常简单，且速度快，效果良好。是资料整理的一种切实有效的方法。
【参考文献】
李春葆. 数据结构习题与解析. 北京：清华大学出版社，1999.