python笔试面试项目实战2020百练6归并排序快速排序

归并排序

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

图片.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 rightmark

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)