计数排序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int data[8] = {5,6,7,8,4,3,2,1};

void sort(int k)
{
    int *countarray = (int*)malloc((k+1)*4);
    if(!countarray)
    {
        printf("create countarray error\n");
        return ;
    }
    memset(countarray,0,(k+1)*4);
    int size = sizeof(data) / 4;
    int i = 0;
    while(i < size)
    {
        countarray[data[i]]++;
        i++;
    }

    int p = 0;
    while(p<(k+1))
    {
        countarray[p+1] = countarray[p+1] + countarray[p];
        p++;
    }

    int x = 0;
    int *sortdata = (int*)malloc((k+1)*4);
    if(!sortdata)
    {
        printf("create sortdata error\n");
        return ;
    }
    while(x<size)
    {
        int tmp;
        tmp = (--countarray[data[x]]);
        sortdata[tmp] = data[x];
        x++;
    }

    int j=0;
    for(;j<size;j++)
    {
        printf("%d\n",sortdata[j]);
    }

}

int main()
{
   sort(8);
   return 0;
}

时间复杂度O(n)