算排序算法的时空复杂度C语言

算法：计数排序

时间复杂度：O(n+k)，其中n为输入序列的元素个数，k为计数数组的大小。

空间复杂度：O(k)，其中k为计数数组的大小。

C语言代码：

void countingSort(int arr[], int n, int k) {
    int count[k+1];
    int output[n];
    memset(count, 0, sizeof(count));
    for(int i=0; i<n; i++) {
        count[arr[i]]++;
    }
    for(int i=1; i<=k; i++) {
        count[i] += count[i-1];
    }
    for(int i=n-1; i>=0; i--) {
        output[count[arr[i]]-1] = arr[i];
        count[arr[i]]--;
    }
    for(int i=0; i<n; i++) {
        arr[i] = output[i];
    }
}

其中，arr为待排序数组，n为数组的元素个数，k为数组元素的取值范围（假设所有元素的取值范围为[1,k]）。