个人技术笔记

计数排序

发布时间：2015-11-26  栏目：软件算法  评论：0 Comments

基本思路为：

1.       我们希望能线性的时间复杂度排序，如果一个一个比较，显然是不实际的，书上也在决策树模型中论证了，比较排序的情况为nlogn的复杂度。

2.       既然不能一个一个比较，我们想到一个办法，就是如果我在排序的时候就知道他的位置，那不就是扫描一遍，把他放入他应该的位置不就可以了嘛。

3.       要知道他的位置，我们只需要知道有多少不大于他不就可以了吗？

4.       以此为出发点，我们怎么确定不大于他的个数呢？我们先来个约定，如果数组中的元素都比较集中，都在[0, max]范围内。我们开一个max的空间b数组，把b数组下标对应的元素和要排序的A数组下标对应起来。这样不就可以知道不比他大的有多少个了吗？我们只要把比他小的位置元素个数求和，就是不比他大的。例如：A={3,5,7};我们开一个大小为8的数组b，把a[0] = 3 放入b[3]中，使b[3] = 0; 同理 b[5] = 1; b[7] = 2;其他我们都设置为-1，哈哈我们只需要遍历一下b数组，如果他有数据，就来出来，铁定是当前最小的。如果要知道比a[2]小的数字有多少个，值只需要求出b[0] – b[6]的有数据的和就可以了。这个0(n)的速度不是盖得。

5.       思路就是这样咯。但是要注意两个数相同的情况A = {1,2,3,3,4}，这种情况就不可以咯，所以还是有点小技巧的。

6.       处理小技巧：我们不把A的元素大小与B的下标一一对应，而是在B数组对应处记录该元素大小的个数。这不久解决了吗。哈哈。例如A = {1,2,3,3,4}我们开大小为5的数组b;记录数组A中元素值为0的个数为b[0] = 0, 记录数组A中元素个数为1的b[1] = 1,同理b[2] = 1, b[3] = 2, b[4] = 1;好了，这样我们就知道比A[4](4)小的元素个数是多少了：count = b[0] + b[1] + b[2] + b[3] = 4;他就把A[4]的元素放在第4个位置。

 

#include
#include
#include

int max(int *A,size_t length);
void count_sort(int *A,int *B,size_t length,int k);

int main()
{
int datas[10] = {2,5,3,0,2,3,0,3,4,6};
int ret[10];
int i,k;
k = max(datas,10);
printf(“max value k = %d\n”,k);
count_sort(datas,ret,10,k);
printf(“After counting sort,the result is:\n”);
for(i=0;i<10;i++)
printf(“%d “,ret[i]);
printf(“\n”,ret[i]);
exit(0);
}

int max(int *A,size_t length)
{
int k = A[0];
int i;
for(i=1;i<length;++i) if(A[i] > k)
k = A[i];
return k;
}

void count_sort(int *A,int *B,size_t length,int k)
{
int i,j;
//each element in A between 0 and k [0,k],total k+1 elements
int *C = (int*)malloc(sizeof(int)*(k+1));

//init each element in C equal zero
memset(C,0,(k+1)*sizeof(int));
//times of each element in A
for(i=0;i<length;++i)
C[A[i]] = C[A[i]] + 1;

//nubmers of element which less and equal than sepcific position element in A
for(j=1;j<=k;++j)

C[j] = C[j] + C[j-1]; //Index from zero to length-1 in A and B

for(i=length-1;i>=0;i–)
{
B[C[A[i]]-1] = A[i]; //index is starting from zero
C[A[i]] = C[A[i]] – 1; //there might be repeating ones, minus 1 once
}
free(C);
}

 

空间复杂度为O(k+n), 适合k<n或者k比较小的情况.

留下评论

You must be logged in to post a comment.