排序算法笔记

最近在上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

随机输入比较图

#数据结构与算法

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据