计数排序假设n个输入元素中的每一个都是介于0到k之间的整数,此处k为某个整数。当k=O(n)时,计数排序的运行时间为O(n)。线性复杂度。计数排序不是比较排序算法。稳定算法。
算法思想:对每一个输入元素x,确定出小于x的元素个数。有这个信息后,就可以把x直接放到它在最终输出数组的位置上。
假定输入数组A[1..n],length[A]=n,则存放排序结果的数组B[1..n],临时存储区C[0..k]。
/********************************/ /**********计数排序**************/ /********************************/ void CountSort(ElemType a[],ElemType b[],int k,int n) { ElemType* c = (ElemType*)malloc(k*sizeof(ElemType)); for(int j = 0;j < k;j++) c[j] = 0; int i; for(i = 0;i < n;i ++) c[a[i]] = c[a[i]]+1;//C[i]包含等于i的个数 for(i = 1;i < k;i++) c[i] = c[i] + c[i-1];//C[i]包含小于或等于i的元素个数 for(i = n-1;i >= 0;i--) { b[c[a[i]]-1] = a[i]; c[a[i]]--; } }
#--------------# #--Count sort--# #--------------# def count_sort(arr,brr,k): arrlen = len(arr) crr = [] for i in range(0,k): crr.append(0) for j in range(0,arrlen): crr[arr[j]] = crr[arr[j]] + 1 for i in range(1,k): crr[i] = crr[i] + crr[i-1] for i in reversed(range(0,arrlen)): brr[crr[arr[i]]-1] = arr[i] crr[arr[i]] -= 1