Buncket Sort桶排序（c++）實作代碼

代碼原理我就不說了，參考《算法導論》(原書第三版)p112

直接上代碼會不會很爽？

// ConsoleApplication1.cpp: 定義控制台應用程式的入口點。
//
/*
This programme is designed to show the BunckerSort;
Editor:Xiangyu Lv
E-mail:[email protected]//(abroad)
	[email protected]//(in china)
ALL RIGHTS RESERVED!
CSDN上的桶排序好多都退化成了Count Sort，我用了個比較簡單的方法，防止這種退化，如果您有更好的建議或意見歡迎在下方評論
版權聲明：本文為部落客原創文章，未經部落客允許不得轉載。*/
*/

#include "stdafx.h"
#include<iostream>
#include<ctime>
#include<vector>

using namespace std;

typedef unsigned long long MyLoop_t;

template<typename Comparable>
inline Comparable GetMax(vector<Comparable> &a) {
	Comparable Max = 0;
	for (MyLoop_t i = 0; i < a.size(); i++)
		if (a[i] > a[Max])
			Max = i;
	return a[Max];
}

template<typename Comparable>
void BuncketSort(vector<Comparable> &a) {
	Comparable Max = GetMax(a);
	
	MyLoop_t number = a.size();
	MyLoop_t gap =(Max/a.size())+1;//算出每個桶容量
	MyLoop_t buncketNumber = Max/gap+1;
	struct node {
		Comparable element;
		node* next;
	};
	node **allBuncket = new node*[sizeof(node)*buncketNumber];//new出一個桶數組,emmmm我也成劉備了，不過我比他輕松，hhhh :-）
	for (MyLoop_t i = 0; i < buncketNumber; i++)
	{
		allBuncket[i]=nullptr;
	}
	for (MyLoop_t i = 0; i < number; i++) {//資料入桶
		MyLoop_t buncketLab = a[i]/gap;//取桶下标
		if (allBuncket[buncketLab] == nullptr){//如果桶空
			allBuncket[buncketLab] = new node;
			allBuncket[buncketLab]->element = a[i];
			allBuncket[buncketLab]->next = nullptr;
		}
		else {
			if (allBuncket[buncketLab]->element > a[i]) {
				node *temp = new node;
				temp->element = a[i];
				temp->next = allBuncket[buncketLab];
				allBuncket[buncketLab] = temp;
			}
			else {
				node* temp = allBuncket[buncketLab];
				while (a[i] > temp->element && temp->next != nullptr && a[i]>temp->next->element) {
					temp = temp->next;
				}
				node *newNode = new node;
				newNode->element = a[i];
				newNode->next = temp->next;
				temp->next = newNode;
			}
		}
	}
	MyLoop_t j = 0;
	for (MyLoop_t i = 0; i <buncketNumber; i++) {
		if (allBuncket[i] != nullptr) {
			a[j++] = allBuncket[i]->element;
			node* temp = allBuncket[i]->next;
			while(temp!=nullptr){
				a[j++] = temp->element;
				node * temp2 = temp->next;
				delete temp;
				temp = temp2;
			}
			delete allBuncket[i];
		}
	}
	delete[] allBuncket;
}

int main()
{
	time_t start, end;
	vector<int>a;
	for (long long i = 0; i < 1000000; i++){
		int c = rand();
		a.push_back(c);
	}
	start = clock();
	BuncketSort(a);
	end = clock();
	double totaltime = (double)(end - start) / CLOCKS_PER_SEC;
	for (long long i = 1; i < 1000000; i++)
		if (a[i] < a[i - 1]) {
			cout << "error";
			return 1;
		}
	cout << totaltime<<'s'<<endl;
	system("pause");
    return 0;
}