mzh/blog

排序算法笔记

最近在上MIT的6.006算法课,重新温习了下排序算法,发现很多知识点以前并没有吃透,也没有记下来,所以这次还是写在这里了。知之为知之,不知为不知嘛。

Insertion sort

核心

取出元素比较并插入到之前已经排好序的数组中。

例子

  1. [3 5 2 1] # 取第二位5,比较第一3
  2. [3 5 2 1] # 5 比 3 大, 略过
  3. [3 5 2 1] # 取第三位2, 和第二位比较,2 比 5 小,2向前
  4. [3 2 5 1] # 继续比较2 和 3, 2 比 3小,2向前
  5. [2 3 5 1] # 1就重复上述步骤

代码

def insert_sort(a):
    for i in xrange(1, len(a)):
        v = a.pop(i)
        p = bisect.bisect(a[:i], v)
        a.insert(p, v)
    return a

Merge sort

核心

合并已经排好序的两个数组,哪个符合条件就添加到结果里。

合并时,对两个数组头元素作出对比,又称”两指合并”

例子

  1. [3 5] [2 1] # 拆成两个数组,并给他们排序
  2. [3 5] [1 2]
  3. R:[1] Stack:[3 5] [2] #两个数组里1 最小,添加到结果里
  4. R:[1 2] Stack:[3 5] # 继续比较2 和 3, 2 比 3小,2添加到结果里
  5. #就重复上述步骤

代码

def merge_sort(a):

    la = len(a)
    if la == 1:
        return a
    elif la == 2 and a[0] > a[1]:
        a[0], a[1] = a[1], a[0]
        return a
    else:
        left, right = merge_sort(a[:la/2]), merge_sort(a[la/2:])
        result = []

        while left and right:
            if left[0] < right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))

        if left:
            result += left
        if right:
            result += right

    return result

Quick sort

个人最喜欢的一个算法,简单,快速!但是对栈的调用较多~

核心

和MergeSort 很像,也是合并已经排好序的两个数组,但是是哪个符合条件就放入递归的qsort里。

可以说两个是一前一后。

代码

def qsort(a):

    la = len(a)
    if la <= 1:
        return a
    elif la == 2 and a[0] > a[1]:
        a[0], a[1] = a[1], a[0]
        return a
    else:
        lt, gt = [], []
        for x in a[1:]:
            if x > a[0]:
                gt.append(x)
            else:
                lt.append(x)
        return qsort(lt) + [a[0]] + qsort(gt)

Heap sort

核心

借助Heap(堆)的特性:最大/小的元素会在数组的头部,进行排序。

知识点

heap是一种由数组构成的特殊二叉树结构,具体在下面的思维导图里。

代码

def heap_sort(a):
    la = len(a)

    def heapify(start, end):
        father = start

        while True:
            child = father * 2 + 1
            if child > end:
                break
            if child + 1 <= end and a[child] < a[child+1]:
                child += 1
            if a[father] < a[child]:
                # swap
                a[father], a[child] = a[child], a[father]
                father = child
            else:
                break

    # la/2 -> 0
    for i in xrange((la-2)//2, -1, -1):
        heapify(i, la-1)

    # la -> 0
    for end in range(la-1, 0, -1):
        a[0], a[end] = a[end], a[0]
        heapify(0, end-1)
    return a

随机输入比较图

#数据结构与算法