排序算法-冒泡排序、选择排序、插入排序、希尔排序、快速排序
2023-03-20 14:49:27 时间
冒泡排序
思路:从列表第一个元素开始,相邻两个相比较,如果前者比后者大,则交换,使最大的最终交换到列表末尾。
alist = [3, 5, 2, 4, 1, 9] def bubbleSort(alist): for i in range(0, len(alist) - 1): for j in range(0, len(alist) - i - 1): if alist[j] > alist[j + 1]: alist[j], alist[j + 1] = alist[j + 1], alist[j] return alist ret=bubbleSort(alist) print(ret)
选择排序
思路:设置一个max_index,初始假定列表第一个元素为最大值(即max_index=0),然后依次与max_index下标对应的值比较,如果比max_index对应的值大,则将max_index值改为较大的数对应的索引。
alist = [3, 5, 2, 4, 1, 9] def choiceSort(alist): for i in range(0, len(alist) - 1): max_index = 0 for j in range(1, len(alist) - i): if alist[j] > alist[max_index]: max_index = j alist[len(alist) - 1 - i], alist[max_index] = alist[max_index], alist[len(alist) - 1 - i] return alist ret = choiceSort(alist) print(ret)
插入排序
思路:将列表分为左右两部分,前部分有序,后部分无序,后部分依次取值插入前部分,使之前部分始终有序,直到整个列表全部变为前半部分。
alist = [3, 5, 2, 4, 1, 9] def insertSort(alist): for i in range(1, len(alist)): while i > 0: if alist[i - 1] > alist[i]: alist[i - 1], alist[i] = alist[i], alist[i - 1] i -= 1 else: break return alist ret = insertSort(alist) print(ret)
希尔排序
思路:根据gap分组,组内排序,再改变gap,形成新组,再进行组内插入排序,直到gap=1,再进行一次插入排序。(gap=len(alist)//2 ; gap=gap//2)
alist = [3, 5, 2, 4, 1, 9] def shellSort(alist): gap = len(alist) // 2 while gap >= 1: for i in range(gap, len(alist)): while i > 0: if alist[i - gap] > alist[i]: alist[i - gap], alist[i] = alist[i], alist[i - gap] i -= gap else: break gap = gap // 2 return alist ret = shellSort(alist) print(ret)
快速排序
思路:以组的第一个为基准,列表最左端为low,最右端为high,先判断high对应的值和基准值比较,如果移动high值,则暂停移动high,开始移动low,直到low和high重合,然后将基准值放在重合位置。再对基准值左右两边两个列表进行递归操作,直到最后分得最小单位为一个元素,排序完成。
def sort(alist,start,end): low = start high = end #递归结束的条件 if low > high: return #基准:最左侧的数值 mid = alist[low] #low和high的关系只能是小于,当等于的时候就要填充mid了 while low < high:
# 向左偏移high while low < high: if alist[high] > mid: high -= 1 else: alist[low] = alist[high] break
# 向右偏移low while low < high: if alist[low] < mid: low += 1 else: alist[high] = alist[low] break #当low和high重复的时候,将mid填充 if low == high: alist[low] = mid #or alist[high] = mid break #执行左侧序列 sort(alist,start,high-1) #执行右侧序列 sort(alist,low+1,end) return alist
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十