算法排序之最簡單最快的排序--桶排序(Bucket Sort)

桶排序(Bucket Sort)：主要原理是将數組分到有限數量的桶子裡，每個桶子再按個别排序（有可能再使用别的排序算法或是以遞歸方式繼續使用桶排序進行排序）。

桶排序相對于同樣的N，桶數量M越大，其效率越高，最好的時間複雜度能達到O(N)。當然桶排序的空間複雜度為O(N+M)，如果輸入資料非常龐大，而桶的數量也會非常多，則空間代價無疑是昂貴的。

PS：此次我分享的并不是真正的桶排序算法，而是簡化版桶排序，讓初學算法排序的童學更易懂上手！

        接下來就開始主人公出場喽。

        在一次期末考試完了老師要将童學們的分數按照從高到低排序，咱們班一共10位童學，此時老師要讓計算機将這10個分數輸出，那我們該怎麼做呢？

首先我們要申請101個桶book[101]，分别表示分數0~100分，剛開始将book[0]~book[100]都初始化為0，表示這些分數都還沒有人得過，當出現分數時我們就相對應的将a[i]的值添加1，最後将出現過分數的下标列印出來即可。 

        是不是發現很簡單吧！ 那我們就用程式來實作一下，這在我主要就提供Java代碼（10個分數将是每次随機生成），别的語言大家感興趣都是可以自己編寫的。

public static void main(String[] args) {
		
		long startTime = System.currentTimeMillis();
		bucketSort(10, 100);
		long endTime = System.currentTimeMillis();
		System.out.println("\n" + (endTime - startTime));
	}
	
	public static void bucketSort(Integer input, Integer rand) {
		
		int[] book = new int[rand + 1];
		for (int i = 0; i < book.length; i++) {
			book[i] = 0;
		}
		Random r = new Random();
		for (int i = 0; i < input; i++) {
			
			int num = r.nextInt(rand);
			for (int j = 0; j < book.length; j++) {
				
				if (num == j) {
					book[j] ++;
				}
			}
		}
		
		for (int i = book.length -1 ; i >= 0; i--) {
			
			for (int j = 1; j <= book[i]; j++) {
				System.out.print(i + " ");
			}
		}
	}
           

       最後我們再來看一下算法的時間複雜度，在不包括随機數周遊的過程，此種簡化版桶排序的時間複雜度應該為O(N+M)，當然桶的數量非常多時，記憶體開辟的空間依然是個問題。        好，那我們最簡單最快的排序就講述完了。 但你們有沒有發現一個問題呢？ 老師一般在按分數排名的時候，最終想要看的是童學的名字，并不是分數。而此種排序無法對人本身進行排序， 那你會問有木有别的什麼排序呢？  答案是：肯定有。        期待我下一篇的文章分享。。  算法排序之鄰居好說話--冒泡排序！