@[TOC]计数排序
1.概述
计数排序：计数排序又称为鸽巢原理，是对哈希直接定制法变形应用，是一种稳定的算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法，当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序。
2.代码
#include<stdio.h> #include<stdlib.h> #include<string.h> void CountSort(int*a,int n) { int max=a[0],min=a[0]; int i=0; for(i=0;i<n;i++) { if(a[i]<min) min=a[i]; if(a[i]>max) max=a[i]; } int range=max-min+1; int *count=(int*)malloc(sizeof(int)*range); memset(count,0,sizeof(int)*range); for(i=0;i<n;i++) { count[a[i]-min]++; } int j=0; for(i=0;i<range;i++) { while(count[i]--) { a[j++]=i+min; } } free(count); } int main() { int arr[]={10,9,8,7,6,5,4,3,2,1}; int n=10; CountSort(arr,n); for(int i=0;i<n;i++) { printf("%d ",arr[i]); } return 0; }
