大學《數(shù)據(jù)結構》第七章：排序-第一節(jié)-基本概念

本章概覽當前講授一、知識結構二、本章重難點本章的學習目的是要求考生深刻理解各種內(nèi)部排序方法的基本思想及其特點；熟悉各種內(nèi)部排序方法的排序過程；掌握各種內(nèi)部排序算法的時間復雜度的分析方法，并熟記其分析結論；要求能根據(jù)各種排序方法的優(yōu)缺點及不同的應用場合，選擇合適的方法進行排序。其中，插入排序，要求達到"綜合應用"層次。本章重點是各種內(nèi)部排序算法的基本思想，算法的實現(xiàn)過程和性能分析比較是本章的難點。第一節(jié)基本概念1、排序（sort）的概念所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。2、排序的穩(wěn)定性在待排序的文件中，若存在多個關鍵字相同的記錄，經(jīng)過排序后這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的；若具有相同關鍵字的記錄之間的相對次序發(fā)生變化，則稱這種排序方法是不穩(wěn)定的。注意：排序算法的穩(wěn)定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得算法不滿足穩(wěn)定性要求，則該排序算法就是不穩(wěn)定的。3、排序方法的分類（1）按是否涉及數(shù)據(jù)的內(nèi)、外存交換分在排序過程中，若整個文件都是放在內(nèi)存中處理，排序時不涉及數(shù)據(jù)的內(nèi)、外存交換，則稱之為內(nèi)部排序(簡稱內(nèi)排序)；反之，若排序過程中要進行數(shù)據(jù)的內(nèi)、外存交換，則稱之為外部排序。注意：①內(nèi)排序適用于記錄個數(shù)不很多的小文件②外排序則適用于記錄個數(shù)太多，不能一次將其全部記錄放入內(nèi)存的大文件。（2）按策略劃分內(nèi)部排序方法內(nèi)部排序可以分為五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。4．排序算法性能評價（1）評價排序算法好壞的標準①執(zhí)行算法需要的時間②算法所需的輔助空間③算法本身的復雜程度（2）排序算法的時間開銷一般情況下，用算法執(zhí)行中關鍵字之間的比較次數(shù)和記錄的移動次數(shù)來衡量。（3）排序算法的空間復雜度若排序算法所需的輔助空間并不依賴于問題的規(guī)模n，空間復雜度是O(1)，則稱這樣的排序為就地排序。非就地排序的空間復雜度是一般為O(n)。當前講授5、待排序記錄的數(shù)據(jù)類型定義#definenl00//假設的文件長度，即待排序的記錄數(shù)目typedefintKeyType；//假設的關鍵字類型typedefstruct//記錄類型{KeyTypekey；//關鍵字項InfoTypeotherinfo；//其它數(shù)據(jù)項，類型InfoType依賴于具體應用而定義}RecType；typedefRecTypeSeqList[MAXSIZE+1]；//SeqList為順序表類型，表中第0個單元一般用作哨兵sqlistR；//R順序表類型數(shù)組【真題選解】（例題?單選題）如果在排序過程中不改變關鍵字相同元素的相對位置，則認為該排序方法是()A.不穩(wěn)定的B.穩(wěn)定的C.基于交換