基于數據結構的選擇排序算法剖析與改進

摘 要:排序在數據處理中起著非常重要的作用。選擇排序算法是數據結構中的一種基本的排序算法，運用極其廣泛。這里對基本選擇排序的算法進行剖析，繼而提出一種改進的思路，形成改進型的選擇排序。其特點是在比較的過程中將被交換數據的下標進行保存，在選擇下一個目標時只需在最后一次交換的位置與待排紀錄之間進行，從而大大地減少了比較的次數。從時間復雜度、空間復雜度與穩定性進行比較，體現出其優越性能。

關鍵詞:選擇排序;算法;時間復雜度;空間復雜度

中圖分類號:TP311文獻標識碼:A

文章編號:1004-373X(2010)06-084-03

Research on Sorting Selective Algorithm Based on Data Structure

LI Chong

(Chongqing Vocational Institute of Engineering，Chongqing，400037，China)

Abstract:Sorting plays an important role in data processing.The widely used selective algorithm is a basic sorting way in the data structure.This research analyses the basic selective sorting algorithm，promotes improving ways，determines an improved selective sorting way.In this way the number of comparison is greatly reduced because only the subscript of the transferred data is stored in the process of comparison，and the next object is chosen between the last transferred and the to-be-sorted data.This research also compares them in time complexity，space complexity and stability，and presents excellent performance of the improved way.

Keywords:selective sorting;algorithm;time complexity;space complexity

0 引 言

一個好的排序算法主要體現在排序時間的快慢和查找效率上。如何設計一個好的排序算法在數據處理中是非常重要的。目前，常見的一些排序算法有插入排序、選擇排序、冒泡排序、快速排序、希爾排序等。這些排序算法在數據處理的應用中各有優缺點。這里著重以選擇排序為例，通過對其算法設計思路和排序的時間復雜度、空間復雜度及排序的穩定性進行分析，從而提出一些改進的排序思路，以提高其排序的效率。

1 基本選擇排序算法思路

選擇排序算法思想是:對于待排序的n個對象，對它們進行逐趟掃描。對于第i趟(i=0，1，2，…，n-3，n-2)掃描，在后面的n-i個待排序對象中選出關鍵碼最小或最大(從小到大的排序選最小，從大到小的排序選最大)的對象，作為有序對象序列的第i個對象。當到第n-2趟時完成。因為最后待排序對象還剩一個數據，就不用再選了。

目前基本的選擇排序算法有以下幾種:

(1)直接選擇排序。

直接選擇排序算法的設計思路如同前面所述，對于待排序的n個對象V～V。首先在V～V中選出關鍵字最小的對象，如果它不是對象V，則將它與V交換。然后再從V[1] ～V中找出關鍵字最小的對象，如果它不是對象V[1]，則將它與V[1]交換。以此類推，直到排至V時結束。

直接選擇排序的關鍵字比較次數與對象的初始值無關。第i趟選擇所需的比較次數為n-i-1(i=0，1，2，…，n-3，n-2)次。因此，對于n個對象的排序序列，總的關鍵碼比較次數為:

KCN=∑n-2i=0(n-i-1)=n(n-1)/2

另外，通過上述算法能清楚地分析得出:當找到第一個關鍵碼最小的記錄時需要比較n-1次，找到關鍵碼次小的記錄需要比較n-2次。以此類推，找到第i(i=0，1，2，…，n-3，n-2)個關鍵碼時需要比較n-i次。因此，對于待排序的n個對象進行一次直接選擇排序所需要的總的比較次數為:

(n-1)+(n-2)+ …+2+1=n(n-1)/2n2/2

故直接選擇排序的時間復雜度為O(n2)。

(2)錦標賽排序。

錦標排序算法的思路與體育比賽時的淘汰賽類似。首先取得待排序的n個對象的關鍵碼，進行兩兩比較，得到個比較的優勝者(關鍵碼小者)，作為第一步比較的結果保留下來。然后再對這個關鍵碼進行兩兩比較，…，如此重復，直到選出第一個關鍵碼最小的對象為止，并將關鍵碼最小的對象的參選標志進行修改。如果n不是2的k次冪，則將剩余的單個葉結點直接補足到滿足2k-1

例如關鍵碼為(5，3，2，9，1，8，7，4)的一組對象，其所構成的勝者樹如圖1所示，樹根即為最小的關鍵碼，然后把根結點的參選標志進行修改。在進行第二趟比較時，只需對修改了參選標志的子樹進行重新比較，如圖2所示(▲表示已經修改了參選標志的對象)，這樣以后每次的比較次數為O(log2 n)。

圖1 勝利樹

圖2 修改后的勝利樹

(3)堆排序。

堆排序是在直接選擇排序的基礎上，利用完全二叉樹的特點形成的一種排序算法。它主要是利用完全二叉樹的順序結構。其具體的思路是:將待排序的n個對象放在一個數組V中。將V看作一棵完全二叉樹，每個結點表示一個記錄，V[1]表示完全二叉樹的根結點，剩余的V依次逐層從左到右進行排列，構成一棵完全二叉樹。任意結點V的左子結點為V，右子結點為V，雙親結點為V。

