专栏首页python学习之旅算法笔记(九):希尔排序和桶排序

算法笔记(九):希尔排序和桶排序

(一)希尔排序

先将整个待排记录序列分割成若干个子序列,然后分别进行直接插入排序,待整个序列中的数据基本有序时,再对全体记录进行一次直接插入排序。具体做法是:

1)   算出增量序列

2)   根据增量序列对待排记录进行直接插入排序

 1 #希尔排序
 2 def shellSort(A):
 3     k = len(A)
 4     incremental = []
 5     #算出增量序列
 6     while (k > 1):
 7         k = k // 2
 8         incremental.append(k)
 9     dk = 0 #增量序列incremental的初始索引值
10     while(dk < len(incremental)):
11         #根据增量序列对列表进行插入排序
12         for i in range(0,len(A),incremental[dk]) :
13             key = A[i]
14             j = i - incremental[dk]
15             while j >= 0 and key < A[j]:
16                 A[j+incremental[dk]] = A[j]
17                 j -= incremental[dk]
18             A[j+incremental[dk]] = key
19         dk += 1
20     return A

(二)桶排序

 1 #桶排序
 2 def bucketSort(A):
 3     n = max(A)
 4     B = [0]* (n+1) #创建新的列表
 5     for i in A: #B[i] 的值+1
 6         B[i]  += 1
 7     A = [] #清空列表A
 8     #根据列表B,依次输出元素,添加到列表A中
 9     for i in range(len(B)):
10         if B[i] != 0 :
11             for k in range(B[i]):
12                 A.append(i)
13     return A
14 
15 
16 A = [1,12,720,328,278,356,789,234,123,113,113,9999,789,999,8999]
17 
18 print(bucketSort(A))

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python+Selenium笔记(十二):数据驱动测试

    (一)   前言 通过使用数据驱动测试,实现对输入值和预期结果的参数化。(例如:输入数据和预期结果可以直接读取Excel文档的数据) (二)   ddt 使用d...

    free赖权华
  • 算法学习笔记(五):快速排序和简单选择排序

    free赖权华
  • Python笔记(二):列表+列表数据处理+函数

    #才疏学浅,难免有不恰当之处,请不吝指正,谢谢。 #适合初学者。     列表的数据自下而上堆放(形成一个堆栈),类似于其他编程语言的数组。例如: user =...

    free赖权华
  • leetcode: 68. Text Justification [✗]

    Petrichor_
  • 小白课代表的使用说明(必读)

    课代表
  • 邂逅二次元爱豆 | 波洞星战设定

    ? 腾讯ISUX isux.tencent.com 社交用户体验设计 ? ? ? 导语 在ACG圈有着这样一种赛事:没有硝烟战火,没有(广义上的)明星参与...

    腾讯ISUX
  • 裸机安全谁负责?

    很多人希望硬件商品可以成为软件定义网络的支撑框架,但是裸机交换机中软件的安全该由谁负责呢?这是上周黑帽会议上探讨的安全问题之一。软件供应商需要硬件解决方案,而交...

    SDNLAB
  • 开灯就上网?万亿级LiFi产业尚在实验室阶段

    大数据文摘
  • Java单体应用 - 架构模式 - 03.设计模式-13.代理模式

    原文地址:http://www.work100.net/training/monolithic-architecture-design-patterns-pro...

    光束云
  • Android-Could not download kotlin-reflect.jar

    Could not download kotlin-reflect.jar (org.jetbrains.kotlin:kotlin-reflect:1.1.3...

    战神伽罗

扫码关注云+社区

领取腾讯云代金券