桶排序

一、基本思路

a、將數(shù)組中元素劃分到不同的桶中。先對遍歷數(shù)組找到最大值元素（maxNum）和最小值元素（minNum），然后設(shè)定用的個數(shù)為x個，然后把【maxNum,minNum】均勻劃分成?x個區(qū)間，每個區(qū)間就是一個桶。將數(shù)組中的元素分配到各相應(yīng)的桶中；

b、對桶內(nèi)的元素進行排序，任意選擇一種排序算法；

c、將各個桶中的元素合并成一個大的有序序列（數(shù)組）；

d、假設(shè)數(shù)據(jù)是均勻分布的，則每個桶的元素平均個數(shù)為?n/k?。假設(shè)選擇用快速排序?qū)γ總€桶內(nèi)的元素進行排序，那么每次排序的時間復(fù)雜度為?O(n/klog(n/k))?。總的時間復(fù)雜度為O(n)+O(m)O(n/klog(n/k)) = O(n+nlog(n/k)) = O(n+nlogn-nlogk?。所以桶排序的時間復(fù)雜度和空間復(fù)雜度都為：O(n+k)；當?k?接近于?n?時，桶排序的時間復(fù)雜度就可以認為是?O(n)的。即桶越多，時間效率就越高，而桶越多，空間就越大。

桶排序在什么時候最快呢？->?當輸入的數(shù)據(jù)可以均勻的分配到每一個桶中。

桶排序在什么時候最慢呢？->當輸入的數(shù)據(jù)被分配到了同一個桶中。

二、代碼實現(xiàn)

更多算法知識【瘋狂1024】