排序是比较常用的算法，其实有很多种实现，比如冒泡排序，选择排序，归并排序，希尔排序，快速排序等，今天介绍使用python语言实现这几种排序算法。
冒泡排序冒泡排序是最常见到的排序算法，也是大学学习时遇到的第一种排序算法，它的实现思想是：相邻的两个元素进行比较，然后把较大的元素放到后面（正向排序），在一轮比较完后最大的元素就放在了最后一个位置，因为这一点像鱼儿在水中吐的气泡在上升的过程中不断变大，所以得名冒泡排序。在该排序算法中，要遍历n-1轮，每一轮都要比较数组中的元素，所以时间复杂度是
O(n2)。具体实现的代码如下：
def bubble_sort(alist):
length = len(alist)
for i in range(length - 1):
# i表示比较多少轮
for j in range(length - i - 1):
# j表示每轮比较的元素的范围，因为每比较一轮就会排序好一个元素的位置，
# 所以在下一轮比较的时候就少比较了一个元素，所以要减去i
if alist[j] > alist[j + 1]:
alist[j], alist[j + 1] = alist[j + 1], alist[j]
在比较的过程中相同的元素并不会发生交换，所以冒泡排序是一种稳定的排序算法。
选择排序选择排序的思路是：第一轮的时候，所有的元素都和第一个元素进行比较，如果比第一个元素大，就和第一个元素进行交换，在这轮比较完后，就找到了最小的元素；第二轮的时候所有的元素都和第二个元素进行比较找出第二个位置的元素，以此类推。
每遍历一次排好一个元素，而每一次都会比较所有的元素，所以时间复杂度为O(n2)。因为在交换的过程中，相同的元素位置可能发生变化，所以选择排序是不稳定的。具体的实现代码如下：
def selection_sort(alist):
length = len(alist)
for i in range(length - 1, 0, -1):
for j in range(i):
if alist[j] > alist[i]:
alist[j], alist[i] = alist[i], alist[j]
插入排序
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。如图所示：
插入排序的时间复杂度为O(n2)。
具体的实现代码如下所示：
def insert_sort(alist):
for i in range(1, len(alist)):
# 从第二个元素开始，每次取出一个元素，插入前面的序列使其有序
for j in range(i, 0, -1):
if alist[j] < alist[j - 1]:
alist[j], alist[j - 1] = alist[j - 1], alist[j]
快速排序
快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
步骤为：
- 从数列中挑出一个元素，称为"基准"（pivot），一般是第一个元素。
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
def quick_sort(alist, start, end):
if start >= end:
return
low = start
high = end
mid = alist[low]
while low < high:
while low < high and mid < alist[high]:
# 从右边开始找，如果元素小于基准，则把这个元素放到左边
high -= 1
alist[low] = alist[high]
while low < high and mid > alist[low]:
# 从左边开始找，如果元素大于基准，则把元素放到右边
low += 1
alist[high] = alist[low]
# 循环退出，low==high，把基准元素放到这个位置
alist[low] = mid
# 递归调用，重新排列左边的和右边的序列
quick_sort(alist, start, low-1)
quick_sort(alist, low+1, end)
因为每次将序列切分为2部分，如果切割了n次把元素切割完，序列的长度为m，则2n=m，所以切割的时间复杂度为log（n),在每次切割的时候都会比较所有的元素，需要n次，所以整体的时间复杂度为O(nlog(n))。在比较的过程中元素的位置可能挪动，所以快速排序是不稳定的排序。
希尔排序希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。排序过程
希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。
例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样(竖着的元素是步长组成)：
13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10
然后我们对每列进行排序：
10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45
将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了，然后再以3为步长进行排序：
10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45
排序之后变为：
10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94
最后以1步长进行排序（此时就是简单的插入排序了）
希尔排序的分析如下：
具体实现代码如下：
def shell_sort(alist):
n = len(alist)
# 初始步长
gap = n / 2
while gap > 0:
# 按步长进行插入排序
for i in range(gap, n):
j = i
# 插入排序
while j >= gap and alist[j - gap] > alist[j]:
alist[j - gap], alist[j] = alist[j], alist[j - gap]
j -= gap
# 得到新的步长
gap = gap / 2
- 最坏时间复杂度：O(n2)
- 稳定性：不稳定
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
def merge_sort(alist):
if len(alist) <= 1:
return
num = len(alist) / 2
# 划分
left = merge_sort(alist[:num])
right = merge_sort(alist[num:])
# 合并
return merge(left, right)
def merge(left, right):
l, r = 0, 0
result = []
while l < len(left) and r < len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result.append(left[l:])
result.append(right[r:])
return result
总结：
