排序的常用方法及其改進(jìn)

胡佳

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

排序的常用方法及其改進(jìn)

胡佳

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

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

排序；改進(jìn)；時(shí)效分析

0 引言

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

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

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

1 排序問題的簡單算法和改進(jìn)算法

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

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

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

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

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

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

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

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

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

圖1

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

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

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

圖2

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

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

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

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

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

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

2 結(jié)語

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

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

[2]胡佳.幾種典型關(guān)聯(lián)規(guī)則算法的分析與比較[J].現(xiàn)代計(jì)算機(jī)（專業(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年江西省社會(huì)科學(xué)規(guī)劃項(xiàng)目

胡佳（1982-），南昌新建人，碩士講師研究方向?yàn)橛?jì)算機(jī)教育和數(shù)據(jù)挖掘