摘要： 前面講了插入排序，交換排序，選擇排序，歸并排序，下面接著來講桶排序，基數排序。 桶排序和基數排序均屬于分配排序。分配排序的基本思想：排序過程無須比較關鍵字，而是通過用額外的空間來"分配"和"收集"來實現排序，它們的時間復雜度可達到線性階：O(n)。簡言之就是：用空間換時間，所以性能與基于比較的排序才有數量級的提高！ 桶排序(Bucket Sort)，也稱箱排序 基本思想：設置若干個箱子，依次掃描待排序的記錄 array[0]，array[1]，…，array[n - 1]，把關鍵字等于 k 的記錄全都裝入到第 k 個箱子里(分配)，然后按序號依次將各非空的箱子里的記錄收集起來，從而完成排序。 閱讀全文