⑴ 常規的排序演算法的共同點是什麼
常規的排序演算法的共同點是:
(1)比較;
(2)交換,即通過交換兩個數據之間的位置關系來達到符合要求的次序;
(3)移動,它是交換的變形,也是通過把數據從某一存儲地址換到另外的地址來達到符合要求的次序。
在計算機科學所使用的排序演算法通常被分類為:
(a)計算的復雜度(最差、平均、和最好性能),依據列表(list)的大小(n)。
一般而言,好的性能是O(nlogn),且壞的性能是O(n^2)。對於一個排序理想的性能是O(n)。
而僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要O(nlogn)。
(b)存儲器使用量(空間復雜度)(以及其他電腦資源的使用)
(c)穩定度:穩定的排序演算法會依照相等的關鍵(換言之就是值)維持紀錄的相對次序。
(d)一般的方法:插入、交換、選擇、合並等等。交換排序包含冒泡排序和快速排序。插入排序包含希爾排序,選擇排序包括堆排序等。