《啊哈！算法》簡單桶排序（Simple Bucket Sort）

首先想想如何簡單地排序？

假設我們有5個學生，分數分别是5, 3, 5, 2, 8，滿分10分。

由實際可知，分數範圍在[0,10]，閉區間範圍内。

首先申請一個一維數組int arr[11]， 是從[0, 10]。

這裡認為第i個元素代表得i分的人的數目。

比如i=0，arr[0]=3，那麼代表得0分的人有三個。

首先第一個人分數是5，那麼就arr[5]=arr[5]+1；

第二個人分數是3，那麼就arr[3]=arr[3]+1；

第三個人分數是5，那麼就arr[5]=arr[5]+1；

第四個人分數是2，那麼就arr[2]=arr[2]+1；

第五個人分數是8，那麼就arr[8]=arr[8]+1；

然後再依次輸出即可（或者置回對應的位置）。

a[2]為1表示2出現過一次，那麼就輸出一個2；

a[n]為m表示n出現過m次，那麼就輸出m個n；

C Code:

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define SAFE_FREE(p) {free(p);p=NULL;}

/************************************************
 * 函數名稱：print_array
 * 參數清單：.int *parray:一個int類型指針，指向一個數組首位址
 *           .int n：一個int類型變量，指明數組大小
 * 函數描述：輸出數組中每個元素
 * 傳回值  ：void
 * Author  ：test128
 * History ：//
 * *********************************************/
void print_array(int *parray, int n)
{
    int i;
    for (i=; i<n; i++)
    {
        printf("%d ", parray[i]);
    }
    printf("\n");
}

/**********************************************
 * 函數名稱：bucketSort
 * 參數清單：
 * int *parr：待排序數組起始位置
 * int n：有多少個元素
 * int buckets：有多少個桶（即最大的位置）
 * 函數描述：簡化版桶排序
 * Author  ：test128
 * History ：//
 * **********************************************/
void bucketSort(int *parr, int n, int buckets)
{
    int *res = (int *)malloc(sizeof(int) * (buckets + ));
    if (res == NULL)
    {
        return ;
    }

    memset(res, , sizeof(int) * (buckets + ));

    int i=;
    while (i<n)
    {
        res[parr[i]]++;
        i++;
    }

    int index = ;
    for (i=; i <= buckets; i++)
    {
        while (res[i]--)
        {
            parr[index++] = i;
        }
    }

    SAFE_FREE(res);
}

int main()
{
    int arr[] = {, , , , , , , , , , , , };

    printf("before sort:\n");
    print_array(arr, );

    bucketSort(arr, , );

    printf("after sort:\n");
    print_array(arr, );

    return ;
}
           

（注：我的代碼和原書中有些不一樣。）

輸出結果：

[test128@localhost sort]$ ./main
before sort:
             
after sort:
            
           

這樣排序的特點是，必須知道值得範圍，然後做一下映射，記錄在一個數組裡面。

我個人認為，很有點Hash。

剛剛是從小到大進行排序，從大到小進行排序隻需要修改一下周遊的順序即可。

/**********************************************
 * 函數名稱：bucketSort
 * 參數清單：
 * int *parr：待排序數組起始位置
 * int n：有多少個元素
 * int buckets：有多少個桶（即最大的位置）
 * 函數描述：簡化版桶排序
 * Author  ：test1280
 * History ：2017/04/18
 * **********************************************/
void bucketSort(int *parr, int n, int buckets)
{
    int *res = (int *)malloc(sizeof(int) * (buckets + ));
    if (res == NULL)
    {
        return ;
    }

    memset(res, , sizeof(int) * (buckets + ));

    int i=;
    while (i<n)
    {
        res[parr[i]]++;
        i++;
    }

    int index = ;
    for (i=buckets; i >=; i--)
    {
        while (res[i]--)
        {
            parr[index++] = i;
        }
    }

    SAFE_FREE(res);
}
           

輸出結果：

[test128@localhost sort]$ ./main
before sort:
             
after sort:
            
           

桶排序簡單易懂，但是存在一些問題：

1.如果隻有3個數需要排序，但是最大的和最小的相差20000，那麼就有很多的空間被浪費；

2.如果是小數，或者别的比較難以映射成整數的情形下，比較難處理。

文中也提到，真正的桶排序要比這個複雜一些，後續我看到再進行記錄整理。

注：此篇Blog為讀《啊哈！算法》筆記。