排序算法之归并排序的python实现
2024-09-05 14:37:06
采用分治法:
分割:递归地把当前序列平均分割成两半。
集成:在保持元素顺序的同时将上一步得到的子序列集成到一起(归并)。
归并操作(归并算法),指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
递归法(Top-down)
1.申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
2.设定两个指针,最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
4.重复步骤3直到某一指针到达序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾
迭代法(Bottom-up)
原理如下(假设序列共有 n个元素):
1.将序列每相邻两个数字进行归并操作,形成 c e i l ( n / 2 ) 个序列,排序后每个序列包含两/一个元素
2.若此时序列数不是1个则将上述序列再次归并,形成 c e i l ( n / 4 )个序列,每个序列包含四/三个元素
3.重复步骤2,直到所有元素排序完毕,即序列数为1
下面为快速排序的代码实现:
def merge_sort(lst):
if len(lst) <= 1:
# 当列表元素只有一个的时候,直接返回
return lst
mid = len(lst) // 2
left = lst[:mid]
right = lst[mid:] left = merge_sort(left)
right = merge_sort(right)
# 递归的进行排序
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
if left:
result += left
if right:
result += right
return result
# 返回排序后的结果 if __name__ == "__main__":
li = [9, 4, 2, 3.6, -1, 0, 25, -34, 8, 9, 1, 0]
print("排序前的队列:",li)
print("排序后的队列:", merge_sort(li))
最新文章
- 【noip】noip201503求和(市赛后公布)
- MySQL开启general_log跟踪sql执行记录
- Effective Java 读书笔记之九 并发
- linux:问题
- AsyncTask不能同时运行多个实例解决办法
- 查看Linux版本系统信息方法汇总
- Filter过滤器实现同一地址手机和电脑页面不同
- vs2010 条件断点 has changed是什么意思?
- js 调用父窗口的方法
- 在android里用ExpandableListView实现二层和三层列表
- Oracle存储过程中如何使用游标
- SVG裁切和蒙版
- GCD之信号量机制二
- react-native 引入某些低三方库时出现的Command `run-android` unrecognized,命令不识别错误
- 实现promise
- iBtais 多重嵌套循环
- 关于eclipse的indigo版中文注释时字体太小的问题(转)
- Android 应用程序之间内容分享详解(一)
- 乐视mysql面试题【转】
- redis 客户端命令