我的c++学习笔记(一)——计数排序

计数排序假设输入数据均为正整数，且范围已知（即最大值已知），其运行时间规模为O(n)。

原理简述：考虑输入集中数据互不相等的情况，（1）新建一个临时数组，其维度（元素数量）与输入集最大值一致，（2）对输入集中的数据进行扫描，以输入集中的元素值为索引，将临时数组的元素置1，（3）扫描临时数组，若数组某元素为1，则将其索引值填入目标数组
当输入集中的数据有重复时需要做少许修改
计数排序不是原地排序，但是对于重复的元素，排序完成后它能保持其相对秩序

注：本文主要考虑输入集中的数据有重复的情况，若已知输入集中数据互不相等，可以将临时数组改为位向量，具体解法见《编程珠玑I》第一章（这个我没有动手实践过）

第一次在这个上面插代码，注释前混用了tab和空格

根据上面分析的前提条件，将算法的接口设计为
count_Sort(srcBegin, srcEnd, dest, upperBound)
因为目标迭代器使用了operator[]，所以其必须是随机迭代器而不能使用std::back_insertor,这一点似乎很不科学

/**********************************************************************
 * 用模板实现计数排序
 * 输入: 前向迭代器begin, end,
 *      指示目标区间起始地址的迭代器（必须是随机迭代器）
 *      待排序集合的最大值
 *
 * 执行结果：将区间[begin, end)内的值按照"<"排序后置于以dest开始的区间中
 * 注意： 输入集合内的值必须属于区间[0, upBound);
 * 函数不检查参数合法性
 *
 * author: compass
 * date: 2009年 11月 12日 星期四 19:44:58 CST
 * Email: [e-mail]
 **********************************************************************/

#ifndef __COUNTSORT_H__
#define __COUNTSORT_H__

#include <iterator>

template<typename IterSrc, typename IterDest>
void count_Sort(const IterSrc &begin, const IterSrc &end, /*输入区间*/
        IterDest dest,                                    /* 目标区间 */

        /* 下面为待排序集合的最大值 */
        const typename std::iterator_traits<IterSrc>::value_type upBound)  
{
    typedef typename std::iterator_traits<IterSrc>::value_type _ValueType;

    if(begin == end)                /*处理空区间 */
        return;

    _ValueType countArray[upBound];

    /* 初始化数组 */
    std::fill( countArray, countArray+upBound, 0);

    /* 统计每个*iter出现的次数 */
    for(IterSrc iter=begin; iter != end; ++iter)
        countArray[*iter] += 1;

    /* countArray[i]存储小于或等于i的元素个数 */
    for(size_t i=1; i!=upBound; ++i)
        countArray[i] +=countArray[i-1];
    
    for(IterSrc iter=begin; iter != end; ++iter)
    {
        /* 考虑iter指向最小的元素且该元素不重复，则
         * countArray[*iter]为1，
         * 而我们需要使dest[0]为最小的元素，而不是dest[1],
         * 其他同理
         */
        dest[ countArray[(*iter)]-1 ] = *iter;
        countArray[(*iter)] -= 1;
    }

    return;
}

#endif        /*countSort.h */


上面的临时数组countArray不能在定义时初始化，因为编译时其大小是不可知的

在我的第一个版本的最后一个for循环中，dest的索引表达式没有减1，导致内存非法方位，而我又不习惯用gdb调试，于是添加std::cout，然后该死的是添加的调试代码中竟然犯了一个相当低级的错误：数组索引从1开始，花了两个小时才把调试代码中的这个bug揪出来，当然顺便把原本存在的问题也解决了。
不知道上面代码还有没有其他的错误，欢迎批评指正（包括编程风格，stl使用等）

我的测试代码：

/**********************************************************************
 * 本程序用于对整数排序，调用计数排序
 * 从stdin读入数据，将排序好的数据输出到stdout，每行输出20个数
 * 读入数据为区间[0, 100)范围内的整数
 * date: 2009年 10月 11日 星期日 16:24:48 CST
 * 作者：compass
 * Email: [e-mail]
 **********************************************************************/
#include "countSort.h"
#include <iomanip>
#include <iostream>
#include <cstdlib> //for EXIT_SUCCESS
#include <iterator> //for iterators in fuction copy()
#include <algorithm> //for copy()
#include <vector>

int main(int argc, char* arg[])
{
    std::vector<int> iVecSrc;

    std::istream_iterator<int> eof;
    std::istream_iterator<int> inIter(std::cin);
    copy(inIter, eof, // the source
            std::back_inserter(iVecSrc) ); // the destination


    //保证目标容器有足够的容积
    //因为count_Sort()中对目标迭代器使用的赋值而不是插入，
    //所以这里不能用 iVecDest.reserve();
    std::vector<int> iVecDest(iVecSrc);


    //调用排序算法
    count_Sort(iVecSrc.begin(), iVecSrc.end(),
         iVecDest.begin(), //目标区间迭代器必须是随机迭代器

          100);
       
    //输出
    int n=1;
    for(std::vector<int>::const_iterator iter=iVecDest.begin();
            iter != iVecDest.end();
            ++iter, ++n)
    {
        std::cout.setf(std::ios::right);
        std::cout << std::setw(10) << *iter << " ";
        if(10 == n)
        {
            std::cout<<std::endl;
            n=0;
        }
    }

    std::cout << std::endl;
    return EXIT_SUCCESS;
}

参考资料：《算法导论》第8章