排序(sort)或分類
所謂排序就是要整理文件中的記錄使之按關鍵字遞增(或遞減)次序排列起來其確切定義如下
輸入n個記錄R R …R n 其相應的關鍵字分別為K K …K n
輸出R il R i …R in 使得K i ≤K i ≤…≤K in (或K i ≥K i ≥…≥K in )
被排序對象文件
被排序的對象文件由一組記錄組成
記錄則由若干個數據項(或域)組成其中有一項可用來標識一個記錄稱為關鍵字項該數據項的值稱為關鍵字(Key)
注意
在不易產生混淆時將關鍵字項簡稱為關鍵字
排序運算的依據關鍵字
用來作排序運算依據的關鍵字可以是數字類型也可以是字符類型
關鍵字的選取應根據問題的要求而定
【例】在高考成績統計中將每個考生作為一個記錄每條記錄包含准考證號姓名各科的分數和總分數等項內容若要惟一地標識
一個考生的記錄則必須用准考證號作為關鍵字若要按照考生的總分數排名次則需用總分數作為關鍵字
排序的穩定性
當待排序記錄的關鍵字均不相同時排序結果是惟一的否則排序結果不唯一
在待排序的文件中若存在多個關鍵字相同的記錄經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變該排序方
法是 穩定的 ;若具有相同關鍵字的記錄之間的相對次序發生變化則稱這種排序方法是 不穩定的
注意
排序算法的穩定性是針對所有輸入實例而言的即在所有可能的輸入實例中只要有一個實例使得算法不滿足穩定性要求則該
排序算法就是不穩定的
排序方法的分類
按是否涉及數據的內外存交換分
在排序過程中若整個文件都是放在內存中處理排序時不涉及數據的內外存交換則稱之為 內部排序 (簡稱內排序);反之
若排序過程中要進行數據的內外存交換則稱之為 外部排序
注意
① 內排序適用於記錄個數不很多的小文件
② 外排序則適用於記錄個數太多不能一次將其全部記錄放人內存的大文件
按策略劃分內部排序方法
可以分為五類插入排序選擇排序交換排序歸並排序和分配排序
From:http://tw.wingwit.com/Article/program/sjjg/201311/23810.html
