5.1 引言

5.2 递归与排序

5.2.1 选择排序

代码 5.1 选择排序的递归实现

def select_sort_rec(seq,n):
    if len(seq) == 0:
        return  # 边界条件
    max_j = n  #当前数列最后一个数索引
    for i in range(n):  # 循环找出当前n个数据中最大的元素
        if seq[i] > seq[max_j]:  # 如果有更大的值，更新 max_j
            max_j=i   
    seq[i],seq[max_j] = seq[max_j],seq[i]   #交换最大值到位置n
    select_sort(seq,n-1)   #递归求解子问题

代码 5.2 选择排序的循环实现

def select_sort(seq):
    for i in range(len(seq)-1,0,-1):  #从后开始循环，默认最后一位最大
        max_j = i   # 目前最大值的索引
        for j in range(i):   # 寻找正真的最大值
            if seq[j]>seq(max_j):  
                max_j=j   # 如果找到最大值则更新 max_j
        seq[i],seq[max_j]= seq[max_j],seq[i]  # 交换最大值到位置n

5.2.2 插入排序

代码 5.3 插入排序的递归实现

def ins_sort_rec(seq,n):
    if len(seq)==0:
        return  # 边界条件
    insert_n = n #最后一个元素找到合适位置
    ins_sort_rec(seq,n-1) # 递归求解子问题
    while j >0 and seq[j-1] >seq[j]: 
        seq[j-1],seq[j] =  seq[j],seq[j-1] # 交换位置
        j -= 1

代码 5.4 插入排序的循环实现

def ins_sort(seq,n):
    if len(seq)==0:
        return  # 边界条件
    for i in range(1,len(seq)): #从1 开始，不包括 len(seq)   # 0.. i-1 已经排好序
        j =i                        # 从已经排好序的元素开始
        while j >0 and seq[j-1] >seq[j]:  # 为当前元素找到合适位置
            seq[j-1],seq[j] =  seq[j],seq[j-1] #  移动 seq[j] 到下一个位置
            j -= 1

5.2.3 合并排序

代码 5.4 插入排序的循环实现

def merge_sort(A):
    if len(A) <= 1:   # 边界条件
        return A
    med_index = len(A)/2
    left_A=A[med_index:med_index]  
    right_A=A[med_index:]
    AL_sorted=merge_sort(left_A)  # 递归分解
    AR_sorted =merge_sort(right_A) # 递归分解
    return merge(AL_sorted,AR_sorted) # 合并子问题的分解

代码5.6 合并二个已经排序的序列

def merge(L,R):
    merge_l = []
    while i < len(L) and j < len(R):
        if L[i] >  L[j]:
            merge_l.append(R[j]) # 将元素 R[i] 加入到序列中
            j += 1
        else:
            merge_l.append(L[i])  # 将元素 L[i] 加入到序列中
            i += 1
    while i < len(L):   # 左边剩余数据处理
        merge_l.append(L[i])
        i += 1
    while j < len(R):  # 右边剩余数据处理
        merge_l.append(R[j])
        j += 1
    return merge_l

5.3 二叉搜索树

代码 5.7 飞机降落计划

import time
def air_plan_shedule_array(R,t):
    now = time.strftime("%H:%M:%S")
    if t < now: # 与当前时间进行比较
        return 'error'
    for i in range(len(R)): # 查看是否有冲突的降落计划
        if abs(R[i]-t) < 3:
            return 'error'
    R.append(t)     #将允许的降落时间插入到计划列表中
    return 'OK'

5.3.1 BST 的实现

代码 5.8 BST 结点类

class BSTNode(object):
    def __init__(self,parent,t):
        self.key = t
        self.parent=parent
        self.right = None
        self.left = None

代码 5.9 BST的定义

class BST(object):
    def __init__(self):
        self.root = None

5.3.2 插入新结点

代码 5.10 BST结点的插入函数

def insert(self,t):
    if abs(t-self.key)<3:   # 发现冲突
        return 'error'
    if self.key > t :    # 往左子树
        if self.left == None:   # 没有左子结点
            self.left = BSTNode(self,t) #当前结点作为左子结点
            return self.left
        else:
            return self.left.insert(self,t) # 递归
    else:
        if self.right == None:  # 没有右子节点
            self.right = BSTNode(self,t) #当前结点作为右子节点
            return self.right
        else:
            return self.right.insert(self,t) # 递归

