桶排序（Bucket Sort）
一客冈、概念
- 執(zhí)行流程
- 創(chuàng)建一定數(shù)量的桶（比如用數(shù)組亡鼠，鏈表作為桶）赏殃。
- 按照一定的規(guī)則（不同類型的數(shù)據(jù)，規(guī)則不同）间涵，將序列中的元素均勻分配到對應的桶仁热。
- 分別對每個桶進行單獨排序。
- 將所有非空桶的元素合并成有序序列勾哩。
二抗蠢、實際操作
- 首先有如下一個數(shù)組：
image
- 數(shù)組中有
8個元素，那么創(chuàng)建8個桶思劳。 - 元素在桶中的索引：
元素值 * 元素數(shù)量迅矛。
image
- 對每個桶中的元素進行排序：
image
- 依次將桶中元素存入數(shù)組即可：
image
三、代碼實現(xiàn)
image
- 空間復雜度：
O(n + m)潜叛，m是桶的數(shù)量秽褒。
image
四壶硅、十大排序算法
image
- 冒泡，選擇销斟，插入庐椒，歸并，快速蚂踊，希爾约谈，堆排序，屬于
比較排序犁钟。 - 比較排序無法突破
O(nlogn)的效率棱诱。
