排序(sort)或分類

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

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

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

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

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

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

　　注意：

　　在不易產(chǎn)生混淆時，將關(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)計中將每個考生作為一個記錄。每條記錄包含準(zhǔn)考證號、姓名、各科的分?jǐn)?shù)和總分?jǐn)?shù)等項(xiàng)內(nèi)容。若要惟一地標(biāo)識一個考生的記錄，則必須用"準(zhǔn)考證號"作為關(guān)鍵字。若要按照考生的總分?jǐn)?shù)排名次，則需用"總分?jǐn)?shù)"作為關(guān)鍵字。

　　排序的穩(wěn)定性

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

　　填寫下面表單即可預(yù)約申請免費(fèi)試聽java課程!害怕學(xué)不會?助教陪讀，隨時解惑!擔(dān)心就業(yè)?一地學(xué)習(xí)，可全國推薦就業(yè)!

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

　　注意：

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

　　排序方法的分類

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

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

　　注意：

　�、� 內(nèi)排序適用于記錄個數(shù)不很多的小文件

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

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

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