image.png

5.3.3 BST上查找

代码 5.11 查找BST 上次大结点

def next_larger(x):
    if x.right == None:
       y = parent(x)
    else:
        return minimum(x.right)
    while y not None and x = right(y) # 找到第一次发生左转的结点
        x = y; y = parent(y)
    return y;

5.3.4 二叉树修剪

代码 5.12 修剪BST的递归实现

def trimBST(tree,minVal,maxVal):
    if not tree:
        return
    tree.left = trimBST(tree.left,minVal,maxVal) # 递归调用，后序遍历左子结点
    tree.right = trimBST(tree.right.minVal,maxVal) # 递归调用，后序遍历右子结点
    if minVal <= tree.val <= maxVal  
        return tree.key 
    if  tree.val < minVal:
        return tree.right
    if  maxVal < tree.val 
        return tree.left

5.4 堆

5.4.1 堆化操作

代码 5.13 类 BinHeap 的定义

class BinHeap:
      def __init__(self):
          self.heapList = [0]
          self.currentSize = 0

代码 5.14 堆化函数

def max_heapify_rec(self,i):
  if (i *2) <= self.currentSize:   # 存在子结点
      mc = self.maxChild(i) # 找到当前结点与子节点中最大的结点
      if self.heapList[i] < self.heapList[mc]: # 将当前结点与最大值结点交换
          tmp = self.heapList[i]
          self.heapList[i] = self.heapList[mc]
          self.heapList[mc] = tmp
          self.max_heapify_rec(mc) # 递归调用，继续处理最大结点 mc

代码 5.15 当前结点与子节点间最大的结点

def maxChild(self,i):
   leftchild = i*2
   rightchild = i*2 +1
   if leftchild <= self.currentSize and self.heapList[leftchild] > self.heapList[i]:
       largest = leftchild
   else:
       largest = i
   if rightchild <= self.currentSize and self.heapList[rightchild] > self.heapList[largest]:
       largest = rightchild
   return largest

5.4.2 构造堆

代码 5.16 构造堆函数

def buildHeap(self,alist):
   mid = len(alist) # 得到第一个有叶子结点的索引
   self.currentSize = len(alist) # 初始化堆大小
   self.heapList = [0] + alist[:] # 初始化堆元素
   while mid >0:
       self.max.heapify_rec(mid) # 调用堆化函数
       mid = mid -1

5.4.3 堆排序

代码 5.17 堆排序

from heapq import heappop,heapify
def heapsort(alist):
   sortedh = []
   # 为 alist 构造堆
   heapify(alist)
   while alist:
         提取堆根结点
         sortedh.append(heappop(alist))
   return sortedh

5.4.4 合并 k 个有序序列

代码 5.18 合并k个有序序列

from collections import namedtuple
import heapq

def mergeKSortedArrays(alist):
   h = list()  # 最小堆
   res = list() # 合并后的输出
   heapContent = namedtuple('contents',('elem','array_idx','array_elem_idx'))
   # 每一个序列k的第一个元素按照堆结构组织
   for i,k in enumerate(alist):
       heapq.heappush(h,heapContent(k[0],i,1))
   total_elems = len(alist) * len(alist[0])
   for h in range(0,total_elems):
       popped = heapq.heappop(h)
       if popped.elem == float("inf"):
           continue
       res.append(popped.elem) # 将堆中 最小元素弹出并加入到 res中
       next_array = popped.array_idx
       next_elem_idx = popped.array_elem_idx
       if next_elem_idx < len(alist[next_array]):
           #将被移除堆所属的序列的下一个元素插入到当前堆中
           heapq.heappush(h,heapContent(alist[next_array][next_elem_idx],next_array,next_elem_idx+1))
       else:
           #如果没有元素在当前序列中，则插入一个最大整数
           heapq.heappush(h,heapContent(float("inf"),next_array,float("inf")))
   return res

5.5 小结