不久前实现的各种排序思路和代码

最近实现的各种排序思路和代码
最近为了准备实习生面试，看了算法导论前面一部分的内容，还实现了一些常见的排序算法
现在稍微整理一下最近的工作，可能有些不足之处，实现的也是最简单的整形的操作，以后继续完善之。
首先是插入排序，插入排序的原理和我们打扑克一样，当你拿到一张新牌的时候，你会从后往前找，因为已经到手的部分是已经排序好的（如果你是高手乱序打牌请飘过）找到新牌可以插入的合适位置放入，然后继续拿牌。
代码如下

堆排序和快速排序都是原地排序，可以说这两个思想都太牛了，一般人很难想到的，我们站在巨人的肩膀上应该更加努力。。废话说多了，这两个都是渐进最优的比较排序算法。
那么还有更快的么，算法导论里给了几个，计数排序，基数排序，桶排序。
我仅仅实现了计数排序，但对三种排序都稍微做了了解。
计数排序就是用空间换时间，并不进行任何比较，就是对数字进行统计。然后根据统计结果直接放入新数组的指定位置，所以这个排序可以在O(N)的复杂度完成排序，但空间复杂度为O(N+M)N为数组长度，M为数值范围。需要指定一个数值的范围，开辟一个数组记录该数字出现的次数。上代码
const  int range=1000;void count_sort(int* a,int* b,int size)//计数排序，需要知道数据的范围range{int i;int count[ range+1 ];for( i=0;i<=range;++i ){count[i]=0;}for( i= 1 ;i <=size;++i ){count[a[i]]+=1;}for( i=1; i<=range;++i ){count[i]+=count[i-1];}for( i=1 ;i<=size;++i ){b[count[a[i]]]=a[i];count[a[i]]-=1;}}

其实很容易看出来，range就是这种排序的限制，Short类型都有2的16次方大。。这个数组得开多大啊。。所以这样看，计数排序的意义就是为基数排序服务。基数排序就是把要排的数字分割成1个一个的位数，比如138 就是1， 3， 8
                         241     2， 4， 1
                         163     1， 6， 3

就拿上面的数字为例，先对个位排序得到    
                                        2,4,1
                                        1,6,3
                                        1,3,8

然后对十位进行排序得到                  
                                        1,3,8
                                        2,4,1
                                        1,6,3

然后对百位进行排序                      
                                        1,3,8
                                        1,6,3
                                        2,4,1

这样结果就出来了，所有的数字就可以分解成range=10的从最低位到最高位的计数排序。
这样假设有d 位，那么完成的复杂度就是O(d*N) 比快排快吧。。
至于桶排序的思想其实类似，就是将数值按照一定范围进行划分，将某个范围内的数值放到一起（这里称为桶），然后对放在一起的进行排序，再从每一个桶中读出已经排序好的元素。

这些代码都是以升序为目的的，没有使用任何高级C++技术。 排序就到这里了，欢迎点评指正！