http://blog.csdn.net/qw_study/arc

基本思想：

定义一个带排序数中的最大数为DataForStore数组长度，一遍扫描带排序数组，将其值作为DataForStore数组中对应下标的数加1，随后在DataForStore数组中即是一排序号的数，顺序输出即可。

当然该算法有条件限制，如排序数中的最大数不能太大，至于DataForStore数组可以采用位存储方案，这里为了便于实验，即忽略空间要素。。。。。。

只是扫描一遍数组即完成排序，真正的O(N)复杂度



using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            BitMap bm = new BitMap(1000000, 10000);
            bm.CreateRandomData();//产生随机数
            bm.Sort();//排序
            bm.PrintDataAfterSort();//输出
            Console.ReadLine();
        }
    }
    class BitMap
    {
        public int DateLenth;
        public int MaxNumber;
        public int[] DataForStore;
        public int[] DataForSort;
        /// <summary>
        ///
        /// </summary>
        /// <param name="datelenth">带排序个数</param>
        /// <param name="maxnumber">带排序最大数</param>
        public BitMap(int datelenth, int maxnumber)
        {
            DateLenth = datelenth;
            MaxNumber = maxnumber;
            DataForStore = new int[maxnumber];
        }
        /// <summary>
        /// 产生随机数，便于测试
        /// </summary>
        public void  CreateRandomData()
        {
            Random r = new Random();
            DataForSort = new int[DateLenth];            
            for (int i = 0; i < DateLenth; i++)
            {
                DataForSort[i] = r.Next(MaxNumber);
            }
        }
        /// <summary>
        /// 排序
        /// </summary>
        public void Sort()
        {
            for (int i = 0; i < DateLenth; i++)
            {
                DataForStore[DataForSort[i]]++;
            }
        }
        /// <summary>
        /// 输出排序后的数据
        /// </summary>
        public void PrintDataAfterSort()
        {
            for (int i = 0; i < MaxNumber; i++)
            {
                for (int j = 0; j < DataForStore[i]; j++)
                {
                    Console.Write(i+",");
                }
            }
        }
    }
}