Go Through算法导论:桶排序

2016年02月28日 原创
关键词: C++ 数据结构 算法导论
摘要 本文介绍了什么是通排序以及如何用c++写一个通排序的程序。

通排序(bucket sort)假设输入数据服从均匀分布,平均情况下它的时间代价为O(n)。与计数排序类似,因为对输入数据作了某种假设,通排序的速度也很快。具体来说,计数排序假设输入数据都属于一个小区间内的整数,而桶排序则假设输入是由一个随机过程产生,该过程将元素均匀、独立地分布在[0,1)区间上。

通排序将[0,1]区间划分为n个相同大小的子区间,或称为桶。然后,将n个输入数分别放到各个桶中。因为输入数据是均匀、独立地分布在[0,1]区间上,所以一般不会出现很多数落在同一个桶中的情况。为了得到输出结果,我们先对每个桶中的数进行排序,然后遍历每个桶,按照次序把各个桶中的元素列出来即可。

在桶排序的代码中,我们假设输入是一个包含n个元素的数组A,且每个元素A[i]满足0≤A[i]≤1。此外,算法还需要一个临时数组B[0..n-1]来存放链表(即桶),并假设存在一种用于维护这些链表的机制。

下面是桶排序的伪代码:

BUCKET-SORT(A)

   n=A.length

   let B[0..n-1] be a new array

   for i = 0 to n-1

      make B[i] an empty list

   for i = 1 to n

      insert A[i] into list B[floor(nA[i])]

   for i = 0 to n-1

      sort list B[i] with insertion sort

   concatenate the lists B[0],B[1],...,B[n-1] together in order

下图显示了在一个包含10个元素的输入数组上的桶排序过程。

以下是桶排序的c++程序,其中运用了list自带的sort函数。

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;

void bucketsort(double* a, int n) {
    list<double>* b = new list<double>[n];
    for (int i = 0; i < n; i++) {
        b[int(a[i])].push_back(a[i]);
    }
    for (int i = 0; i < n; i++) {
        b[i].sort();
    }
    for (int i = 0,j=0; i < n; i++) {
        while (b[j].size() < 1)j++;
        a[i] = b[j].front();
        b[j].pop_front();
    }
}

int main() {
    double arr[] = {0.1,1.1,2.2,3.5,1.5,2.3,7.5,1.7};
    int n = 8;
    bucketsort(arr, n);
    for (int i = 0; i < 8; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

程序运行结果: