數(shù)據(jù)結(jié)構(gòu)主講人：朱利華常州信息職業(yè)技術(shù)學(xué)院6.1排序的基本概念火車票——時間電話簿——姓氏電腦——最近修改時間數(shù)據(jù)結(jié)構(gòu)（Java語言描述）常州信息職業(yè)技術(shù)學(xué)院與日常生活息息相關(guān)排序排序基本概念和術(shù)語排序排序，把任意序列的數(shù)據(jù)記錄，按關(guān)鍵字遞增或遞減的次序重新排成一個有序的序列。有n個記錄的序列{R1,R2,…，

Rn

}，其相應(yīng)關(guān)鍵字序列是{K1,K2,…，Kn}，通過對這些關(guān)鍵字進(jìn)行比較排序，將這些記錄排列成一個有序的記錄序列{Rp1,Rp2,…，Rpn}，使得相應(yīng)的關(guān)鍵碼滿足Kp1≤Kp2≤?≤Kpn（升序）或Kp1≥Kp2≥?≥Kpn（降序），這樣的過程就稱為排序。排序目的為了查找方便。排序過程需要進(jìn)行兩種基本操作：排序的基本操作基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)（Java語言描述）常州信息職業(yè)技術(shù)學(xué)院比較兩個關(guān)鍵字值的大小將記錄從一個位置移動到另一個位置。數(shù)據(jù)元素又稱為記錄。一個數(shù)據(jù)元素或記錄可由多個數(shù)據(jù)項組成，能起到標(biāo)識作用的數(shù)據(jù)項稱為關(guān)鍵字。以數(shù)據(jù)元素某個數(shù)據(jù)項作為比較和排序依據(jù)，則該數(shù)據(jù)項稱為排序關(guān)鍵字。主關(guān)鍵字指能起到唯一標(biāo)識作用的關(guān)鍵字，反之稱次關(guān)鍵字。按照主關(guān)鍵字進(jìn)行排序，排序結(jié)果唯一，按次關(guān)鍵字進(jìn)行排序，排序結(jié)果可能不唯一。主關(guān)鍵詞與次關(guān)鍵字基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)（Java語言描述）常州信息職業(yè)技術(shù)學(xué)院排序不僅針對主關(guān)鍵字，也會參考次關(guān)鍵字。如待排序序列中存在兩個或兩個以上的關(guān)鍵字相等的記錄，排序結(jié)果會出現(xiàn)不唯一，導(dǎo)致排序穩(wěn)定和不穩(wěn)定兩種情況。排序的穩(wěn)定性基本概念和術(shù)語對于關(guān)鍵字值相同的兩個數(shù)據(jù)元素經(jīng)過某種排序算法排序后，若數(shù)據(jù)元素的位置關(guān)系排序前與排序后保持一致，則稱此排序方法是穩(wěn)定的；反之，則稱為不穩(wěn)定的。示例基本概念和術(shù)語對關(guān)鍵字值為5，3，8，3，6，6

的記錄排序?！痉治觥咳襞判蚝蟮男蛄袨?，3，5，6，6，8，其相同關(guān)鍵字值的元素位置依然是3在3前，6在6前，與排序前保持一致，則表示這種排序法是穩(wěn)定的。若排序后的序列為：3，3，5，6，6，8，則表示這種排序法是不穩(wěn)定的?！咀⒁狻糠€(wěn)定排序和不穩(wěn)定排序均能排好序。但在某些應(yīng)用場合，對排序的穩(wěn)定性是有特殊要求的。根據(jù)排序時數(shù)據(jù)所占用存儲器的不同，分為內(nèi)部排序和外部排序兩類。內(nèi)部排序是在排序整個過程中，待排序記錄都在內(nèi)存中。外部排序是由于排序的記錄個數(shù)太多，數(shù)量非常大，排序過程中需要借助外部存儲器（如磁盤）在內(nèi)外存之間多次交換數(shù)據(jù)才能進(jìn)行待排序，因此記錄一部分在內(nèi)存，一部分在外存。排序的分類基本概念和術(shù)語步驟外部排序：(1)預(yù)處理:從待排文件中讀取一組記錄到內(nèi)存排序區(qū)，按內(nèi)部排序法進(jìn)行排序，排好后輸出到外存中。不斷重復(fù)，每次讀一組記錄，直到原文的所有記錄被處理完畢。(2)將上一步分組排序好的記錄進(jìn)行合并排序。排序算法的性能指標(biāo)基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)（Java語言描述）常州信息職業(yè)技術(shù)學(xué)院時間復(fù)雜度比較次數(shù)和移動次數(shù)穩(wěn)定性CPU或內(nèi)存利用率高空間復(fù)雜度執(zhí)行算法所需空間排序算法類別基本概念和術(shù)語1插入類排序2交換類排序3選擇類排序4歸并類排序每次將一個待排記錄，按其關(guān)鍵字大小插入到前面已排好子序列的適當(dāng)位置，直到全部插入完成插入排序、折半排序、希爾排序每趟從待排記錄中選出最小或最大，順序放在已排好序列最后（前），直到全部記錄排序完直接選擇排序、堆排序兩兩比較待排序