排序（sort）或分類

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

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

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

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

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

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

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

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

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

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

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

排序的穩(wěn)定性

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

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

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

排序方法的分類

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

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

注意：

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

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

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

排序算法分析

1．排序算法的基本操作

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

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

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

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

2．待排文件的常用存儲(chǔ)方式

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

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

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

排序過程：無須移動(dòng)記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈?zhǔn)?排序。

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

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

3．排序算法性能評(píng)價(jià)

（1） 評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)

評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)主要有兩條：

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

（2） 排序算法的空間復(fù)雜度

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

（3） 排序算法的時(shí)間開銷

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

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

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

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

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