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

　　冒泡排序

　　·自下向上確定最輕的一個

　　·自上向下確定最重的一個

　　·自下向上確定最輕的一個後自上向下確定最重的一個

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

　　快速排序

　　·以第一個元素為參考基准設定動兩個指針發生交換後指針交換位置直到指針重合重復直到排序完成

　　·快速排序是非就地的不穩定排序時間復雜度為O(nlogn)比較次數為n(n)/

　　選擇排序

　　·直接選擇排序

　　·選擇最小的放在比較區前

　　·直接選擇排序就地的不穩定排序時間復雜度為O(n^)比較次數為n(n)/

　　堆排序

　　·建堆按層次將數據填入完全二叉樹從int(n/)處向前逐個調整位置

　　·然後將樹根與最後一個葉子交換值並斷開與樹的連接並重建堆直到全斷開

　　·堆排序是就地不穩定的排序時間復雜度為O(nlogn)不適宜於記錄數較少的文件

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

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