|
|
邀请回答
马上注册,享受更多特权
您需要 登录 才可以下载或查看，没有帐号？立即注册 
x
本帖最后由 Lihoon 于 2020-3-17 20:15 编辑
归并排序通过不停的将数列分隔为两个较短的数列，直至每个数列的个数为1， 长度为1 的数列必然是有序数列；然后将两个有序数列合并成一个新的有序数列，依次递归，直至所有数列合并为1个数列。
生成随机数组的程序：random_list.py 请参考：
http://bbs.inovance.com/forum.php?mod=viewthread&tid=1925&extra=page%3D1
http://bbs.inovance.com/forum.php?mod=viewthread&tid=1896&extra=page%3D1
建立归并排序的程序：merge_sort.py
- #-*- coding:utf-8 -*-
- #Created Date: 2020/03/16
- from random_list import random_list
- import timeit
- import sys
- num = sys.argv[1]
- iList = random_list(int(num))
- def merge_sort(iList):
- '''建立拆分函数，将一个数列拆分成两个数列'''
- if len(iList) <= 1:
- return iList
- middle = len(iList)//2
- left, right = iList[0:middle], iList[middle:]
- """ 通过递归的方式，调用merge_sort()函数，将拆分后的数列继续不停的拆分，直到每个数列长度为1
- 然后调用merge_list()函数，将拆分的数列合并排序为1个数列
- """
- return merge_list(merge_sort(left), merge_sort(right))
-
- def merge_list(left, right):
- '''建立合并函数，将两个数列合并成一个数列'''
- mList = []
- while left and right:
- if left[0] >= right[0]:
- mList.append(right.pop(0))
- else:
- mList.append(left.pop(0))
- while left:
- mList.append(left.pop(0))
- while right:
- mList.append(right.pop(0))
- return mList
- if __name__ == "__main__":
- print("source list: {}".format(iList))
- print("sorted results: {}".format(merge_sort(iList)))
- print(timeit.timeit("merge_sort(iList)", "from __main__ import merge_sort, iList", number = 1000))
得到排序结果为：
- Input number is :10
- source list: [703, 936, 227, 427, 471, 74, 114, 797, 635, 329]
- sorted results: [74, 114, 227, 329, 427, 471, 635, 703, 797, 936]
- 0.0283238
|
上一篇： 【排序】快速排序法python实现下一篇： 【排序】计数排序法python实现
|
