在python实践中，我们往往遇到排序问题，比如在对搜索结果打分的排序（没有排序就没有google等搜索引擎的存在），当然，这样的例子数不胜数。《数据结构》也会花大量篇幅讲解排序。之前一段时间，由于需要，我复习了一下排序算法，并用python实现了各种排序算法，放在这里作为参考。
最简单的排序有三种：插入排序，选择排序和冒泡排序。这三种排序比较简单，它们的平均时间复杂度均为o(n^2)，在这里对原理就不加赘述了。贴出来源代码。
插入排序：
def insertion_sort(sort_list):
iter_len = len(sort_list)
if iter_len < 2:
return sort_list
for i in range(1, iter_len):
key = sort_list[i]
j = i - 1
while j >= 0 and sort_list[j] > key:
sort_list[j+1] = sort_list[j]
j -= 1
sort_list[j+1] = key
return sort_list
冒泡排序：
def bubble_sort(sort_list):
iter_len = len(sort_list)
if iter_len < 2:
return sort_list
for i in range(iter_len-1):
for j in range(iter_len-i-1):
if sort_list[j] > sort_list[j+1]:
sort_list[j], sort_list[j+1] = sort_list[j+1], sort_list[j]
return sort_list
选择排序：
def selection_sort(sort_list):
iter_len = len(sort_list)
if iter_len < 2:
return sort_list
for i in range(iter_len-1):
smallest = sort_list[i]
location = i
for j in range(i, iter_len):
if sort_list[j] < smallest:
smallest = sort_list[j]
location = j
if i != location:
sort_list[i], sort_list[location] = sort_list[location], sort_list[i]
return sort_list
这里我们可以看到这样的句子：
sort_list[i], sort_list[location] = sort_list[location], sort_list[i]
不了解python的同学可能会觉得奇怪，没错，这是交换两个数的做法，通常在其他语言中如果要交换a与b的值，常常需要一个中间变量temp，首先把a赋给temp，然后把b赋给a，最后再把temp赋给b。但是在python中你就可以这么写：a, b = b, a，其实这是因为赋值符号的左右两边都是元组（这里需要强调的是，在python中，元组其实是由逗号“,”来界定的，而不是括号）。
平均时间复杂度为o(nlogn)的算法有：归并排序，堆排序和快速排序。
归并排序。对于一个子序列，分成两份，比较两份的第一个元素，小者弹出，然后重复这个过程。对于待排序列，以中间值分成左右两个序列，然后对于各子序列再递归调用。源代码如下，由于有工具函数，所以写成了callable的类：
class merge_sort(object):
def _merge(self, alist, p, q, r):
left = alist[p:q+1]
right = alist[q+1:r+1]
for i in range(p, r+1):
if len(left) > 0 and len(right) > 0:
if left[0] alist[largest]:
largest = r
if largest!=i:
alist[i], alist[largest] = alist[largest], alist[i]
self._max_heapify(alist, largest, heap_size)
def _build_max_heap(self, alist):
roop_end = int(len(alist)/2)
for i in range(0, roop_end)[::-1]:
self._max_heapify(alist, i)
def __call__(self, sort_list):
self._build_max_heap(sort_list)
heap_size = len(sort_list)
for i in range(1, len(sort_list))[::-1]:
sort_list[0], sort_list[i] = sort_list[i], sort_list[0]
heap_size -= 1
self._max_heapify(sort_list, 0, heap_size)
return sort_list
最后一种要说明的交换排序算法（以上所有算法都为交换排序，原因是都需要通过两两比较交换顺序）自然就是经典的快速排序。
先来讲解一下原理。首先要用到的是分区工具函数（partition），对于给定的列表（数组），我们首先选择基准元素（这里我选择最后一个元素），通过比较，最后使得该元素的位置，使得这个运行结束的新列表（就地运行）所有在基准元素左边的数都小于基准元素，而右边的数都大于它。然后我们对于待排的列表，用分区函数求得位置，将列表分为左右两个列表（理想情况下），然后对其递归调用分区函数，直到子序列的长度小于等于1。
下面是快速排序的源代码：
class quick_sort(object):
def _partition(self, alist, p, r):
i = p-1
x = alist[r]
for j in range(p, r):
if alist[j]