计数排序、基数排序、桶排序 非比较排序算法，平均时间复杂度都是O(N).
这些排序元素，因为其关键值本身就含有了定位特征，因而不需要比较就可以确定其前后位置。
1、计数排序是一种简单的排序方法，将排序结果放到另一个的新的数组中。
计数排序要求 待排序的元素的关键值是位于0-k之间的正整数。因而是个非常特殊的情况。
输入数组A：元素关键值是 0-K的正整数，可以有重复值
输出数组B：输出数组A的一个非减序列
中间数组C：大小K，它的i(0<=i<=k)索引位置存储的是A元素集合和。
这里意思是：原始数组A元素变成了中间数组C下标。
void Sort(int array[],int n,int outArray[],int k) //默认 区间是0——K
{
int* Temp=new int[k+1];
memset(Temp,0,(k+1)*sizeof(int));
for(int i=0;i<n;i++)
Temp[array[i]]++;
int m=0;
for (int i=0;i<=k;i++)
{
while(Temp[i]-->0)//如果有重复的话要递减
outArray[m++]=i; //array[m++]也是可以的 这里是标准计数排序的优化 可以使outArray 省去
}
delete[] Temp;
}
第一次我以为这就是计数排序，但后来发现 这个算法虽然可以解决有限区间的排序问题。但不是标准的(算法导论上)计数排序。
这个算法严格的来说并非排序算法，像统计(引用别人的描述)。所以也就不是什么稳定排序与非稳定排序，因为排序后的数组中的数已尽被全新的数替代。 已尽改变以前的数组中元素。
引用:维基百科计数排序
当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。
由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。
算法的步骤如下：
- 找出待排序的数组中最大和最小的元素
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
void BookSort(int array[],int outarray[],int n,int k) { //标准排序 int* Temp=new int[k+1]; memset(Temp,0,(k+1)*sizeof(int)); for(int i=0;i<n;i++) Temp[array[i]]++; for (int i=1;i<=k;++i) { Temp[i]=Temp[i]+Temp[i-1]; } //for (int i=n-1;i>=0;--i) //从后往前遍历原始数组 是稳定排序 for (int i=0;i<n;++i) //从前往后遍历原始数组 就不再是稳定排序 { //计数排序核心思想 int m=array[i];//原始数组元素关键字的值 int q=Temp[m];//根据原始数组元素关键字的值 对应于临时数组的下标 找到临时数组的值 outarray[ q- 1] = array[i];//临时数组的值 即是原始数组原始关键字的 排序位置 Temp[m] =Temp[m]-1;//因为有重复的数 排序的位置需要减去一个 } }
代码测试:
int N=20; int array[]={0,0,8,9,6,9,4,0,6,0,0,5,65,76,77,8,79,98,89,96}; int* outArray=new int[N]; Sort(array,N,outArray,100); //BookSort(array,outArray,N,100); for (int i=0;i<N;++i) { cout<<outArray[i]<<" "; } system("PAUSE"); return EXIT_SUCCESS;
总结:
计数排序要求规则太多，内存要求很大。接下来我会将其它线性排序算法写一写。然后直接做比较以及和其他非线性排序之间的比较。
文中肯定存在错误，请您如果发现任何有疑问的地方给我信息。谢谢...
PS：C++ 知识点
初始化中间数组C 运用 C++ 函数 void *memset(void *s,int c,size_tn) memset是对字节进行操作
char a[5]; memset(a,'1',5); 可以全部初始化为'1'
int a[5]; memset(a,0,5); 并不能全部初始化为0 因为是按字节进行初始化的 所以应该 memset(a,0,5*sizeof(int));
指针的大小是问：一个指针变量占用多少内存空间？分析：既然指针只是要存储另一个变量的地址，。注意，是存放一变量的地址，而不是存放一个变量本身，所以，不管指针指向什么类型的变量，它的大小总是固定的：只要能放得下一个地址就行！32位系统存放一个地址需要几个字节？答案是和一个 int 类型的大小相同：4字节。
指向数组的指针: int arr[] = {1,2,3,4,5}; //一个数组
int* parr; //一个指针。parr = arr; //没有‘&’？对啊，对数组就是不用取址符。
cout << *parr << endl; //输出 *parr 正确答案是输出数组中的第一个元素： 1 。
重点 & 易错点：对指针 进行加1操作，得到的是下一个元素的地址，而不是原有地址值直接加1。知到了如何“加”，也就知道了如何“减”。减以后，得到的是上一个元素的大小。所以，一个类型为 T 的指针的移动，以 sizeof(T) 为移动单位。int* pInt; 移动单位为 sizeof(int) 。即：4。而 char* pChar; 移动单位为 sizeof(char)。即1。
后置 ++ 或 后置-- 操作，需要系统生成一个临时变量。
当 * （作为地址解析符）和 ++ 同时作用在指针时，不管是前置还是++，都要比*有更高的优先级。
指针和数组是不一样的，但数组做为参数传递时就会退化为同类型的指针.
有2个原则：对数组sizeof是数组的大小；对指针sizeof是指针的大小（4）；