mData;? ? ? ? ? ? ? ? head = head->mNext;? ? ? ? }}參考地址：
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/9.bucketSort.md
https://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F
以下是熱心網(wǎng)友對(duì)桶排序算法的補(bǔ)充，僅供參考：
熱心網(wǎng)友提供的補(bǔ)充1：
# coding=utf-8
# author: [email protected]
# datetime:2020/7/28 18:37
"""
程序說(shuō)明：
桶排序
1）在額外空間充足的情況下，盡量增大桶的數(shù)量
2）使用的映射函數(shù)能夠?qū)⑤斎氲?N 個(gè)數(shù)據(jù)均勻的分配到 K 個(gè)桶中
個(gè)人理解，如果都是整數(shù)還可以用計(jì)數(shù)排序來(lái)計(jì)數(shù)統(tǒng)計(jì)然后排序，但是如果是一個(gè)連續(xù)空間內(nèi)的排序，即統(tǒng)計(jì)的是一個(gè)浮點(diǎn)類型的數(shù)組成
的數(shù)組，那么，就無(wú)法開(kāi)辟一個(gè)對(duì)應(yīng)的空間使其一一對(duì)應(yīng)的存儲(chǔ)。此時(shí)，我們需要新建一個(gè)帶有存儲(chǔ)范圍的空間，來(lái)存儲(chǔ)一定范圍內(nèi)的元素
空間復(fù)雜度：O(n)
時(shí)間復(fù)雜度: O(n)
穩(wěn)定
"""
def bucket_sort_simplify(arr, max_num):
"""
簡(jiǎn)化版
"""
buf = {i: [] for i in range(int(max_num)+1)} # 不能使用[[]]*(max+1)，這樣新建的空間中各個(gè)[]是共享內(nèi)存的
arr_len = len(arr)
for i in range(arr_len):
num = arr[i]
buf[int(num)].append(num) # 將相應(yīng)范圍內(nèi)的數(shù)據(jù)加入到[]中
arr = []
for i in range(len(buf)):
if buf[i]:
arr.extend(sorted(buf[i])) # 這里還需要對(duì)一個(gè)范圍內(nèi)的數(shù)據(jù)進(jìn)行排序，然后再進(jìn)行輸出
return arr
if __name__ == "__main__":
lis = [3.1, 4.2, 3.3, 3.5, 2.2, 2.7, 2.9, 2.1, 1.55, 4.456, 6.12, 5.2, 5.33, 6.0, 2.12]
print(bucket_sort_simplify(lis, max(lis)))熱心網(wǎng)友提供的補(bǔ)充2：
又沒(méi)把C#的寫(xiě)進(jìn)來(lái)，我來(lái)寫(xiě)掉吧，代碼如下：
static void BucketSort(List list, int bucketCount, int maxBucketCount)
{
List> buckets = new List>(bucketCount);//二維列表
for (int i = 0; i < bucketCount; i++)
{
buckets.Add(new List());
}
for (int i = 0; i < list.Count; i++)
{
// int j = Mathf.Min(list[i] / (maxBucketCount / bucketCount), bucketCount - 1);//j表示改放的哪個(gè)桶,不能大于n-1
int j = Math.Min(list[i] / (maxBucketCount / bucketCount), bucketCount - 1);//j表示改放的哪個(gè)桶,不能大于n-1
buckets[j].Add(list[i]);//放入對(duì)應(yīng)桶
for (int x = buckets[j].Count - 1; x > 0; x--)//放一個(gè)排序一次，兩兩對(duì)比就可以
{
if (buckets[j][x] < buckets[j][x - 1])//升序
{
int tmp = buckets[j][x];//交換
buckets[j][x] = buckets[j][x - 1];
buckets[j][x - 1] = tmp;
}
else
{
break;//如果不發(fā)生交換直接退出，因?yàn)榍懊娴闹熬团判蚝昧?
}
}
}
list.Clear();//輸出
for (int i = 0; i < buckets.Count; i++)
{
list.AddRange(buckets[i]);
}
}
熱心網(wǎng)友提供的補(bǔ)充3：
C 語(yǔ)言實(shí)現(xiàn)桶排序，桶內(nèi)采用插入排序:
#include
#include
#include
#define BUCKET_SIZE (5) /**< 假定均勻分布的情況下平均每個(gè)桶放幾個(gè)元素*/
typedef struct Node
{
int elem;
struct Node* list_next;
} Node;
typedef struct BucketManager
{
int nums;
Node** buckets;
} BucketManager;
typedef struct BucketSpaceManager
{
int index;
Node* nodes_space;
} BucketSpaceManager;
BucketSpaceManager* init_bucket_space(int size)
{
BucketSpaceManager* space_mgr = (BucketSpaceManager*)malloc(sizeof(BucketSpaceManager));
if (!space_mgr)
{
printf("out of memory,File:%s, Func:%s, Line:%d
", __FILE__, __func__, __LINE__);
goto exit_1;
}
space_mgr->index = 0;
space_mgr->nodes_space = (Node*)malloc(size * sizeof(Node));
if (!space_mgr->nodes_space)
{
printf("out of memory,File:%s, Func:%s, Line:%d
", __FILE__, __func__, __LINE__);
goto exit_2;
}
return space_mgr;
exit_2:
free(space_mgr);
exit_1:
return NULL;
}
BucketManager* init_buckets(int bucket_nums)
{
BucketManager* bucket_mgr = (BucketManager*)malloc(sizeof(BucketManager));
if (!bucket_mgr)
{
printf("out of memory,File:%s, Func:%s, Line:%d
", __FILE__, __func__, __LINE__);
goto exit_1;
}
bucket_mgr->nums = bucket_nums;
bucket_mgr->buckets = (Node**)calloc(bucket_mgr->nums, sizeof(Node*));
if (!bucket_mgr->buckets)
{
printf("out of memory,File:%s, Func:%s, Line:%d
", __FILE__, __func__, __LINE__);
goto exit_2;
}
return bucket_mgr;
exit_2:
free(bucket_mgr);
exit_1:
return NULL;
}
Node* get_bucket_space(BucketSpaceManager* space_mgr)
{
if (space_mgr)
{
return &space_mgr->nodes_space[space_mgr->index++];
}
else
{
return NULL;
}
}
void release_bucket_space(BucketSpaceManager* space_mgr)
{
if (space_mgr)
{
if (space_mgr->nodes_space)
{
free(space_mgr->nodes_space);
}
free(space_mgr);
}
}
void release_buckets(BucketManager* buckets_mgr)
{
if (buckets_mgr)
{
if (buckets_mgr->buckets)
{
free(buckets_mgr->buckets);
}
free(buckets_mgr);
}
}
int find_max_min(int* arr, int size, int* p_max, int* p_min)
{
if (size <= 0)
{
return -1;
}
*p_max = arr[0];
*p_min = arr[0];
int i;
for (i = 1; i < size; ++i)
{
if (arr[i] > *p_max)
{
*p_max = arr[i];
}
if (arr[i] < *p_min)
{
*p_min = arr[i];
}
}
return 0;
}
int insert_bucket(BucketManager* bucket_mgr, int index, Node* new_node)
{
Node* cur, *pre;
if (!bucket_mgr->buckets[index])
{
bucket_mgr->buckets[index] = new_node;
}
else
{
/** 桶內(nèi)使用插入排序 */
cur = bucket_mgr->buckets[index];
pre = cur;
while (cur->list_next && new_node->elem > cur->elem)
{
pre = cur;
cur = cur->list_next;
}
if (new_node->elem <= cur->elem)
{
if (pre == cur)
{
new_node->list_next = cur;
bucket_mgr->buckets[index] = new_node;
}
else
{
new_node->list_next = cur;
pre->list_next = new_node;
}
}
else
{
cur->list_next = new_node;
}
}
return 0;
}
void bucket_sort(int* arr, int size)
{
int max, min;
int ret = find_max_min(arr, size, &max, &min);
if (ret < 0)
{
return;
}
BucketSpaceManager* space_mgr = init_bucket_space(size);
if (!space_mgr)
{
printf("out of memory,File:%s, Func:%s, Line:%d
", __FILE__, __func__, __LINE__);
goto exit_1;
}
int bucket_nums = (max - min) / BUCKET_SIZE + 1;
BucketManager* bucket_mgr = init_buckets(bucket_nums);
if (!bucket_mgr)
{
goto exit_2;
}
int i;
for (i = 0; i < size; ++i)
{
int index = (arr[i] - min) / BUCKET_SIZE;
Node* new_node = get_bucket_space(space_mgr);
if (!new_node)
{
goto exit_3;
}
new_node->elem = arr[i];
new_node->list_next = NULL;
insert_bucket(bucket_mgr, index, new_node);
}
for (i = 0; i < bucket_mgr->nums; ++i)
{
Node* node = bucket_mgr->buckets[i];
while(node)
{
printf("%d ", node->elem);
node = node->list_next;
}
}
printf("
");
exit_3:
release_buckets(bucket_mgr);
exit_2:
release_bucket_space(space_mgr);
exit_1:
return;
}
下載測(cè)試代碼
以上為桶排序算法詳細(xì)介紹，插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等排序算法各有優(yōu)缺點(diǎn)，用一張圖概括： 
關(guān)于時(shí)間復(fù)雜度
平方階 (O(n2)) 排序 各類簡(jiǎn)單排序：直接插入、直接選擇和冒泡排序。
線性對(duì)數(shù)階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數(shù)。 希爾排序
線性階 (O(n)) 排序 基數(shù)排序，此外還有桶、箱排序。
關(guān)于穩(wěn)定性
穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序。
不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序。
名詞解釋：
n：數(shù)據(jù)規(guī)模
k："桶"的個(gè)數(shù)
In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存
Out-place：占用額外內(nèi)存
穩(wěn)定性：排序后 2 個(gè)相等鍵值的順序和排序之前它們的順序相同
科技
