python数据结构教程 Day9

本节重点

1. 归并排序
2. 快速排序

一、归并排序

算法思路：

应用分治策略，是一种递归算法，思路是将数据表持续分裂为两半，对两半分别进行归并排序。

• 递归的基本结束条件是：数据表仅有1个数据项 ，自然是排好序的；
• 缩小规模：将数据表分裂为相等的两半，规模减为原来的二分之一；
• 调用自身：将两半分别调用自身排序，然后将分别排好序的两半进行归并，得到排好序的数据表

实现1：

def mergeSort1(alist):
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        mergeSort1(lefthalf)
        mergeSort1(righthalf)

        i = j = k = 0
        while i<len(lefthalf) and j<len(righthalf): # 交错归并到结果列表
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i = i + 1
            else:
                alist[k] = lefthalf[j]
                j = j + 1
            k = k + 1
        
        while i < len(lefthalf): # 有一边已经没有元素了，归并左半部分剩余项
            alist[k] = lefthalf[i]
            i = i + 1
            k = k + 1

        while j < len(righthalf):
            alist[k] = righthalf[j]
            j = j + 1 
            k = k + 1

另一种更pythonic的实现：

def mergeSort2(alist):
    if len(alist)<1:
        return alist
    middle = len(alist) // 2
    left = mergeSort2(alist[:middle])
    right = mergeSort2(alist[middle:])

    merged = []
    while left and right:
        if left[0] <= right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))
    merged.extend(right if right else left)
    return merged

算法分析：

分裂的过程，借鉴二分查找中的分析结果，是对数复杂度，时间复杂度为O(log n)。

归并的过程，相对于分裂的每个部分，其所有数据项都会被比较和放置一次，所以是线性复杂度，其时间复杂度是O(n)。

综合考虑，每次分裂的部分都进行一次O(n)的数 据项归并，总的时间复杂度是O(nlog n)

最后，还是注意到两个切片操作为了时间复杂度分析精确起见，可以通过取消切片操作，改为传递两个分裂部分的起始点和终止点，也是没问题的，只是算法可读性稍微牺牲一点点。

归并排序算法使用了额外1倍的存储空间用于归并。这个特性在对特大数据集进行排序的时候要考虑进去。

二、快速排序

算法思路：

快速排序的思路是依据一个“中值”数据 项来把数据表分为两半：小于中值的一半和大于中值的一半，然后每部分分别进行快速排序（递归）。

如果希望这两半拥有相等数量的数据项，则应该找到数据表的“中位数” 但找中位数需要计算开销。要想没有开销，只能随意找一个数来充当“中值” 比如，第1个数或随机一个数或三点取样等。

快速排序的递归三要素：

基本结束条件：数据表仅有1个数据项， 自然是排好序的

缩小规模：根据“中值” ，将数据表分为 两半，最好情况是相等规模的两半

调用自身：将两半分别调用自身进行排序 （排序基本操作在分裂过程中）

算法流程：

设置左右标（left/rightmark）
左标向右移动，右标向左移动
• 左标一直向右移动，碰到比中值大的就停止
• 右标一直向左移动，碰到比中值小的就停止
• 然后把左右标所指的数据项交换
继续移动，直到左标移到右标的右侧，停止移动
这时右标所指位置就是“中值”应处的位置
将中值和这个位置交换
分裂完成，左半部比中值小，右半部比中值大

图示：

实现：

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 rightmark >= leftmark and alist[rightmark] >= pivotvalue:
            rightmark = rightmark + 1
        if rightmark > leftmark:
            done = True
        else:
            alist[leftmark],alist[rightmark] = alist[rightmark], alist[leftmark]
    # 退出循环后，中值就位
    alist[first],alist[rightmark] = alist[rightmark],alist[first]
    return rightmark # 返回中值点(分裂点)

算法分析：

快速排序过程分为两部分：分裂和移动。

• 分裂总能把数据表分为相等的两部分，那么就是O(log n)的复杂度。
• 而移动需要将每项都与中值进行比对，还是O(n)

综合起来就是O(nlogn)，且算法运行过程中不需要额外的存储空间。

注意：

选定中值的好坏直接影响快速排序的效率

如果不那么幸运的话，中值所在的分裂点过于偏离中部，造成左右两部分数量不平衡。极端情况，有一部分始终没有数据，这样时间复杂度就退化到O(n²)，还要加上递归调用的开销，比冒泡排序还糟糕。