胡佳

（南昌師范學(xué)院數(shù)學(xué)與計算機科學(xué)系，南昌 330000）

排序的常用方法及其改進

胡佳

（南昌師范學(xué)院數(shù)學(xué)與計算機科學(xué)系，南昌 330000）

介紹幾種常用的排序方法及其改進，有簡單的直接插入排序和改進的希爾排序；有簡單的交換氣泡排序以及改進的快速排序；還有單向掃描的改進的氣泡排序。每種排序都給出它的主要思想，排序的主要過程和代碼，改進的算法給出時效的分析。

排序；改進；時效分析

0 引言

在日常生活中我們有很多需要排序的工作，假如是少量的數(shù)據(jù)進行排序，那我們在可以通過肉眼來判斷和安放數(shù)據(jù)，但是如果數(shù)據(jù)量很大的時候，用日常的方法就難以排放數(shù)據(jù)，這時候我們可以給計算機一個算法，讓計算機來給大批量的數(shù)據(jù)進行排序。

C語言程序設(shè)計課程教學(xué)中，我們就學(xué)習(xí)過排序算法中的一種冒泡排序，實際上還有很多種排序的方法，它們的穩(wěn)定性和效率都不一樣。這部分內(nèi)容我們是方在數(shù)據(jù)結(jié)構(gòu)課程中介紹。這里我們首先給排序下一個定義，對于n個結(jié)點組成的線性表（a0，a1，…，an-1），按照結(jié)點中某個字段的值的遞增或遞減的次序，對列表中的各個結(jié)點進行重新排列的過程，我們可以稱為排序。排序的方法分為內(nèi)部排序和外部排序兩大類。內(nèi)部排序指得是排序的整個時間段所有的結(jié)點都存放在內(nèi)存，調(diào)整待排序的結(jié)點的位置也是在內(nèi)存；外部排序指的是排序期間，有大部分的結(jié)點存放在外存，排序的過程需要借助內(nèi)存來調(diào)整存放在外存正在等待排序的結(jié)點。

假設(shè)數(shù)據(jù)結(jié)點A0，A1，…，An-1的關(guān)鍵字的值依次是key0，key1，…，keyn-1。這里數(shù)據(jù)結(jié)點都是線性結(jié)構(gòu)，在實際應(yīng)用中可以用數(shù)組來實現(xiàn)。因此數(shù)據(jù)結(jié)點的排序的過程就是為了確定關(guān)鍵字下標(biāo)排列的過程，即tag[0]，tag[1]，…tag[n-1]（0<=tag[i]<=n-1，0<=i<=n-1），0<=i<= n-1，當(dāng)i≠j時，tag[i]≠tag[j]），所以當(dāng)關(guān)鍵字相等時，數(shù)據(jù)結(jié)點通過某種排序方法排序后，數(shù)據(jù)結(jié)點的先后次序依然不變。即keytag[i]=keytag[j]（tag[i] tag[j]），在排序后，對應(yīng)的keytag[i]在keytag[j]的前面或者keytag[j]在keytag[i]，這種情況為穩(wěn)定的排序，否則為不穩(wěn)定的排序。我們在選擇和分析排序算法時，除了主要考慮時間復(fù)雜度外，還要考慮算法的穩(wěn)定性。常見的簡單的插入排序、選擇排序和氣泡排序都是穩(wěn)定的排序。下面我們介紹在此基礎(chǔ)上看這些排序的改進方法和具體的代碼實現(xiàn)，并把它們做一個比對。這里指定排序的次序為從小到大。

1 排序問題的簡單算法和改進算法

首先看簡單的插入排序，它是穩(wěn)定的，不僅適用于線性表的順序存儲，而且適用于線性表的鏈?zhǔn)酱鎯?。這里我們用順序存儲的數(shù)組來實現(xiàn)直接插入，它的算法思想很簡單，就是先將原始數(shù)據(jù)結(jié)點的第一個結(jié)點元素看成一個有序的序列，然后依次取原始數(shù)據(jù)結(jié)點序列的第二個、第三個依次插入，直到插入最后一個數(shù)據(jù)結(jié)點為止。

以下是實現(xiàn)功能模塊的源代碼：

該算法的基本操作是兩個數(shù)據(jù)結(jié)點之間的比較，排序經(jīng)過了n-1次的插入，在每輪的插入過程中要進行n-x次的比較，x表示的是第幾輪的插入。整個排序的過程需要最多需要經(jīng)過∑_1^（n-1）x次的比較，即n（n-1）/2，比較次數(shù)最少的為n-1，這種排序適用于數(shù)據(jù)結(jié)點個數(shù)比較少的情況。

簡單直接的插入排序只是比較相鄰的兩個數(shù)據(jù)結(jié)點，一次比較僅僅把數(shù)據(jù)結(jié)點移動一個位置而已。如果要對位置相隔較遠(yuǎn)的數(shù)據(jù)結(jié)點進行比較，并且使得結(jié)點在比較以后能夠一次跨越較大的距離，這就需要把數(shù)據(jù)結(jié)點中值較小的結(jié)點盡快的往前移動，值較大的盡量快地往后進行移動，以此來提高排序的速度。這就需要對簡單的插入排序進行改進。改進的思想如下：首先以dis1為步長，并且dis1>0&&dis1

