非比較排序——桶排序

相對于計數排序，桶排序和計數排序的差别就在于處理相同資料的差别上。計數排序假設輸入資料都屬于一個小區間内的整數，而桶排序則是假設輸入是由一個随時過程産生的，該過程将元素均勻分布在[0, 1)區間上。

在桶排序的過程中有一個非常重要的地方就是，投射的位置 =  current_data * number_array / maximum_array_scope ， 如果出現多個數投射在相同的位置上，那麼這裡就和hash 處理沖突一樣，補充一個連結清單，并且在連結清單中元素是有序的。

圖解：

考慮到圖檔太大的問題，是以每一張圖檔都剪成了2張

一共生成30個随機資料，下一張圖是和這張圖相連的

經過映射之後的情況是：

最後隻需要依次序輸出即可。

#include <iostream>
#include <list>
#include <algorithm>
#include <time.h>
#include <string.h>
#define MAX 1000
#define N 30
using namespace std;
typedef list<int> LISTINT;

int main()
{
	LISTINT::iterator iter;
	int a[N];
	srand(time(NULL));
	
	for(int i =0;i < N; i++)
		a[i] = rand()%MAX;
	for(int i = 0;i < N; i++)
		cout << a[i] << " ";
	cout << endl;
	
	LISTINT *listAll = new LISTINT[N];
	int index[N];
	memset(index, 0, sizeof(index));
	
	for(int i = 0; i < N; i++)
	{
		int temp = a[i]*N / MAX;
		if(index[temp]==0)
		{
			index[temp] = 1;
			listAll[temp].push_back(a[i]);
		}else{
			listAll[temp].push_back(a[i]);
			listAll[temp].sort();
		}
	}
	for(int i = 0; i < N; i++)
	{
		if(index[i] != 0)
			for(iter = listAll[i].begin(); iter != listAll[i].end(); ++iter)
				cout << *iter << " ";
	}
	cout << endl;
	delete(listAll);
	return 0;
}