快捷導(dǎo)航

C語(yǔ)言排序算法之桶排序解析

更新時(shí)間：2023年10月30日 10:23:21 作者：有人_295

這篇文章主要介紹了C語(yǔ)言排序算法之桶排序解析,桶排序Bucket?sort或所謂的箱排序,是一個(gè)排序算法,工作的原理是將數(shù)組分到有限數(shù)量的桶里,每個(gè)桶再分別排序,大部分是在分桶時(shí),即插入時(shí)就排序了,需要的朋友可以參考下

1. 算法思想

桶排序（Bucket sort）或所謂的箱排序，是一個(gè)排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶里，每個(gè)桶再分別排序（大部分是在分桶時(shí)，即插入時(shí)就排序了）。

個(gè)人理解，適合數(shù)據(jù)比較集中排序，桶的數(shù)量適當(dāng)設(shè)置。

2. 實(shí)現(xiàn)原理

桶排序以下列程序進(jìn)行：

設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶子。
尋訪序列，并且把項(xiàng)目一個(gè)一個(gè)放到對(duì)應(yīng)的桶子去。
對(duì)每個(gè)不是空的桶子進(jìn)行排序。
從不是空的桶子里把項(xiàng)目再放回原來(lái)的序列中。

3. 動(dòng)態(tài)演示

在這里插入圖片描述

（1）數(shù)據(jù)分桶

在這里插入圖片描述

（2）桶內(nèi)數(shù)據(jù)排序（大部分是在分桶時(shí)，即插入時(shí)就排序了）

在這里插入圖片描述

（3）然后連接就好了

4. 完整代碼

主要函數(shù)

插入函數(shù)：void insert(BN* list, int value)
排序函數(shù)：void bucket_sort(int* array, int size, int num)

#include <malloc.h>
#include <stdio.h>
#include <stdlib.h> // rand() srand()
#include <time.h>   // time()

typedef struct BucketNode
{
    int                data;
    struct BucketNode* next;
} BN;

void displayL(BN* L);               // 輸出鏈表
void display(int* array, int size); // 輸出數(shù)組
int  check(int* array, int size);   // 檢查函數(shù)

/***************************************************************************
 * @date    2020/12/03
 * @brief   合并鏈表
 * @param   head    頭指針
 * @param   list    順序數(shù)據(jù)鏈表
 ***************************************************************************/
BN* merge(BN* head, BN* list)
{
    BN* last   = head;
    last->next = list->next;
    while (last->next) {
        last = last->next;
    }
    return last;
}

/***************************************************************************
 * @date    2020/12/03
 * @brief   順序插入節(jié)點(diǎn)
 * @param   list    代表第幾個(gè)桶的鏈表
 * @param   value   數(shù)據(jù)
 ***************************************************************************/
void insert(BN* list, int value)
{
    BN* prev   = list;
    BN* curr   = list->next;
    BN* node   = (BN*)malloc(sizeof(BN));

    node->data = value;
    node->next = NULL;
    if (curr == NULL) {
        prev->next = node;
    } else {
        while (curr != NULL && curr->data < value) {
            prev = curr;
            curr = curr->next;
        }
        prev->next = node;
        node->next = curr;
    }
}

/***************************************************************************
 * @date    2020/12/03
 * @brief   桶排序主程序
 * @param   array   數(shù)組
 * @param   size    數(shù)組大小
 * @param   num     幾個(gè)桶
 ***************************************************************************/
