CountingSort(计数排序)原理及C++代码实现

0
16

计数排序是需要假设输入数据的排序之一,它假设输入元素是0到k区间内的一个整数,其中k为某个整数。当k=O(n)时,计数排序的时间复杂度为θ(n)。

因为不是通过比较来排序,所以它的时间复杂度可以达到θ(nlgn)以下。

计数排序是稳定的排序之一。

代码如下:(仅供参考)

//计数排序期望输入数据都是小区间内的整数
void CountingSort(int * const begin, int * const end) {
    vector<int> temp(10000); //假设输入值小于10000
    vector<int> out(end - begin);

    for (int i = 0; i < end - begin; ++i)
        ++temp[*(begin + i)];
    for (int i = 1; i < 10000; ++i)
        temp[i] += temp[i-1];
    for (int i = end - begin - 1; i >= 0; --i) {
        out[temp[*(begin + i)] - 1] = *(begin + i);
        --temp[*(begin + i)];
    }
    for (int i = 0; i < end - begin; ++i)
        *(begin + i) = out[i];
}

<

发布回复

请输入评论!
请输入你的名字