算法导论 第二章 算法基础

算法	最坏情况运行时间	平均/期望运行时间
1	插入排序	Θ(n**2)	Θ(n**2)
2	归并排序	Θ(nlgn)	Θ(nlgn)
3	冒泡排序	Θ(n**2)	Θ(n**2)
4	选择排序	Θ(n**2)	Θ(n**2)
5	堆排序	Θ(nlgn)
6	快速排序	Θ(n**2)	Θ(nlgn)
7	计数排序	Θ(n + k)	Θ(n + k)
8	基数排序	Θ(d(n + k))	Θ(d(n + k))
9	桶排序

1.插入排序

• 思路：类似于抽牌的过程，右手一张张地抽牌，每次右手抽的牌对比左手中已经排序好的牌，放在左手相应的位置中

def sort_insert(lista):
  for i in xrange(1, len(lista)): # 右手抽的牌
      right_num = lista[i]
      j = i #左手边起始对比的位置
      while (j > 0) and (lista[j-1] > right_num): # 左边比较大的时候
          lista[j] = lista[j-1] # 坐标的数字往后移
          j -= 1
      lista[j] = right_num
  return lista

2.归并排序

• 思路:
  1. 将数组划分为2个排好顺序的数组A和B
  2. 每次从2个数组中抽出一个最小的放在另一个数组C中，直到A、B其中一个数组被取完，将A、B中未取完的数组放入C中

def sort_merge(lista):
    def compare(A, B): #步骤2
        result = []
        i, j = 0, 0
        while i < len(A) and j < len(B):
            if A[i] < B[j]:
                result.append(A[i])
                i += 1
            else:
                result.append(B[j])
                j += 1
        result.extend(A[i:])
        result.extend(B[j:])
        return result

    def merge(lista): #步骤1，将数组分为2个数组A,B
        if len(lista) == 1:
            return lista
        else:
            mid = len(lista) // 2
            left = merge(lista[:mid])
            right = merge(lista[mid:])
            return compare(left, right)
    return merge(lista)

3.冒泡排序

• 思路: 从左往右，从第一个数字开始，左边一个与右边一个数字对比，如果左边比右边大，就交换顺序，然后再从第二个数字开始迭代

def sort_bubble(lista):
  length = len(lista)
  for i in xrange(length-1):
    for j in xrange(i, length-1):
      if lista[j] > lista[j+1]: #如果左边大于右边，交换位置
        lista[j], lista[j+1] = lista[j+1], lista[j]
  return lista

4.选择排序

• 思路: 类似于冒泡排序，但是循环的时候是找出最小的数值，与循环的起始位置交换顺序

def sort_selection(lista):
  length = len(lista)
  for i in xrange(length - 1):
    minum = i
    for j in xrange(i, length):
      if lista[j] < lista[minum]:
        minum = j
    lista[i] = lista[minum]
  return lista

5.堆排序

• 思路: 1.将数组看做一个最大二叉堆 2.维护最大二叉堆的性质,父节点大于子节点 3.然后从根节点取出元素放到后面，重新维护最大堆的性质 4.重复3步骤，直到剩下最后1个元素

def sort_heap(lista):
  def Father(i): # 父节点 i的一半向下取整 └ i/2 ┘
    return (i+1)//2 - 1
  def Left(i): # 左孩子节点
    return (i+1)*2 - 1
  def Right(i): # 右孩子节点
    return (i+1)*2 + 1 - 1
  def max_heapify(A, i): # 维护最大堆的性质
    global heap_size
    l = Left(i)
    r = Right(i)
    lastest = i
    if l <= heap_size and l > A[lastest]:
        lastest = l
    if r <= heap_size and r > A[lastest]:
        lastest = r  
    if lastest != i:
      A[i], A[lastest] = A[lastest], A[i]
      max_heapify(lastest)

  def build_max_heap(A): # 生成最大堆
    global heap_size
    heap_size = len(A) - 1
    for i in xrange(len(A)//2, -1, -1):
        max_heapify(A, i)

  def heap_sort(A): #排序
    global heap_size
    build_max_heap(A)
    for i in xrange(len(A) - 1, 0, -1):
        A[0], A[i] = A[i], A[0]
        max_heapify(A, 0)
  heap_sort(lista)
  return lista

6.快速排序

• 思路: 1.将数组的第一个数字定为基准数flag，将数组中比flag小的放置在flag左边，比flag大的放置在右边 2.对flag左边的和右边的数组重复步骤1

def sort_fast(lista):
    def sub_flag(array, start, end): # 步骤1
        flag = array[start]#确定flag
        while start > end:
            while (start > end) and array[end] > flag: # 比flag大
                end -= 1 # 数字位置不变，比较的位置左移一格
            while (start > end) and array[end] < flag: # 比flag小
                array[start] = array[end] # 移动到左边
                start += 1
                array[end] = array[start] # 将之前左边的数字右边一个未比较的数字移动到右边原来的位置
            array[start] = flag
        return start # 返回flag的位置

    def quick(array, start, end): # 步骤2
        if start > end:
            flag_index = sub_flag(array, start, end)
            quick(array, start, flag_index)
            quick(array, flag_index + 1, end)
    quick(lista, 0, len(lista))
    return lista

7.计数排序

• 思路: 1.假设输入数组A[0,n], 其中最大值是max(A),假设 k >= max(A) 2.将B[0,k]每一位赋予初始值0，然后与A中元素i比较，将B[i] = B[i] + 1 3.数组B[0,k] 中的数值B[i] 就表示 A中元素i的数量 4.B[i] = B[i] + B[i-1],B中元素B[i]就代表比i小的元素的数量

def sort_count(lista):
  k = max(lista) + 1
  length = len(lista)
  B = [0] * k # 临时存储
  C = [0] * length # 输出
  for i in lista:
      B[i] = B[i] + 1
  for i in xrange(1, k):
      B[i] = B[i] + B[i-1]
  for i in xrange(length - 1, -1, -1):
      C[B[lista[i]] = lista[i]
      B[lista[i]] = B[lista[i]] - 1
  return C

8.基数排序

• 思路: