归并排序 相对简单 归并的含义是将两个或两个以上有序表组合成一个新的有序表:
假设初始序列含有n个记录,则可看成是n个有序的子序列;每个子序列的长度为1,然后两两归并,得到 (n+1)/ 2 个子序列;再两两归并……如此重复,最终得到一个有序序列,这种叫做2路归并,如图所示:
代码实现:
def merge(list_a, list_b) :
key_a,key_b = 0, 0
result = []
len_a = len(list_a)
len_b = len(list_b)
while key_a < len_a and key_b < len_b :
if list_a[key_a] <= list_b[key_b] :
result.append(list_a[key_a])
key_a += 1
else :
result.append(list_b[key_b])
key_b += 1
while key_a < len_a :
result.append(list_a[key_a])
key_a += 1
while key_b < len_b :
result.append(list_b[key_b])
key_b += 1
return result
#loop
def merge_sort1(list) :
length = len(list)
result = []
step = 1
while(step <= (length+1)/2) :
result = []
for i in range(0,length,step * 2) :
max_key = i + 2*step
result.extend(merge(list[i:i+step],list[i+step:i+step*2]))
list = result
step += 1
return result
#recursion
def merge_sort2(list):
length = len(list)
if length == 1 :
return list
else :
temp_a = merge_sort2(list[0:length/2])
temp_b = merge_sort2(list[length/2:length])
return merge(temp_a,temp_b)
if __name__ == '__main__' :
list = [49,38,65,97,76,13,27]
print merge_sort1(list)
print merge_sort2(list)
其中 merge_sort1 采用循环的写法,merge_sort2 采用递归写法,与快速排序和堆排序相比,归并排序是一种稳定的排序方法
- 大小: 37.1 KB
分享到:
相关推荐
pyhton编写的归并排序是一种高效的快速排序算法,也是python本身内部的排序算法,它不仅时间复杂度小而且简单,符合分而治之的原则,也让很多程序员喜欢,大家快打开看看吧。
归并排序.py 使用python代码实现归并排序.py 使用python代码实现归并排序.py 使用python代码实现归并排序.py 使用python代码实现归并排序.py 使用python代码实现归并排序.py 使用python代码实现归并排序.py 使用...
python 归并排序算法 归并排序是一种基于分治思想的排序算法,它将待排序的序列分成若干个子序列,每个子序列都是有序的,然后再将这些有序的子序列合并成一个有序的序列。归并排序的时间复杂度为O(nlogn),是一种...
基于python的归并排序算法设计与实现
Python实现归并排序.rar
文件归并排序 命令行说明: sort.py -i <input_filename> -o <output_filename> [-d ] [-c ] [-s ] [-t ] -i 输入源文件名 -o 输出目标文件名,如果未指定,则结果覆盖到源文件 -d 可选项,文件文本行的列分隔符,...
归并排序是典型的分治法的应用 思想:先递归分解数组,再合并数组 原理:将数组分解最小之后,然后合并两个有序数组,基本思想是比较两个数组的最前面的数,谁小就取谁,取完后,将相应的指针后移以为。然后再比较,...
关于python的算法一直都是让我们又爱又恨,但是如果可以灵活运用起来,对我们的编写代码过程,可以大大提高效率,针对算法之一“归并排序”的灵活掌握,一起来看下吧~ 归并算法——小试牛刀 实例内容: 有 1 个无序...
详细描述请查看该文章:https://blog.csdn.net/qq_28531269/article/details/122415336?spm=1001.2014.3001.5502
Python 算法 16归并排序实现.mp4
Python 算法 15归并排序思想.mp4
归并排序
插入排序.py python实现的排序插入排序.py python实现的排序插入排序.py python实现的排序插入排序.py python实现的排序插入排序.py python实现的排序插入排序.py python实现的排序插入排序.py python实现的排序插入...
/usr/bin/python import sys def merge(array, q, p, r): left_array = array[q:p+1] right_array = array[p+1:r+1] left_array_num = len(left_array) right_array_num = len(right_array) i, j , k= [0, 0, q] ...
基于python的排序算法-归并排序Merge Sort
Python 算法 17归并排序_时间复杂度.mp4
第28周-第02章节-Python3.5-归并排序 希尔排序.mp4
本文实例讲述了Python实现的归并排序算法。分享给大家供大家参考,具体如下: 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 将已有序的子序列...
python八个常用排序(插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序)
主要为大家详细介绍了python编程实现归并排序的具体代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下