桶排序

• 2022 年 3 月 5 日
• 筆記

桶排序

桶排序的思想是，若待排序的記錄的關鍵字在一個明顯有限範圍內時，可設計有限個有序桶，每個桶只能裝與之對應的值，順序輸出各桶的值，將得到有序的序列。簡單來說，在我們可以確定需要排列的數組的範圍時，可以生成該數值範圍內有限個桶去對應數組中的數，然後我們將掃描的數值放入匹配的桶里的行為，可以看作是分類，在分類完成後，我們需要依次按照桶的順序輸出桶記憶體放的數值，這樣就完成了桶排序。

程式碼+思路

#include<stdio.h>
int main()
{	
	int a[10]={0};	//以10個桶為例，必須將10個桶初始值設為0
	int n;			//要輸入的數字個數 
	scanf("%d",&n);
	int i,j;
	for(i=0;i<n;i++)
	{
		int key;
		scanf("%d",&key);
		a[key]++;	//輸入key，key會放在a[key]中，同時a[key]++記錄了該桶存放的數據+1 
		
	}
	for(i=0;i<10;i++)	//這裡表示將這10個桶裡面的數全部輸出，如果寫n，則輸出到n桶就停止了，如果有比n要大的數字即存放在了n桶後面就無法輸出 
		for(j=0;j<a[i];j++)	//小於a[i] ，一個桶裡面可能有好幾個一樣的數字 
			printf("%d ",i);
	return 0;
}