# 桶排序

分類 排序算法 数组 $O(n^2)$ $O(n+k)$ $O(n*k)$

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++实现算法

```#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;
pre = &dummyNode;
while(NULL!=curr && curr->mData<=val){
pre = curr;
curr = curr->mNext;
}
newNode->mNext = curr;
pre->mNext = newNode;
return dummyNode.mNext;
}

ListNode dummyNode;
ListNode *dummy = &dummyNode;
}else{
}
dummy = dummy->mNext;
}

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);
}
ListNode *head = buckets.at(0);
for(int i=1;i<BUCKET_NUM;++i){