排序（sort）或分類

所謂排序，就是要整理文件中的記錄，使之按關(guān)鍵字遞增(或遞減)次序排列起來。其確切定義如下：

輸入：n 個記錄 R1，R2，…，Rn，其相應的關(guān)鍵字分別為 K1，K2，…，Kn。

輸出：Ril，Ri2，…，Rin，使得 Ki1≤Ki2≤…≤Kin。(或 Ki1≥Ki2≥…≥Kin)。

1．被排序?qū)ο?-文件

被排序的對象--文件由一組記錄組成。

記錄則由若干個數(shù)據(jù)項(或域)組成。其中有一項可用來標識一個記錄，稱為關(guān)鍵字項。該數(shù)據(jù)項的值稱為關(guān)鍵字(Key)。

注意： 在不易產(chǎn)生混淆時，將關(guān)鍵字項簡稱為關(guān)鍵字。

2．排序運算的依據(jù)--關(guān)鍵字

用來作排序運算依據(jù)的關(guān)鍵字，可以是數(shù)字類型，也可以是字符類型。

關(guān)鍵字的選取應根據(jù)問題的要求而定。

【例】在高考成績統(tǒng)計中將每個考生作為一個記錄。每條記錄包含準考證號、姓名、各科的分數(shù)和總分數(shù)等項內(nèi)容。若要惟一地標識一個考生的記錄，則必須用"準考證號"作為關(guān)鍵字。若要按照考生的總分數(shù)排名次，則需用"總分數(shù)"作為關(guān)鍵字。

排序的穩(wěn)定性

當待排序記錄的關(guān)鍵字均不相同時，排序結(jié)果是惟一的，否則排序結(jié)果不唯一。

在待排序的文件中，若存在多個關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的；若具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生變化，則稱這種排序方法是不穩(wěn)定的。

注意： 排序算法的穩(wěn)定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得算法不滿足穩(wěn)定性要求，則該排序算法就是不穩(wěn)定的。

排序方法的分類

1．按是否涉及數(shù)據(jù)的內(nèi)、外存交換分

在排序過程中，若整個文件都是放在內(nèi)存中處理，排序時不涉及數(shù)據(jù)的內(nèi)、外存交換，則稱之為內(nèi)部排序(簡稱內(nèi)排序)；反之，若排序過程中要進行數(shù)據(jù)的內(nèi)、外存交換，則稱之為外部排序。

注意：

• 內(nèi)排序適用于記錄個數(shù)不很多的小文件。
• 外排序則適用于記錄個數(shù)太多，不能一次將其全部記錄放人內(nèi)存的大文件。

2．按策略劃分內(nèi)部排序方法

可以分為五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。

排序算法分析

1．排序算法的基本操作

大多數(shù)排序算法都有兩個基本的操作：

(1) 比較兩個關(guān)鍵字的大??；

(2) 改變指向記錄的指針或移動記錄本身。

注意： 第(2)種基本操作的實現(xiàn)依賴于待排序記錄的存儲方式。

2．待排文件的常用存儲方式

（1） 以順序表(或直接用向量)作為存儲結(jié)構(gòu)

排序過程：對記錄本身進行物理重排（即通過關(guān)鍵字之間的比較判定，將記錄移到合適的位置）。

（2） 以鏈表作為存儲結(jié)構(gòu)

排序過程：無須移動記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈式)排序。

（3） 用順序的方式存儲待排序的記錄，但同時建立一個輔助表(如包括關(guān)鍵字和指向記錄位置的指針組成的索引表)

排序過程：只需對輔助表的表目進行物理重排（即只移動輔助表的表目，而不移動記錄本身）。適用于難于在鏈表上實現(xiàn)，仍需避免排序過程中移動記錄的排序方法。

3．排序算法性能評價

（1） 評價排序算法好壞的標準

評價排序算法好壞的標準主要有兩條：

• 執(zhí)行時間和所需的輔助空間
• 算法本身的復雜程度

（2） 排序算法的空間復雜度

若排序算法所需的輔助空間并不依賴于問題的規(guī)模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。 非就地排序一般要求的輔助空間為O(n)。

（3） 排序算法的時間開銷

大多數(shù)排序算法的時間開銷主要是關(guān)鍵字之間的比較和記錄的移動。有的排序算法其執(zhí)行時間不僅依賴于問題的規(guī)模，還取決于輸入實例中數(shù)據(jù)的狀態(tài)。

文件的順序存儲結(jié)構(gòu)表示

#define n l00 //假設(shè)的文件長度，即待排序的記錄數(shù)目  
typedef int KeyType； //假設(shè)的關(guān)鍵字類型  
typedef struct{ //記錄類型  
  KeyType key； //關(guān)鍵字項  
  InfoType otherinfo；//其它數(shù)據(jù)項，類型InfoType依賴于具體應用而定義  
 }RecType；  
typedef RecType SeqList[n+1]；//SeqList為順序表類型，表中第0個單元一般用作哨兵  

注意： 若關(guān)鍵字類型沒有比較算符，則可事先定義宏或函數(shù)來表示比較運算。

【例】關(guān)鍵字為字符串時，可定義宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那么算法中"a<b"可用"LT(a，b)"取代。若使用 C++，則定義重載的算符"<"更為方便。