排序概念
排序：將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列疚颊，重新排列成一個(gè)按關(guān)鍵字有序的序列兴使。
排序定義
假設(shè)含n個(gè)記錄的序列為:
{R0,R1,...,R(n-1)} (1)
其相應(yīng)的關(guān)鍵字序列為：
{K0,K1,...,K(n-1)} (2)
需確定0,1,2立由，n-1的一種排序p0,p1,...,p(n-1)给赞，使其相應(yīng)的關(guān)鍵字滿足如下的非遞減（或非遞增）關(guān)系：
Kp0<=Kp1<=...<=Kp(n-1)
即使式（1）的序列成為一個(gè)按關(guān)鍵字有序的序列：
{Rp0,Rp1,...,Rp(n-1)} (3)
穩(wěn)定排序和不穩(wěn)定排序
關(guān)鍵Ki可以是記錄Ri(i=0,1,2,...,n-1)的主關(guān)鍵字舀武，也可以是記錄Ri的次關(guān)鍵字，甚至是若干數(shù)據(jù)項(xiàng)的組合骏啰。
若Ki是主關(guān)鍵字节吮，則任何一個(gè)記錄的無序序列經(jīng)排序后得到的結(jié)果是唯一的；
若Ki是次關(guān)鍵字判耕，則排序的結(jié)果不唯一透绩，因?yàn)榇判虻挠涗浶蛄兄锌赡艽嬖趦蓚€(gè)或兩個(gè)以上關(guān)鍵字相等的記錄。
若Ki = Kj(0<=i<=n-1,0<=j<=n-1,i!=j),且在排序前的序列中Ri領(lǐng)先于Rj(即i<j)壁熄。
若在排序后的序列中Ri仍領(lǐng)先于Rj帚豪，則稱所用的排序方法是穩(wěn)定的；反之草丧，若可能使排序后的序列中Rj領(lǐng)先于Ri狸臣，則稱所用的排序方法是不穩(wěn)定的。
排序的分類
內(nèi)部排序：待排序記錄存放在計(jì)算機(jī)隨機(jī)存儲器中進(jìn)行的排序過程
外部排序：待排序記錄的數(shù)量很大昌执，以致內(nèi)存一次不能容納全部記錄烛亦，在排序過程中尚需對外存進(jìn)行訪問的排序過程诈泼。
內(nèi)部排序的分類——不同原則
插入排序、交換排序此洲、選擇排序、歸并排序委粉、計(jì)數(shù)排序
內(nèi)部排序的分類——工作量
- 簡單的排序方法呜师，時(shí)間復(fù)雜度為O(n^2)
- 先進(jìn)的排序方法，時(shí)間復(fù)雜度為O(nlogn)
- 基數(shù)排序贾节，時(shí)間復(fù)雜度為O(d * n)
排序需要的基本操作
（1）比較兩個(gè)關(guān)鍵字的大兄埂；（必要）
（2）將記錄從一個(gè)位置移動至另一個(gè)位置栗涂。（通過改變記錄的存儲方式來予以避免）
待排序記錄序列的存儲方式
（1）待排序的一組記錄存放在地址連續(xù)的一組存儲單元上知牌。在序列中相鄰的兩個(gè)記錄Rj和Rj+1(j=0,1,...,n-1)，它們的存儲位置也相鄰斤程。在這種存儲方式中角寸，記錄之間的次序關(guān)系由其存儲位置決定，而實(shí)現(xiàn)排序必須借助移動記錄忿墅。
（2）一組待排序記錄存放在靜態(tài)鏈表中扁藕，記錄之間的次序關(guān)系由指針指示，則實(shí)現(xiàn)排序不需要移動記錄疚脐，僅需修改指針即可亿柑。——鏈表排序
（3）待排序記錄本身存儲在一組地址連續(xù)的存儲單元內(nèi)棍弄，同時(shí)另設(shè)一個(gè)指示各個(gè)記錄存儲位置的地址向量望薄，在排序過程中不移動記錄本身，而移動地址向量中這些記錄的“地址”呼畸，在排序結(jié)束之后再按照地址向量中的值調(diào)整記錄的存儲位置痕支。——地址排序
