桶排序演算法原理

IT科技
關注：5.28K次

排序演算法是《資料結構與演算法》中最基本的演算法之一。排序演算法可以分為內部排序和外部排序，內部排序是資料記錄在記憶體中進行排序，而外部排序是因排序的資料很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序演算法有：插入排序、希爾排序、選擇排序、氣泡排序、歸併排序、快速排序、堆排序、基數排序等。以下是桶排序演算法：

桶排序是計數排序的升級版。它利用了函式的對映關係，高效與否的關鍵就在於這個對映函式的確定。為了使桶排序更加高效，我們需要做到這兩點：

在額外空間充足的情況下，儘量增大桶的數量使用的對映函式能夠將輸入的 N 個數據均勻的分配到 K 個桶中

同時，對於桶中元素的排序，選擇何種比較排序演算法對於效能的影響至關重要。

1. 什麼時候最快

當輸入的資料可以均勻的分配到每一個桶中。

2. 什麼時候最慢

當輸入的資料被分配到了同一個桶中。

3. 示意圖

元素分佈在桶中：

然後，元素在每個桶中排序：

程式碼實現

JavaScript

例項

Java

例項

public class BucketSort implements IArraySort {

private static final InsertSort insertSort = new InsertSort();

@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝，不改變引數內容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

return bucketSort(arr, 5);
}

private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
if (arr.length == 0) {
return arr;
}

int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}

int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
int[][] buckets = new int[bucketCount][0];

// 利用對映函式將資料分配到各個桶中
for (int i = 0; i < arr.length; i++) {
int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
buckets[index] = arrAppend(buckets[index], arr[i]);
}

int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// 對每個桶進行排序，這裡使用了插入排序
bucket = insertSort.sort(bucket);
for (int value : bucket) {
arr[arrIndex++] = value;
}
}

return arr;
}

/**
* 自動擴容，並儲存資料
*
* @param arr
* @param value
*/
private int[] arrAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}

}

PHP

例項

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;
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;
}
}

參考地址：
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

以下是熱心網友對桶排序演算法的補充，僅供參考：

熱心網友提供的補充1：

# coding=utf-8# author: [email protected]# datetime:2020/7/28 18:37"""程式說明：    桶排序    1）在額外空間充足的情況下，儘量增大桶的數量    2）使用的對映函式能夠將輸入的 N 個數據均勻的分配到 K 個桶中      個人理解，如果都是整數還可以用計數排序來計數統計然後排序，但是如果是一個連續空間內的排序，即統計的是一個浮點型別的陣列成      的陣列，那麼，就無法開闢一個對應的空間使其一一對應的儲存。此時，我們需要新建一個帶有儲存範圍的空間，來儲存一定範圍內的元素    空間複雜度：O(n)    時間複雜度: O(n)    穩定"""def bucket_sort_simplify(arr, max_num):    """    簡化版    """    buf = {i: [] for i in range(int(max_num)+1)}  # 不能使用[[]]*(max+1)，這樣新建的空間中各個[]是共享記憶體的    arr_len = len(arr)    for i in range(arr_len):        num = arr[i]        buf[int(num)].append(num)  # 將相應範圍內的資料加入到[]中    arr = []    for i in range(len(buf)):        if buf[i]:            arr.extend(sorted(buf[i]))  # 這裡還需要對一個範圍內的資料進行排序，然後再進行輸出    return arrif __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)))

熱心網友提供的補充2：

又沒把C#的寫進來，我來寫掉吧，程式碼如下：

static void BucketSort(List<int> list, int bucketCount, int maxBucketCount){    List<List<int>> buckets = new List<List<int>>(bucketCount);//二維列表    for (int i = 0; i < bucketCount; i++)    {        buckets.Add(new List<int>());    }    for (int i = 0; i < list.Count; i++)    {        // int j = Mathf.Min(list[i] / (maxBucketCount / bucketCount), bucketCount - 1);//j表示改放的哪個桶,不能大於n-1        int j = Math.Min(list[i] / (maxBucketCount / bucketCount), bucketCount - 1);//j表示改放的哪個桶,不能大於n-1        buckets[j].Add(list[i]);//放入對應桶        for (int x = buckets[j].Count - 1; x > 0; x--)//放一個排序一次，兩兩對比就可以        {            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;//如果不發生交換直接退出，因為前面的之前就排序好了            }        }    }    list.Clear();//輸出    for (int i = 0; i < buckets.Count; i++)    {        list.AddRange(buckets[i]);    }}

熱心網友提供的補充3：

C 語言實現桶排序，桶內採用插入排序:

#include <stdio.h>#include <stdlib.h>#include <string.h>#define BUCKET_SIZE (5) /**< 假定均勻分佈的情況下平均每個桶放幾個元素*/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    {        /** 桶內使用插入排序 */        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;}

下載測試程式碼

以上為桶排序演算法詳細介紹，插入排序、希爾排序、選擇排序、氣泡排序、歸併排序、快速排序、堆排序、基數排序等排序演算法各有優缺點，用一張圖概括：

關於時間複雜度

平方階 (O(n2)) 排序各類簡單排序：直接插入、直接選擇和氣泡排序。

線性對數階 (O(nlog2n)) 排序快速排序、堆排序和歸併排序；

O(n1+§)) 排序，§ 是介於 0 和 1 之間的常數。希爾排序

線性階 (O(n)) 排序基數排序，此外還有桶、箱排序。

關於穩定性

穩定的排序演算法：氣泡排序、插入排序、歸併排序和基數排序。

不是穩定的排序演算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：資料規模

k："桶"的個數

In-place：佔用常數記憶體，不佔用額外記憶體

Out-place：佔用額外記憶體

穩定性：排序後 2 個相等鍵值的順序和排序之前它們的順序相同

標籤：演算法

文章版權屬於文章作者所有，轉載請註明 https://shqsg.com/dianzi/4xm1e5.html

當前位置：生活全書館 >

IT科技