今天贴出的算法是计数排序Counting Sort。在经过一番挣扎之前，我很纠结，今天这个算法在一些scenarios，并不是最优的算法。最坏情况和最好情况下，时间复杂度差距很大。
代码CountingSort.h：
#include <stdlib.h> namespace dksl
{
void Sort(int *numArray,int length)
{
int max=numArray[];
int *temp=new int[length];
for(int i=;i<length;i++)
{
temp[i]=;
if(max<numArray[i])
max=numArray[i];
}
int* C=new int[max+];
for(int i=;i<=max;i++)
C[i]=;
for(int i=;i<length;i++)
C[numArray[i]]=C[numArray[i]]+;
for(int i=;i<=max;i++)
C[i]=C[i]+C[i-];
for(int i=;i<length;i++)
{
temp[C[numArray[i]]-]=numArray[i];
C[numArray[i]]=C[numArray[i]]-;
}
for(int i=;i<length;i++)
numArray[i]=temp[i];
delete temp;
delete C;
}
}
测试：
// CountingSort.cpp : 定义控制台应用程序的入口点。
// #include "stdafx.h"
#include <iostream>
#include "CountingSort.h" using namespace std;
using namespace dksl;
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {, , , , , , , , , };
Sort(a,);
cout<<"The sorted array is:";
for(int i = ; i < ; i++)
cout<<a[i]<<" ";
cout<<endl;
system("PAUSE");
return ;
}
结果：