本页使用了标题或全文手工转换

桶排序

维基百科,自由的百科全书
跳转至: 导航搜索
桶排序
分類 排序算法
數據結構 数组
最差時間複雜度 O(n^2)
平均時間複雜度 O(n+k)
最差空間複雜度 O(n*k)

桶排序 (Bucket sort)或所謂的箱排序,是一個排序演算法,工作的原理是將陣列分到有限數量的桶子裡。每個桶子再個別排序(有可能再使用別的排序演算法或是以遞迴方式繼續使用桶排序進行排序)。桶排序是鴿巢排序的一種歸納結果。當要被排序的陣列內的數值是均勻分配的時候,桶排序使用線性時間(Θn))。但桶排序並不是 比较排序,他不受到 O(n log n) 下限的影響。

桶排序以下列程序進行:

  1. 設置一個定量的陣列當作空桶子。
  2. 尋訪序列,並且把項目一個一個放到對應的桶子去。
  3. 對每個不是空的桶子進行排序。
  4. 從不是空的桶子裡把項目再放回原來的序列中。

虛擬碼[编辑]

function bucket-sort(array, n) is
  buckets ← new array of n empty lists
  for i = 0 to (length(array)-1) do
    insert array[i] into buckets[msbits(array[i], k)]
  for i = 0 to n - 1 do
    next-sort(buckets[i])
  return the concatenation of buckets[0], ..., buckets[n-1]

C++实现算法[编辑]

假设数据分布在[0,100)之间,每个桶内部用链表表示,在数据入桶的同时插入排序。 然后把各个桶中的数据合并。

#include<iterator>
#include<iostream>
#include<vector>
using namespace std;
const int BUCKET_NUM = 10;
 
struct ListNode{
	explicit ListNode(int i=0):mData(i),mNext(NULL){}
	ListNode* mNext;
	int mData;
};
 
ListNode* insert(ListNode* head,int val){
	ListNode dummyNode;
	ListNode *newNode = new ListNode(val);
	ListNode *pre,*curr;
	dummyNode.mNext = head;
	pre = &dummyNode;
	curr = head;
	while(NULL!=curr && curr->mData<=val){
		pre = curr;
		curr = curr->mNext;
	}
	newNode->mNext = curr;
	pre->mNext = newNode;
	return dummyNode.mNext;
}
 
 
ListNode* Merge(ListNode *head1,ListNode *head2){
	ListNode dummyNode;
	ListNode *dummy = &dummyNode;
	while(NULL!=head1 && NULL!=head2){
		if(head1->mData <= head2->mData){
			dummy->mNext = head1;
			head1 = head1->mNext;
		}else{
			dummy->mNext = head2;
			head2 = head2->mNext;
		}
		dummy = dummy->mNext;
	}
	if(NULL!=head1) dummy->mNext = head1;
	if(NULL!=head2) dummy->mNext = head2;
 
	return dummyNode.mNext;
}
 
void BucketSort(int n,int arr[]){
	vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));
	for(int i=0;i<n;++i){
		int index = arr[i]/BUCKET_NUM;
		ListNode *head = buckets.at(index);
		buckets.at(index) = insert(head,arr[i]);
	}
	ListNode *head = buckets.at(0);
	for(int i=1;i<BUCKET_NUM;++i){
		head = Merge(head,buckets.at(i));
	}
	for(int i=0;i<n;++i){
		arr[i] = head->mData;
		head = head->mNext;
	}
}

外部链接[编辑]

參考[编辑]