排序算法性能分析及基数排序算法的应用

张震

（大连海洋大学，辽宁 大连 116300）

排序算法性能分析及基数排序算法的应用

张震

（大连海洋大学，辽宁 大连 116300）

在信息化高度发达的今天，工作中资料整理仍然涉及到手工排序。文章对各种排序算法的性能进行了比较。通过实例演示，阐述了基数排序在资料整理中的应用，以提高手工排序的效率。

排序算法；基数排序；性能分析

近年来，教师岗位考核中经常涉及到收取业绩材料，这些材料必须按照统一的编号管理，形成一致性档案，便于在审核过程中对资料进行查找。面对来自于不同部门、不同级别教师的大量资料，如何快速、有效地整理显然非常必要了。在实际工作中主要是通过查找、编号、排序对资料进行整理的。选择一种快速高效的排序方法能提高资料整理的效率。基数排序是众多排序算法中非常适合手工操作的高效算法。

1 排序算法分析

通常采用的排序方法有：直接插入排序、简单选择排序、快速排序、基数排序等。

（1）直接插入排序的基本思想是：每一趟将一个待排序的记录，按其关键字值的大小插入到已经排序的部分文件中适当位置上，直到全部插入完成。算法的时间复杂度是O（n2）。

（2）简单选择排序的基本思想是：每步从待排序的记录中选出关键字最小的记录（档案），按顺序放在已排序的记录（档案）序列的最后，直到全部排完为止。算法的时间复杂度是O（n2）。

（3）快速排序的基本思想是：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分，并把该记录排在这两部分的中间（称为该记录归位），这个过程称作一趟快速排序。之后分别对分割所得两个子序列“递归”进行快速排序。快速排序的时间复杂度为O（nlog2n）。

（4）基数排序的基本思想是：一般地，记录R[i]的关键字R[i].key是由d位数字组成，即kd-1kd-2…k0，每一个数字表示关键字的一位，其中kd-1为最高位，k0是最低位，每一位的值都在0≤ki＜r范围内，其中r称为基数。排序时先按最高位的值对记录进行排序，在此基础上，再按次高位进行排序，依此类推。由高位向低位，每趟都是根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最低位，则完成了基数排序的整个过程。基数排序的时间复杂度为O（d（n+r））。

用三组无序数据分别应用四种排序方法进行手工排序，则数据移动的次数反映排序的快慢。实验数据如表1所示：

表1 移动次数比较

由表1中数据可以看出，基数排序移动数据的次数最少，所用的时间最短，说明在手工操作中是可行的。而且在所有排序方法中只有基数排序是不需要进行关键字比较的，整个排序过程中只是通过数据的“分配”和“收集”就可实现数据的排序。

2 基数排序算法在档案整理过程中的实现

在实际工作中，首先对档案资料编号，编号规则是部门号+级别号+工号（例如：050812），编号位数依照实际情况确定，这里分别用两位数来代表部门号、级别号，用三位数代表工号，组成七位数字的档案编号。排序中不是严格按照编号的每一位来操作，而是按照档案编号的组成部分为关键字来进行排序。

（1）根据部门编号的两位数字对档案进行分组，分组后再顺序收集。此操作完成后档案材料就按部门不同有序排列，并且同一部门的材料连续排列在了一起。

（2）根据级别号的两位数字对档案进行分组，分组结束后在顺序收集。此操作完成后不仅实现了档案材料按级别有序排列，而且同一级别的档案材料按部门不同有序排列。表2以一组数据为例，显示两次排序结果。

表2 排序过程

3 基数排序实现过程中注意的问题

基数排序过程类似人们生活中扑克牌整理过程。其实现过程分为高位优先和地位优先两种。表2演示的是高位优先过程。地位优先过程是排序时先按最低位的值对记录进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最高位，则完成了基数排序的整个过程。选择低位优先过程还是高位优先过程取决于自己期望的排序结果。实际操作过程中不必严格按照从高位到低位或从低位到高位的顺序推进。可以根据期望的结果顺序灵活选择每一趟分组的依据。例如，期望资料宏观上按部份好排列，部门号相同的资料再按级别排列，则可以第一趟按级别分组后收集，第二趟按部门号分组后收集，就可以得到期望的结果。若期望宏观上按级别排序，级别相同时按部门排序，则可以第一趟按部门号分组后收集，第二趟按级别分组后收集，表2描述的就是这个过程。

4 结语

在信息技术高度发展的今天，资料的手动整理仍然是人们工作中的一部分，要快速、高效地对众多资料进行一致性整理，没有好的方法是不行的。基数排序方法不仅效率高，而且较其它方法，不需要进行关键字的比较，非常适合手工操作，是资料整理中切实有效地方法。

［1］伍一，孔凡辉，孙柏祥.数据结构应用教程，第二版［M］.北京：清华大学出版社，2015.

［2］项丽萍.数据结构中各种排序算法的比较与分析［J］.太原城市职业技术学院学报，2008，（12）：112.

［3］何宇晨，严晶涛，柏云，等.排序算法的性能比较及基数排序在数据分类中的应用［J］.福建电脑，2011，（11）：90.

Performance Analysis of Sequencing Algorithm and App lication of Cardinal Number Sorting Algorithm

ZHANG Zhen
（Dalian Ocean University，Dalian，Liaoning 116300，China）

In the highly developed information era，the work of data processing is still related to manual sorting.This paper compares the performance of various sorting algorithms.Through the example demonstration，the application of cardinality sorting in data collation is described to improve the efficiency of manual sorting.

sorting algorithm；cardinality ranking；performance analysis

TP301.6

A

2095-980X（2017）06-0036-01

2017-05-08

张震（1972-），女，讲师，主要从事计算机科学与计算专业教学工作。