归并排序

现在，我们将注意⼒转向使⽤分治策略改进排序算法。要研究的第⼀个算法是归并排序 ，它是递归算法，每次将⼀个列表⼀分为⼆。如果列表为空或只有⼀个元素，那么从定义上来说它就是有序的（基本情况）。如果列表不⽌⼀个元素，就将列表⼀分为⼆，并对两部分都递归调⽤归并排序。当两部分都有序后，就进⾏归并 这⼀基本操作。归并是指将两个较⼩的有序列表归并为⼀个有序列表的过程。

图片.png

def mergeSort(items):    print("Splitting ",items)    if len(items)>1:        mid = len(items)//2        lefthalf = items[:mid]        righthalf = items[mid:]        mergeSort(lefthalf)        mergeSort(righthalf)        i = j = k = 0        while i<len(lefthalf) and j<len(righthalf):            if lefthalf[i]<righthalf[j]:                items[k]=lefthalf[i]                i=i+1            else:                items[k]=righthalf[j]                j=j+1            k=k+1        while i<len(lefthalf):            items[k]=lefthalf[i]            i=i+1            k=k+1        while j<len(righthalf):            items[k]=righthalf[j]            j=j+1            k=k+1    print("Merging ",items)items = [54,26,93,17,77,31,44,55,20]mergeSort(items)print(items)items = [21, 1, 26, 45, 29, 28, 2, 9, 16, 49, 39, 27, 43, 34, 46, 40] mergeSort(items)print(items)

参考资料

• 本文最新版本地址
• 本文涉及的python测试开发库 谢谢点赞！
• 本文相关海量书籍下载
• python工具书籍下载-持续更新
• 本文配套视频在线播放 下载

希尔排序

和归并排序⼀样，快速排序 也采⽤分治策略，但不使⽤额外的存储空间。不过，代价是列表可能不会被⼀分为⼆。出现这种情况时，算法的效率会有所下降。

快速排序算法⾸先选出⼀个基准值 。尽管有很多种选法，但为简单起⻅，本节选取列表中的第⼀个元素。基准值的作⽤是帮助切分列表。在最终的有序列表中，基准值的位置通常被称作分割点 ，算法在分割点切分列表，以进⾏对快速排序的⼦调⽤。

图片.png

图片.png

图片.png

def quickSort(alist):    quickSortHelper(alist,0,len(alist)-1)def quickSortHelper(alist,first,last):    if first<last:        splitpoint = partition(alist,first,last)        quickSortHelper(alist,first,splitpoint-1)        quickSortHelper(alist,splitpoint+1,last)def partition(alist,first,last):    pivotvalue = alist[first]    leftmark = first+1    rightmark = last    done = False    while not done:        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:            leftmark = leftmark + 1        while alist[rightmark] >= pivotvalue and rightmark >= leftmark:            rightmark = rightmark -1        if rightmark < leftmark:            done = True        else:            temp = alist[leftmark]            alist[leftmark] = alist[rightmark]            alist[rightmark] = temp    temp = alist[first]    alist[first] = alist[rightmark]    alist[rightmark] = temp    return rightmarkalist = [54,26,93,17,77,31,44,55,20]quickSort(alist)print(alist)

原著是一个有趣的人,若有侵权,请通知删除