首页 / 算法 / Python归并排序实例
Python归并排序实例
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Python归并排序实例,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1961字,纯文字阅读大概需要3分钟。
内容图文
![Python归并排序实例](/upload/InfoBanner/zyjiaocheng/1147/653db769cdf04a289406b6bc9f54b5ed.jpg)
Python归并排序
测试代码如下↓
def guibing(list1):
n = len(list1)
print(list1)
if n == 1:
return list1
half = n // 2
left_res = guibing(list1[:half])
right_res = guibing(list1[half:])
return mergersort(left_res, right_res)
def mergersort(a, b):
c = []
llen = len(a)
rlen = len(b)
h = 0
j = 0
while j < llen and h < rlen:
if a[j] < b[h]:
c.append(a[j])
j += 1
else:
c.append(b[h])
h += 1
if j == len(a): # 这里不能简单比较a、b长度
for i in b[h:]:
c.append(i)
else:
for i in a[j:]:
c.append(i)
return c
if __name__ == ‘__main__‘:
list1 = [7, 9, 3, 4, 5, 8]
print(guibing(list1))
# print (list1)
F5运行程序,排序正常,注意这里不能再打印传入的list,因为返回的是新列表
Python快速排序算法实例分析
快速排序的时间复杂度是O(NlogN)
算法描述:
① 先从序列中取出一个数作为基准数
② 分区过程, 将比这个数大的数全部放到它的右边, 小于或等于它的数全部放到它的左边
③ 再对左右区间重复第二步, 直到各区间只有一个数
假设对 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 进行排序, 首先在这个序列中随便找一个基准数(用来参照), 比如选择 6 为基准数, 接下来把所有比基准数大的数放在6的右边, 比6小的数放在左边
原理分析:
① 选择最左边的数为基准数key
② 设立两个游标 low 和 high , 分别指向数组的最低位和最高位
③ 然后high先动, 如果high位上的数比key大, 则向前走, 如果high-1位上的数比key大, 继续向前走, 直到该位上的数<=key
④ 此时比较low位, 如果<=key, low向后走, 变为low+1, 依次类推, 直到该位上的数比key大
⑤ 交换high和low位上的数
⑥ 重复以上步骤, 直到low=high , 交换 key 和 high 位上的值
⑦ 最后进行递归操作
代码如下
#!/usr/bin/env python
# coding:utf-8
# 设置最低位和最高位
def quickSort(nums, low, high):
# 设置一个比较基准key
key = nums[low]
while low<high:
# 如果最高位的数 大于等于 key则向前走
while low<high and nums[high] >= key:
high -= 1
# 如果最低位的数 小于等于 key则向后走
while low<high and nums[low] <= key:
low += 1
# 交换值
nums[low], nums[high] = nums[high], nums[low]
#最后low=high, 此时交换key和high位上的值, 使小于key的值在key左边, 大的在key右边
nums[nums.index(key)], nums[low] = nums[low], nums[nums.index(key)]
# 返回最低位的位置
return low
# 进行重复操作
def interval(nums, low, high):
if low<high:
# 进行排序并得到最低位位置以循环操作
key_index = quickSort(nums, low, high)
interval(nums, low, key_index)
interval(nums, key_index+1, high)
nums = [64,3,9,2,4,7,0,12,45,]
interval(nums, 0, len(nums)-1)
print ("测试结果:")
print (nums)
#"""
#[0, 2, 3, 4, 7, 9, 12, 45, 64]
#"""
原文:https://www.cnblogs.com/WYlover/p/10729546.html
内容总结
以上是互联网集市为您收集整理的Python归并排序实例全部内容,希望文章能够帮你解决Python归并排序实例所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。