【C++信息學(xué)奧賽培訓】數據排序之桶排序(BucketSort)詳解以及實例解析

一、桶排序算法介紹：

桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就(jiù)在于這(zhè)個映射函數的确定。爲了使桶排序更加高效，我們需要做到這(zhè)兩(liǎng)點：

1.在額外空間充足的情況下，盡量增大桶的數量。

2.使用的映射函數能(néng)夠將(jiāng)輸入的 N 個數據均勻的分配到 K 個桶中同時(shí)，對(duì)于桶中元素的排序，選擇何種(zhǒng)比較排序算法對(duì)于性能(néng)的影響至關重要。

二、桶排序算法可視化演示：

元素分布在桶中：

然後(hòu)，元素在每個桶中排序：

三、什麼(me)時(shí)候最快？

當輸入的數據可以均勻的分配到每一個桶中。

四、什麼(me)時(shí)候最慢？

當輸入的數據被分配到了同一個桶中。

五、桶排序算法實例解析（信息學(xué)奧賽一本通例題）