简化版桶排序

2016-11-30 11:15:19来源:CSDN作者:tzshlyt人点击

简化版桶排序

思路:

定义一个数组(桶),大小为待排序的最大数字加1,每个桶里初始化为0,遍历待排序的数组,取出每个数字,在对应桶上加一,如数字是3,就在桶[3]上加一,最后遍历全部桶,依次取出数字,即排好序。

代码:

#include <stdio.h>int main() {    int a[11], i, j, t;    int b[9] = {2, 4, 5, 6, 3, 4, 2, 9, 10};    for (i = 0; i < 10; i++) {        a[i] = 0;    }    for(i = 0; i < 9; i++) {        t = b[i];        a[t]++;    }    for (i = 0; i < 11; i++) {        for(j = 0; j < a[i]; j++){            printf("%d ", i);        }    }    return 0;}

时间复杂度

第6行执行m次,第10行执行n次,第15、16行执行m+n次,所以算法时间复杂度为O(2*(m+n)),即O(m+n),即O(M+N)。

问题

浪费空间,如果排序数范围是0~1000,则需要申请1001个变量;

不能排序小数。

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台