- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- int find_max(int array[], int len)
- {
- int i = 0;
- int max = array[0];
- for (i = 1; i < len; i++) {
- if (array[i] > max)
- max = array[i];
- }
- return max;
- }
- int find_min(int array[], int len)
- {
- int i = 0;
- int min = array[0];
- for (i = 1; i < len; i++) {
- if (array[i] < min)
- min = array[i];
- }
- return min;
- }
- void count_sort1(int array[], int sort[], int len)
- {
- int i, max;
- int *temp = NULL;
- max = find_max(array, len);
- temp = (int *)malloc((max + 1)* sizeof(int));
- if (temp == NULL) {
- return;
- }
- memset(temp, 0, sizeof(int) * (max + 1));
- for (i = 0; i < len; i++) {
- temp[array[i]]++;
- }
- for (i = 1; i <= max; i++) {
- temp[i] += temp[i-1];
- }
- for (i = (len - 1); i >= 0; i--) {
- sort[temp[array[i]]-1] = array[i];
- temp[array[i]]--;
- }
- }
- void count_sort(int array[], int len)
- {
- int i, j, max, count;
- int *temp = NULL;
- max = find_max(array, len);
- temp = (int *)malloc((max + 1)* sizeof(int));
- if (temp == NULL) {
- return;
- }
- memset(temp, 0, sizeof(int) * (max + 1));
- for (i = 0; i < len; i++) {
- temp[array[i]]++;
- }
- for (i = 1; i <= max; i++) {
- temp[i] += temp[i-1];
- }
- j = 0;
- count = 0;
- for (i = 0; i <= max; i++) {
- while (temp[i] > count) {
- temp[i]--;
- array[j++] = i;
- }
- count = j;
- }
- }
- void disp_array(char *disp, int array[], int length)
- {
- int i = 0;
- if (disp == NULL)
- return;
- printf("-------------%s----------------\\n", disp);
- for (i = 0; i < length; i++) {
- if (i > 0 && (i % 8 == 0))
- printf("\\n");
- printf("%4d ", array[i]);
- }
- printf("\\n");
- return;
- }
- int main()
- {
- int len = 0;
- int sort[1024];
- int array[] = {1000, 20, 1, 1, 1, 1, 1, 1, 1, 20, 39, 1099, 1, 1, 20, 30};
- //int array[] = {10, 5, 1, 1, 1};
- len = sizeof(array) / sizeof(array[0]);
- disp_array("count_sort before", array, len);
- //count_sort(array, len);
- count_sort1(array, sort, len);
- //disp_array("count_sort after", array, len);
- disp_array("count_sort after", sort, len);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/090520149476.html
来源: http://www.codesnippet.cn/detail/090520149476.html