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

　　歸並排序

　　·先兩個一組排序形成(n+)/組再將兩組並一組直到剩下一組為止

　　·歸並排序是非就地穩定排序時間復雜度是O(nlogn)

　　分配排序

　　箱排序

　　·按關鍵字的取值范圍確定箱子數按關鍵字投入箱子鏈接所有非空箱

　　·箱排序的平均時間復雜度是線性的O(n)

　　基數排序

　　·從低位到高位依次對關鍵字進行箱排序

　　·基數排序是非就穩定的排序時間復雜度是O(d*n+d*rd)

　　各種排序方法的比較和選擇

　　·待排序的記錄數目nn較大的要用時間復雜度為O(nlogn)的排序方法

　　·記錄的大小(規模)記錄大最好用鏈表作為存儲結構而快速排序和堆排序在鏈表上難於實現

　　·關鍵字的結構及其初始狀態

　　·對穩定性的要求

　　·語言工具的條件

　　·存儲結構

　　·時間和輔助空間復雜度

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

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