09年自考《數據結構》各章要點二[6]

　　經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變則稱這種排序方法是穩定的否則排序算法是不穩定的

　　排序過程中不涉及數據的內外存交換則稱之為內部排序(內排序)反之若存在數據的內外存交換則稱之為外排序

　　內部排序方法可分五類插入排序選擇排序交換排序歸並排序和分配排序

　　評價排序算法好壞的標准主要有兩條執行時間和所需的輔助空間另外算法的復雜程序也是要考慮的一個因素

　　插入排序

　　·直接插入排序

　　·逐個向前插入到合適位置

　　·哨兵(監視哨)有兩個作用

　　·作為臨變量存放R[i]

　　·是在查找循環中用來監視下標變量j是否越界

　　·直接插入排序是就地的穩定排序時間復雜度為O(n^)比較次數為(n+)(n)/;移動次數為(n+)(n)/

　　希爾排序

　　·等間隔的數據比較並按要求順序排列最後間隔為

　　·希爾排序是就地的不穩定排序時間復雜度為O(n^)比較次數為(n^)移動次數為(n^)

　　交換排序

[]  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/22727.html