算法笔记(六):计数排序和基数排序

(一)说明

        这里我是按自己的理解去实现的,时间复杂度和空间复杂度和算法导论上的可能不一样,感兴趣的话参考下就行,感觉最重要的还是算法思想。根据算法性能去实现算法以后再研究。

(二)计数排序

    计数排序的基本思想是:对每一个输人元素x,确定小于x 的元素个数。 利用这一信息,就 可以直接把x放到它在输出数组中的位置上了。 例如,如果有17个元素小于x,则x就应该在第18个输出位置上。 当有几个元素相同时,这一方案要略做修改。 因为不能把它们放在同一个输出位置上。

     从这段话我们可以得出,我们要处理的事情其实就2个:

     1、获取小于x的元素的个数k,然后将x放到k+1的位置上(当然,因为python列表的索引是从0开始的,所以代码就没必要+1了,直接放到索引k上就行了(就比如:有4个元素小于X,那么此时A[4] = X就行了,因为A[0] A[1]  A[2] A[3]))

     2、处理相同元素的情况。

实现代码:

 1 #计数排序
 2 def conutingSort(A):
 3     B = [0 for i in range(len(A))] #初始化输出序列
 4     #2个for循环获取小于X的元素的个数,5-9行
 5     for i in range(len(A)):
 6         k = 0
 7         for j in range(len(A)):
 8             if A[i] > A[j]:
 9                 k += 1
10         #这个IF else,处理同名元素的情况,B.count(A[i])返回A[i]元素出现的个数
11         if A[i] in B:
12             B[k + B.count(A[i])] = A[i]
13         else:
14             B[k] = A[i]
15     return B
16 
17 A = [5,2,4,7,1,3,2,6,-1,-6]
18 
19 print(conutingSort(A))

(三)基数排序

感觉这种方式单独对正整数进行排序还好,如果考虑负数和小数的问题,问题有点复杂,甚至于可能要借用其他排序算法去处理。看算法导论上面的意思好像也是针对正整数的排序算法,感觉写这本书的大牛文笔好像不太好,没有深入浅出的感觉,或者是翻译的文笔不行。

      基数排序,我个人的理解是,例如:对列表A = [720,328,278,356,789,234,123]进行排序

      1、先按个位数进行排序 ,得到结果[720,123,234,356,328,278,789]

      2、在第一步的基础上,按十位数进行排序,得到结果[720,123,234,328,356,278,789]

      3、在第二步的基础上,按百位数进行排序,得到结果[123,234,278,328,356,720,789]

     这样,有多少位数,就执行多少轮。最重要的是:每一轮结束时,一定要更新列表,然后下一轮排序是在这个的基础上进行的

   实现代码:

   **就是幂,例如x**y  就是 x的y次幂

   % 返回除法的余数

    [a for b in s for a in b] 这个是2重的列表生成式,不了解列表生成式的可以单独去了解下

 1 #基数排序
 2 def radixSort(A, d): # 最大位数是几,d就填几
 3     for i in range(d):  # d轮排序
 4         s = [[] for k in range(10)]
 5         for j in A:
 6             s[int(j / (10 ** i)) % 10].append(j)
 7         A = [a for b in s for a in b] #更新列表A
 8         print(A)
 9     return A
10 
11 A = [720,328,278,356,789,234,123,113,113,999,789,9999,8999]
12 
13 print(radixSort(A,4))

可以看到,前面4个就是每一轮排序后的结果

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习思考者

Python学习(三) 八大排序算法的实现(上)

   本文Python实现了直接插入排序、基数排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、希尔排序。    上篇来介绍前四种排序方式:  ...

1928
来自专栏编程

八大排序算法的 Python 实现!

今天CoCo酱给大家介绍一下关于八大排序算法的Python实现,对八大排序算法进行详细描述和代码实现,下面我们一起来看一下吧。 1、插入排序 描述: 插入排序的...

2217
来自专栏小詹同学

LeetCode 系列——双指针问题 。

关于 LeetCode 系列有段时间没有逐题更新了 ,还是想到一题一题的刷有些凌乱 。如前段时间的推文所说 ,准备系统的讲讲数据结构相关知识点 。

1942
来自专栏令仔很忙

新手学JAVA(六)----处理随机性的数据

在我们的日常生活中会遇到很多随机性的事情,比如:摇奖,彩票,掷色子,这些都可以通过程序计算其中奖的概率。在JAVA的类库中,有一个专门操作这种随机性数据的类—-...

1092
来自专栏恰童鞋骚年

剑指Offer面试题:16.合并两个排序的链表

PS:这也是一道出镜率极高的面试题,我相信很多童鞋都会很眼熟,就像于千万人之中遇见不期而遇的人,没有别的话可说,唯有轻轻地问一声:“哦,原来你也在这里? ”

581
来自专栏Java爬坑系列

C++指针类型识别正确姿势

  指针是C和C++中编程最复杂也是最有技巧的部分,但对于新手来说,指针无疑是最致命的,让很多人望而退步。不过很多事情都是从陌生开始,然后渐渐熟悉起来的,就像交...

1847
来自专栏程序猿DD

第五章 正则表达式的拆分【修订】

本篇文章本不该存在,因小编的失误出现了一些错误,应作者要求,修正昨天同名文章的两处错误。 第五章 正则表达式的拆分 对于一门语言的掌握程度怎么样,可以有两个角度...

1996
来自专栏Danny的专栏

【J2SE快速进阶】——递归算法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

951
来自专栏从流域到海域

《Java程序设计基础》 第6章手记

本章主要内容: - 类的定义 - 成员变量和成员方法 - 类及成员的修饰符 - 对象的创建与使用 - 成员变量的访问与方法的...

2085
来自专栏来自地球男人的部落格

[LeetCode] 152. Maximum Product Subarray

【原题】 Find the contiguous subarray within an array (containing at least one nu...

2195

扫码关注云+社区

领取腾讯云代金券