基于非比较原则的一种排序 适用于大量重复而且密集的数据
---C语言实现
#include <stdio.h> #include <stdlib.h> #include <windows.h> //遍历数组 void LoopForArr(int arr[],int length) { int count; if(arr == NULL || length <=0)return ; for(count = 0;count<length;count++) { printf("%d ",arr[count]); } printf("\n"); } //计数排序 void CountingSort(int arr[],int length) { int Max; int Min; int count; int *TempArr = NULL; if(arr == NULL || length <=0)return ; //找到数组中最大值最小值 Max = Min = arr[0]; for(count = 0;count<length;count++) { Max = Max<arr[count]?arr[count]:Max; Min = Min>arr[count]?arr[count]:Min; } //申请临时数组 TempArr = (int *)malloc(sizeof(int)*(Max-Min)); memset(TempArr,0,sizeof(int)*(Max-Min)); for(count = 0;count<length;count++) { TempArr[arr[count]-Min]++; } //倒回原数组 for(count = 0,Min = 0;count<length;count++) { while(!TempArr[Min]) Min++; arr[count] = Min+1; TempArr[Min]--; } //释放空间 free(TempArr); TempArr = NULL; } int main() { int arr[] = {1,1,3,2,2,2,2,3,3,3,3,23,1,21,3,1,13,3,1,31,31,3,23,1}; CountingSort(arr,sizeof(arr)/sizeof(arr[0])); LoopForArr(arr,sizeof(arr)/sizeof(arr[0])); system("pause"); return 0; }