接著在每組中進行簡單的插入排序。然后以dis2為步長，并且dis2>0&&dis2

由于步長的不斷減少，數(shù)據(jù)結(jié)點越來越有序，因而數(shù)據(jù)結(jié)點的比較次數(shù)和移動次數(shù)也越來越少。這里步長序列的選取并無定論，但是我們可以知道這種排序的總比較次數(shù)和總移動次數(shù)要比簡單選擇排序少很多，且它是一種不穩(wěn)定的排序。以下是實現(xiàn)功能模塊的源代碼：

改進的排序時效分析很難，關(guān)鍵碼的比較次數(shù)與記錄移動次數(shù)依賴于步長因子序列的選取，當(dāng)分組較多時，組內(nèi)元素較少；一趟中直接插入排序元素少，循環(huán)次數(shù)就少；當(dāng)分組較少時，組內(nèi)元素增多，但已接近有序，循環(huán)次數(shù)并不增加。因此，希爾排序的時間復(fù)雜性在O（nlog2n）和O（n2）之間。

現(xiàn)在我們將隨機生成50個整數(shù)，然后對上面的算法進行檢驗，檢驗代碼如下：

驗證的結(jié)果如圖1所示。

圖1

我們將看一種冒泡排序的改進，這種冒泡排序只允許從前向后掃描，它的改進算法思想為，在從前往后一輪比較以后，記錄下最后往下調(diào)的數(shù)據(jù)結(jié)點的位置，若這個數(shù)據(jù)結(jié)點的位置是tag，那么下一遍的范圍在0-tag，假如某輪沒有交換的數(shù)據(jù)結(jié)點，那么整個排序就結(jié)束。所以整個排序有可能少于n-1輪，這就大大的提高的排序的效率，以下是實現(xiàn)功能代碼。

現(xiàn)在我們將隨機生成50個整數(shù)，然后對上面的算法進行檢驗，檢驗代碼如下：

驗證的結(jié)果如圖2所示。

圖2

我們首先選中一個數(shù)據(jù)結(jié)點X，把它作為標(biāo)桿，然后從區(qū)間兩端向中間進行比較和交換，使得X前面的數(shù)據(jù)結(jié)點都比X小，而X后面的數(shù)據(jù)結(jié)點都不比X小，然后我們把X放在前后兩部分的分界處，這樣就可以將整個區(qū)間分成兩個子區(qū)間。按照這樣方法一直做下去，直到區(qū)間為空位置，這時的序列就變成了有序的序列集合。它實際上是一種改進了的交換排序。以下是實現(xiàn)功能模塊的源代碼：

從空間復(fù)雜性看，改進的排序是遞歸的，每層遞歸調(diào)用時的指針和參數(shù)均要用棧來存放，，存儲開銷在理想情況下為O（log2n），在最壞情況下為O（n）。

從時間復(fù)雜性看，在n個記錄的排序表中，一次劃分平均有小于或等于n次關(guān)鍵碼比較，時間復(fù)雜性為O（n）。理想情況下，每次劃分，正好將分成兩個等長的子序列，則需要的排序趟數(shù)為小于或等于log2n，故時間性能為O（nlog2n）。

最壞情況下，每次劃分，只得到一個子序列，時間復(fù)雜性為O（n2）。

通常情況上，快速排序被認(rèn)為在同數(shù)量級（O（nlog2n））的內(nèi)排序方法中平均性能最好的。

這種改進的排序是一個不穩(wěn)定的排序方法。

2 結(jié)語

以上介紹了主要介紹了幾種常用的排序方法及其改進，有簡單的直接插入排序和改進的希爾排序；有單向掃描的改進的冒泡排序；有雙向掃描的改進的交換排序。每種排序都給出它的主要思想，排序的主要過程和代碼，以及時效的分析，希望對大家日常生活中的排序應(yīng)用有所幫助。

[1]胡佳.高職高專《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)改革探析[J].江西教育學(xué)院學(xué)報，2012（6）.

[2]胡佳.幾種典型關(guān)聯(lián)規(guī)則算法的分析與比較[J].現(xiàn)代計算機（專業(yè)版），2011.

Common Methods of Sorting and Its Improvement

HU Jia

（Department of Math and Computer Science，Nanchang Normal University,Nanchang 330000）

Introduces several commonly used methods and their improvements,there are simple direct insertion sort and improved shell sort;there are a simple exchange bubble sort and improved quick sort;there is the improved bubble sort which scans for one way.Gives the main idea of each sort,main process and code,and the time analysis of improved algorithm.

Sort;Improvement;Time Analysis

1007-1423（2016）08-0061-05

10.3969/j.issn.1007-1423.2016.08.013

2015-12-24

2016-02-28

2013年江西省高等學(xué)校教學(xué)改革研究課題、2014年江西省社會科學(xué)規(guī)劃項目

胡佳（1982-），南昌新建人，碩士講師研究方向為計算機教育和數(shù)據(jù)挖掘