美文网首页
基数排序

基数排序

作者: _Cappuccino_ | 来源:发表于2019-08-23 17:18 被阅读0次

    综述

    基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位.
    有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序.最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前.

    算法描述

    1.取得数组中的最大数,并取得位数;
    2.arr为原始数组,从最低位开始取每个位组成radix数组;
    3.对radix进行计数排序(利用计数排序适用于小范围数的特点);

    示意图

    基数排序动态示意图 基数排序静态示意图

    性质

    排序类别:非交换排序
    是否是稳定排序:稳定
    是否是原地排序:否
    时间复杂度:O(n*k)
    空间复杂度:O(n+k)


    Python实现

    def radix_sort(s):
        i = 0  # 记录当前正在排拿一位,最低位为1
        max_num = max(s)  # 最大值
        j = len(str(max_num))  # 记录最大值的位数
        while i < j:
            bucket_list = [[] for _ in range(10)]  # 初始化桶数组
            for x in s:
                bucket_list[int(x / (10 ** i)) % 10].append(x)  # 找到位置放入桶数组
            print(bucket_list)
            s.clear()
            for x in bucket_list:  # 放回原序列
                for y in x:
                    s.append(y)
            i += 1
    
    
    a = [334, 5, 67, 345, 7, 345345, 99, 4, 23, 78, 45, 1, 3453, 23424]
    radix_sort(a)
    print('最后的结果是:', a)
    
    '''
    [[], [1], [], [23, 3453], [334, 4, 23424], [5, 345, 345345, 45], [], [67, 7], [78], [99]]
    [[1, 4, 5, 7], [], [23, 23424], [334], [345, 345345, 45], [3453], [67], [78], [], [99]]
    [[1, 4, 5, 7, 23, 45, 67, 78, 99], [], [], [334, 345, 345345], [23424, 3453], [], [], [], [], []]
    [[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345], [], [], [23424, 3453], [], [345345], [], [], [], []]
    [[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453], [], [23424], [], [345345], [], [], [], [], []]
    [[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424], [], [], [345345], [], [], [], [], [], []]
    最后的结果是: [1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424, 345345]
    '''
    

    C语言实现

    #include <stdio.h>
    #include <string.h>
    
    /* 获取输入数字的索引值,dec指定数字的位数,3代表百位数,order指定需要获取哪一位的索引,1代表个位,2代表十位,3代表百位 */
    int get_index(int num, int dec, int order)
    {
        int i, j, n;
        int index;
        int div;
    
        /* 根据位数,循环减去不需要的高位数字 */
        for (i=dec; i>order; i--) {
            n = 1;
            for (j=0; j<dec-1; j++)
                n *= 10;
            div = num/n;
            num -= div * n;
            dec--;
        }
    
        /* 获得对应位数的整数 */
        n = 1;
        for (i=0; i<order-1; i++)
            n *= 10;
    
        /* 获取index */
        index = num / n;
    
        return index;
    }
    
    /* 进行基数排序 */
    void radix_sort(int array[], int len, int dec, int order)
    {
        int i, j;
        int index;     /* 排序索引 */
        int tmp[len];  /* 临时数组,用来保存待排序的中间结果 */
        int num[10];   /* 保存索引值的数组 */
        memset(num, 0, 10*sizeof(int));  /* 数组初始清零 */
        memset(tmp, 0, len*sizeof(int)); /* 数组初始清零 */
    
        if (dec < order) /* 最高位排序完成后返回 */
            return;
    
        for (i=0; i<len; i++) {
            index = get_index(array[i], dec, order);  /* 获取索引值 */
            num[index]++;  /* 对应位加一 */
        }
    
        for (i=1; i<10; i++)
            num[i] += num[i-1]; /* 调整索引数组 */
    
        for (i=len-1; i>=0; i--) {
            index = get_index(array[i], dec, order);  /* 从数组尾开始依次获得各个数字的索引 */
            j = --num[index];  /* 根据索引计算该数字在按位排序之后在数组中的位置 */
            tmp[j] = array[i]; /* 数字放入临时数组 */
        }
    
        for (i=0; i<len; i++)
            array[i] = tmp[i];  /* 从临时数组复制到原数组 */
    
        printf("the %d time\n", order);
        for (i=0; i<30; i++)
            printf("%d  ", array[i]);
        printf("\n");
    
        /* 继续按高一位的数字大小进行排序 */
        radix_sort(array, len, dec, order+1);
    
        return;
    }
    
    int main(int argc, char *argv[])
    {
        int i;
        int array[30] = {258, 976, 515, 337, 359, 701, 916, 494, 303, 175,
                            677, 825, 131, 560, 147, 254, 759, 814, 917, 382,
                            452, 114, 873, 585, 881, 127, 819, 658, 461, 435};
    
        int len = 30;  /* 测试数据个数 */
        int dec = 3;   /* 数据位数,3代表3位数 */
        int order = 1; /* 排序的位数,1代表个位、2代表十位、3代表百位 */
    
        printf("before\n");
        for (i=0; i<30; i++)
            printf("%d  ", array[i]);
        printf("\n");
    
        /* 排序函数,从个位开始 */
        radix_sort(array, len, dec, order);
    
        printf("final\n");
        for (i=0; i<30; i++)
            printf("%d  ", array[i]);
        printf("\n");
    
        return 0;
    }
    
    /*
    before
    258  976  515  337  359  701  916  494  303  175  677  825  131  560  147  254  759  814  917  382  452  114  873  585  881  127  819  658  461  435
    the 1 time
    560  701  131  881  461  382  452  303  873  494  254  814  114  515  175  825  585  435  976  916  337  677  147  917  127  258  658  359  759  819
    the 2 time
    701  303  814  114  515  916  917  819  825  127  131  435  337  147  452  254  258  658  359  759  560  461  873  175  976  677  881  382  585  494
    the 3 time
    114  127  131  147  175  254  258  303  337  359  382  435  452  461  494  515  560  585  658  677  701  759  814  819  825  873  881  916  917  976
    final
    114  127  131  147  175  254  258  303  337  359  382  435  452  461  494  515  560  585  658  677  701  759  814  819  825  873  881  916  917  976
    */
    

    相关文章

      网友评论

          本文标题:基数排序

          本文链接:https://www.haomeiwen.com/subject/xvbtectx.html