void bucket_sort(int* array, int size, int num)
{
    // 申請(qǐng)內(nèi)存，二級(jí)指針，初始化，可以理解頭指針沒(méi)數(shù)據(jù)，從下一個(gè)開(kāi)始存數(shù)數(shù)據(jù)
    BN** buckets = (BN**)malloc(sizeof(BN*) * num);
    for (int i = 0; i < num; i++) {
        *(buckets + i)         = (BN*)malloc(sizeof(BN));
        (*(buckets + i))->next = NULL;
    }

    // 1. 找到最大值和最小值求間隔（桶的大?。?
    int max = array[0];
    int min = array[0];
    for (int i = 0; i < size; i++) {
        if (array[i] > max) {
            max = array[i];
        }
        if (array[i] < min) {
            min = array[i];
        }
    }
    int space = ((max - min) / num) + 1;

    // 2. 一個(gè)一個(gè)分桶排序
    for (int i = 0; i < size; i++) {
        int n = (array[i] - min) / space;
        insert(*(buckets + n), array[i]);
    }
    for (int i = 0; i < num; i++) {
        printf("第 %d 個(gè)桶數(shù)據(jù): ", i);
        displayL((*(buckets + i))->next);
    }

    // // 3. 合并鏈表
    // BN* head   = (BN*)malloc(sizeof(BN));
    // head->next = NULL;
    // BN* last   = merge(head, *(buckets + 0));
    // for (int i = 1; i < num; i++) {
    //     if ((*(buckets + i))->next) {
    //         last = merge(last, *(buckets + i));
    //     }
    // }
    // head = head->next;

    // // 4. 把鏈表值返回?cái)?shù)組
    // for (int i = 0; i < size; i++) {
    //     array[i] = head->data;
    //     head     = head->next;
    // }

    // 3+4. 當(dāng)然也可以不合并鏈表，直接把數(shù)據(jù)返回?cái)?shù)組
    int index = 0;
    for (int i = 0; i < num; i++) {
        if ((*(buckets + i))->next != NULL) {
            BN* temp = (*(buckets + i))->next;
            while (temp != NULL) {
                array[index++] = temp->data;
                temp           = temp->next;
            }
        }
    }
}

int main()
{
    // 測(cè)試用例
    // int array[]    = {49, 38, 65, 97, 76, 13, 27, 49, 10};
    // int array_size = sizeof(array) / sizeof(array[0]);
    // int bucket_num = 5;
    // printf("%d \n", array_size);
    // printf("排序前數(shù)組：");
    // display(array, array_size);
    // bucket_sort(array, array_size, bucket_num);
    // printf("排序后數(shù)組：");
    // display(array, array_size);

    // 隨機(jī)測(cè)試
    int bucket_num = 5;              // 桶的個(gè)數(shù)
    int array_num  = 20;             // 數(shù)組數(shù)量
    int array_size = 20;             // 數(shù)組大小
    int array[array_size];           // 數(shù)組初始化
    srand((unsigned int)time(NULL)); // 隨機(jī)數(shù)種子，保證每次不一樣
    for (int i = 0; i < array_num; i++) {
        for (int j = 0; j < array_size; j++) {
            array[j] = rand() % 1000; // 隨機(jī)生成數(shù)大小 0~999
        }
        printf("原來(lái)的數(shù)組：");
        display(array, array_size);
        bucket_sort(array, array_size, bucket_num);
        printf("排序后數(shù)組：");
        display(array, array_size);
        // 檢測(cè)排序結(jié)果
        if (check(array, array_size) != 0) {
            exit(-1);
        }
        printf("\n");
    }

    return 0;
}

/***************************************************************************
 * @date    2020/12/03
 * @brief   輸出線性表
 * @param   L   首節(jié)點(diǎn)
 ***************************************************************************/
void displayL(BN* L)
{
    BN* p = L;                  // p 指向首結(jié)點(diǎn)
    while (p != NULL) {         // 不為空，依次遍歷
        printf("%d ", p->data); // 打印
        p = p->next;            // p 移向下一個(gè)節(jié)點(diǎn)
    }
    printf("\n");
}

/***************************************************************************
 * @date    2020/12/03
 * @brief   輸出數(shù)組
 * @param   array   數(shù)組
 * @param   size    數(shù)組大小
 ***************************************************************************/
void display(int* array, int size)
{
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

/**
 * @brief 檢查函數(shù)，從小到大
 *
 * @param array        數(shù)組首指針
 * @param size         數(shù)組大小
 */
int check(int* array, int size)
{
    for (int i = 0; i < size - 1; i++) {
        if (array[i] > array[i + 1]) {
            printf("sort array fail...\n");
            return -1;
        }
    }
    printf("sort array success...\n");
    return 0;
}