数据结构笔记(十六)排序算法之桶排序

发布于 / 程序猿 / 2 条评论

桶排序(英文:Bucket sort)或所谓的箱排序,是一个分布式的排序,工作的原理是将数组分到有限数量的桶里每个桶再进行排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。

基础知识

桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间O(n)。但桶排序并不是比较排序,他不受到O(n*logn)下限的影响。

排序过程

  • 设置一个定量的数组当作空桶子
  • 遍历序列,把元素一个一个放到对应的桶子去
  • 对每个不是空的桶子进行排序
  • 从不是空的桶子里把元素再放回原来的序列中

图文演示

对序列22, 45, 12, 8, 10, 6, 72, 81, 33, 18, 50, 14进行桶排序。序列长度N = 12,最大值max = 81,最小是min = 6,桶子数量bucket = 10

  • 选择除数divide = ceil((max+1)/bucket) = 9

  • 将序列元素放入相应的桶中

  • 对每个桶中元素进行排序

  • 将桶中元素以此取出,放入原序列

  • 动图演示

算法实现

#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
using namespace std;
const int maxn = 100000000;
const int Max = 30000;
int a[maxn];
int b[maxn];

void display(int a[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        cout << a[i] << "  ";
        if ((i+1) % 10 == 0)
            cout << endl;
    }
}

int B[1000][10010]; // 桶数为1000
int B_cnt[100010];

void bucket_sort(int a[], int n) // 桶排序
{
    memset(B_cnt, 0, sizeof(B_cnt));
    for (int i = 0; i < n; ++i) // 分配,除数为100
        B[a[i]/100][B_cnt[a[i]/100]++] = a[i];
    int k = 0;
    for (int i = 0; i < 100; ++i)
    {
        sort(B[i], B[i] + B_cnt[i]); // 对单个桶进行排序
        for (int j = 0; j < B_cnt[i]; ++j) // 回收
            a[k++] = B[i][j];
    }
}

void sort_sort(int a[], int n)
{
    sort(a, a + n);
}

void getTime(void f(int [], int), int a[], int n)
{
    clock_t _start, _end;
    _start = clock();
    f(a, n);
    _end = clock();
    cout << (double)(_end - _start) / CLOCKS_PER_SEC << endl;
}

int main()
{
    //srand((unsigned)time(NULL)); // 设置随机数种子
    for (int i = 0; i < maxn; ++i)
        a[i] = rand() % Max;
    copy(a, a+maxn, b);
    //display(a, maxn);
    getTime(bucket_sort, a, maxn);
    getTime(sort_sort, b, maxn);
    //display(a, maxn);
    return 0;
}

桶内进行排序使用的是C++ STL的sort,现在对直接使用sort排序和使用sort的桶排序进行比较。

对于30000以内的数
当 maxn = 10000     时:sort时间为 0.002s,桶排序为 0.001s。
当 maxn = 100000    时:sort时间为 0.019s,桶排序为 0.004s。
当 maxn = 1000000   时:sort时间为 0.225s,桶排序为 0.07s。
当 maxn = 10000000  时:sort时间为 2.343s,桶排序为 0.416s。
当 maxn = 100000000 时:sort时间为 27.177s,桶排序为 4.394s。

算法分析

  • 时间复杂度

最坏时间复杂度O(n^2)
平均时间复杂度O(n+k)

  • 稳定性

桶排序是稳定排序

  • 空间复杂度

桶排序的空间复杂度为O(n*k)

说明

文中基础知识和理论分析部分来源于维基百科桶排序,图文演示截图来源于YoutobeSorting Algorithm | Bucket Sort – step by step guide

推荐阅读:GeeksforGeeks | Bucket Sort

视频


The end.
2018-01-03 星期三

转载原创文章请注明,转载自: 太傅 » 数据结构笔记(十六)排序算法之桶排序
  1. Shawn

    零评论由我来打破不出所料

    1. TaiFu_S
      @Shawn

      优秀 赞一个