然后，對這棵完全二叉樹進行調整，使得各結點之間的關鍵字滿足下列條件:V≤V，并且V ≤V。即每個結點的值均小于他的兩個子結點的值，這里稱這種完全二叉樹為堆樹。顯然這種“堆樹”的根結點的值為最小，這種堆也稱為“小根堆”。反過來當“堆樹”中條件滿足:V≥ V，并且V ≥V。這種“堆樹”稱為“大根堆”。在第一次構建這種堆的過程稱為“創建初始堆”。

在“初始堆”創建之后，將根結點和結點V進行交換，然后，在V之間重新調整二叉樹的結點，使其成為堆，再將根結點與V交換。依次類推，直到V[1]與V[2]交換為止。這時，整個V數組中的元素，就是有一個序序列。其變化過程如圖3~圖6所示。

圖3 V數組

圖4 V數組對應的完全二叉樹

圖5 V數組所對應的初始堆(大根堆)

圖6 初始堆所對應的數組初始堆

各結點在數組中的存儲情況

在堆排序中，除創建初始堆時需要比較n-1次，在重構過程中，每次只需要-1次比較。因此，整個排序過程的總比較次數為:

(n-1)+(n-1)(-1)n=

O(log2 n)

這種排序算法在存儲空間上除了在交換過程中要使用一個臨時的變量以外，是不需要任何額外的存儲空間來供排序使用，因此，它的空間復雜度為O(1)。堆排序是一種不穩定的排序算法。

2 改進的選擇排序算法

通過對前面幾種選擇排序算法的分析得出，雖然錦標排序算法在完成具體排序時時間上快一點，但它需要很多的額外存儲空間來供排序使用，而堆排序對附加空間的需要很低，但它又是一種不穩定的排序算法。因此，將這兩種算法進行綜合，設計出一種完成具體排序時既在時間上較快，又在空間需求上要求不高的新方法，即這里提出改進型的選擇排序。

這種排序方法的思路是:對待排序的n個記錄V，將V與V[J](j=n-1，n-2，…，2，1)進行比較。在比較過程中，如果存在V≥V，則將其交換，交換后新的V>V(j10)，則交換V與V，交換后的V>V(j1j2>…>jk>0)。選擇第二大元素時，只需要考慮V[1]~V之間的元素。若jk=1，則可確定V[1]即為第二大元素，依此類推，直到選擇了n-1個元素排序完成。其排序過程如圖7所示。

圖7 排序過程

對于以上數組中的數據將V和V[9]，V[8]，…，V[1]進行比較，如果哪個元素比V大，就及時交換這兩個元素，并將交換位置的下標進行保存。因此，以上數組比較第一趟時進行了如下幾次交換。第一次交換是V[7]>V(24>22)，交換后，V變成了24并記住交換位置下標7;第二次交換是V[3]>V(25>24)，交換后，V變成了25并記住交換位置下標3;第三次交換是V[2]>V[3](27>25)，交換后，V變成27并記住交換位置下標2。所以第一趟比較了j1=7，j2=3，j3=2，并且第一趟比較、交換之后的數據如圖8所示。

圖8 交換后的數據

接下來在V[1]~V之間找第二大元素時，此時，不需要將V[1]與V~V[2]之間的數據進行比較，而只需要將V[1]與V~V[2]之間的數據進行比較。在找第三大元素時，只需要將V[2]與V到V[3]之間的元素進行比較。依次類推，當所保存的交換位置用完以后，又可以從V開始。通過上述方法進行選擇排序時，可以大大縮小比較的范圍，縮短排序的時間。同時，在附加存儲空間方面，也只需要提供一個數組來保存比較過程中需要交換位置的下標。因此，在空間上也沒有多大的冗余，從而，降低了對空間的需求。

3 結 語

以上改進的排序算法易于理解，算法程序實現簡單，是對眾多選擇排序算法的歸納，有助于拓寬解決實際問題的思路，從而設計出更好的排序算法。

參考文獻

[1]張福炎.程序員級、高級程序員級程序設計[M].北京:清華大學出版社，1996.

[2]陳明.數據結構(C++版)[M].北京:清華大學出版社，2005.

[3]吳海兵.單循環排序算法及其改進.http://www.xueshuwang.com/html/2/2784.html.

[4]黃福員.冒泡排序算法的改進[J].微機發展，2003，13(11):65-66.

[5] Mark Allen Weiss.數據結構與算法分析C++描述[M].張懷勇，譯.北京:人民郵電出版社，2007.

[6]Thomas H Cormen.算法導論[M].2版.北京:機械工業出版社，2006.

[7]Sartaj Sahni.計算機算法[M].北京:機械工業出版社，2006.

[8]徐士良.實用數據結構[M].北京:清華大學出版社，2006.

[9]徐士良.常用算法程序集[M].北京:清華大學出版社，2001.

[10][美]克萊因伯格.算法設計[M].北京:清華大學出版社，2006.