張震

（大連海洋大學，遼寧 大連 116300）

排序算法性能分析及基數(shù)排序算法的應用

張震

（大連海洋大學，遼寧 大連 116300）

在信息化高度發(fā)達的今天，工作中資料整理仍然涉及到手工排序。文章對各種排序算法的性能進行了比較。通過實例演示，闡述了基數(shù)排序在資料整理中的應用，以提高手工排序的效率。

排序算法；基數(shù)排序；性能分析

近年來，教師崗位考核中經(jīng)常涉及到收取業(yè)績材料，這些材料必須按照統(tǒng)一的編號管理，形成一致性檔案，便于在審核過程中對資料進行查找。面對來自于不同部門、不同級別教師的大量資料，如何快速、有效地整理顯然非常必要了。在實際工作中主要是通過查找、編號、排序對資料進行整理的。選擇一種快速高效的排序方法能提高資料整理的效率?；鶖?shù)排序是眾多排序算法中非常適合手工操作的高效算法。

1 排序算法分析

通常采用的排序方法有：直接插入排序、簡單選擇排序、快速排序、基數(shù)排序等。

（1）直接插入排序的基本思想是：每一趟將一個待排序的記錄，按其關鍵字值的大小插入到已經(jīng)排序的部分文件中適當位置上，直到全部插入完成。算法的時間復雜度是O（n2）。

（2）簡單選擇排序的基本思想是：每步從待排序的記錄中選出關鍵字最小的記錄（檔案），按順序放在已排序的記錄（檔案）序列的最后，直到全部排完為止。算法的時間復雜度是O（n2）。

（3）快速排序的基本思想是：在待排序的n個記錄中任取一個記錄（通常取第一個記錄），把該記錄放入適當位置后,數(shù)據(jù)序列被此記錄劃分成兩部分。所有關鍵字比該記錄關鍵字小的記錄放置在前一部分,所有比它大的記錄放置在后一部分，并把該記錄排在這兩部分的中間（稱為該記錄歸位），這個過程稱作一趟快速排序。之后分別對分割所得兩個子序列“遞歸”進行快速排序?？焖倥判虻臅r間復雜度為O（nlog2n）。

（4）基數(shù)排序的基本思想是：一般地，記錄R[i]的關鍵字R[i].key是由d位數(shù)字組成，即kd-1kd-2…k0，每一個數(shù)字表示關鍵字的一位，其中kd-1為最高位，k0是最低位，每一位的值都在0≤ki＜r范圍內，其中r稱為基數(shù)。排序時先按最高位的值對記錄進行排序，在此基礎上，再按次高位進行排序，依此類推。由高位向低位，每趟都是根據(jù)關鍵字的一位并在前一趟的基礎上對所有記錄進行排序，直至最低位，則完成了基數(shù)排序的整個過程?；鶖?shù)排序的時間復雜度為O（d（n+r））。

用三組無序數(shù)據(jù)分別應用四種排序方法進行手工排序，則數(shù)據(jù)移動的次數(shù)反映排序的快慢。實驗數(shù)據(jù)如表1所示：

表1 移動次數(shù)比較

由表1中數(shù)據(jù)可以看出，基數(shù)排序移動數(shù)據(jù)的次數(shù)最少，所用的時間最短，說明在手工操作中是可行的。而且在所有排序方法中只有基數(shù)排序是不需要進行關鍵字比較的，整個排序過程中只是通過數(shù)據(jù)的“分配”和“收集”就可實現(xiàn)數(shù)據(jù)的排序。

2 基數(shù)排序算法在檔案整理過程中的實現(xiàn)

在實際工作中，首先對檔案資料編號，編號規(guī)則是部門號+級別號+工號（例如：050812），編號位數(shù)依照實際情況確定，這里分別用兩位數(shù)來代表部門號、級別號，用三位數(shù)代表工號，組成七位數(shù)字的檔案編號。排序中不是嚴格按照編號的每一位來操作，而是按照檔案編號的組成部分為關鍵字來進行排序。

（1）根據(jù)部門編號的兩位數(shù)字對檔案進行分組，分組后再順序收集。此操作完成后檔案材料就按部門不同有序排列，并且同一部門的材料連續(xù)排列在了一起。

（2）根據(jù)級別號的兩位數(shù)字對檔案進行分組，分組結束后在順序收集。此操作完成后不僅實現(xiàn)了檔案材料按級別有序排列，而且同一級別的檔案材料按部門不同有序排列。表2以一組數(shù)據(jù)為例，顯示兩次排序結果。

表2 排序過程

3 基數(shù)排序實現(xiàn)過程中注意的問題

基數(shù)排序過程類似人們生活中撲克牌整理過程。其實現(xiàn)過程分為高位優(yōu)先和地位優(yōu)先兩種。表2演示的是高位優(yōu)先過程。地位優(yōu)先過程是排序時先按最低位的值對記錄進行排序，在此基礎上，再按次低位進行排序，依此類推。由低位向高位，每趟都是根據(jù)關鍵字的一位并在前一趟的基礎上對所有記錄進行排序，直至最高位，則完成了基數(shù)排序的整個過程。選擇低位優(yōu)先過程還是高位優(yōu)先過程取決于自己期望的排序結果。實際操作過程中不必嚴格按照從高位到低位或從低位到高位的順序推進?？梢愿鶕?jù)期望的結果順序靈活選擇每一趟分組的依據(jù)。例如，期望資料宏觀上按部份好排列，部門號相同的資料再按級別排列，則可以第一趟按級別分組后收集，第二趟按部門號分組后收集，就可以得到期望的結果。若期望宏觀上按級別排序，級別相同時按部門排序，則可以第一趟按部門號分組后收集，第二趟按級別分組后收集，表2描述的就是這個過程。

4 結語

在信息技術高度發(fā)展的今天，資料的手動整理仍然是人們工作中的一部分，要快速、高效地對眾多資料進行一致性整理，沒有好的方法是不行的?；鶖?shù)排序方法不僅效率高，而且較其它方法，不需要進行關鍵字的比較，非常適合手工操作，是資料整理中切實有效地方法。

［1］伍一，孔凡輝，孫柏祥.數(shù)據(jù)結構應用教程，第二版［M］.北京：清華大學出版社，2015.

［2］項麗萍.數(shù)據(jù)結構中各種排序算法的比較與分析［J］.太原城市職業(yè)技術學院學報，2008，（12）：112.

［3］何宇晨，嚴晶濤，柏云，等.排序算法的性能比較及基數(shù)排序在數(shù)據(jù)分類中的應用［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-），女，講師，主要從事計算機科學與計算專業(yè)教學工作。