1、冒泡排序
从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续这个过程，直到所有数据元素都排好序。
算法的核心在于每次通过两两比较交换位置，选出剩余无序序列里最大（小）的数据元素放到队尾。
def bubbleSort(number):
length = len(number)
for i in xrange(length):
for j in xrange(length-i-1):
if number[j] > number[j+1]:
number[j], number[j+1] = number[j+1], number[j]
print number
bubbleSort([1,3,4,2,7,6,4])
2、直接插入排序
简单的排序方式，取一个数，然后和已经排好的从后往前进行比较，找到适合自己的坑位。
python实现：
def insertSort(A):
for j in range(1, length):
key = A[j]
i = j - 1
while i >= 0 and A[i] > key:
A[i + 1] = A[i]
i = i - 1
A[i + 1] = key
return A
直接插入排序除了上面的方式，还可以以交换的方式。
def insertSort1(number):
for i in range(1,len(number)):
for j in range(i-1,-1,-1):
if number[j] > number[j+1]:
number[j], number[j+1] = number[j+1], number[j]
print number
3、选择排序
选择排序，每一次找一个最大或最小的数。
选择排序和冒泡排序很像。
# 选择排序
def selectSort(number):
length = len(number)
for i in range(length):
minIndex = i
for j in range(i+1, length):
if number[j] < number[minIndex]:
minIndex = j
number[i], number[minIndex] = number[minIndex], number[i]
print number
selectSort([1,3,4,2,7,6,4])
4、希尔排序
希尔排序在直接插入排序的基础上做了改进，先将元素进行分组，原理如下：
本质还是直接插入排序。
# 希尔排序，交换法
def shellSort(seq):
length = len(seq)
inc = 0
while inc <= length/3:
inc = inc * 3 + 1
while inc >= 1:
for i in range(inc, length):
for j in range(i, 0, -inc):
if seq[j] < seq[j-inc]:
seq[j], seq[j-inc] = seq[j-inc], seq[j]
inc//=3
# 移动法
def shellSort1(seq):
length = len(seq)
inc = 0
while inc <= length / 3:
inc = inc * 3 + 1
while inc >= 1:
for i in range(inc, length):
j = i
temp = seq[j]
while j-inc >= 0 and temp < seq[j-inc]:
seq[j] = seq[j-inc]
j -= inc
seq[j] = temp
inc //= 3
希尔排序最关键的是选择步长，本程序选用Knuth在1969年提出的步长序列：1 4 13 40 121 364 1093 3280 。。。后一个元素是前一个元素*3+1。
参考学习
https://www.cnblogs.com/chengxiao/p/6104371.html
5、堆排序
堆排序是借助堆来实现的选择排序，思想同简单的插入排序，以下以大顶堆为例。注意：如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。
堆排序要考虑的问题有以下几个：
- 给定一个序列，如何构造成一个堆
- 如何进行堆的调整
堆排序是将一个数组以二叉树的形式进行调整，但并不需要实现二叉树结构，基础的关系式：编号为 index的节点的父节点为 (index-1) / 2，左右孩子节点为 index * 2 + 1 / 2
对叶子结点来说，可以认为它已经是一个合法的堆了即20，60， 65， 4， 49都分别是一个合法的堆。只要从A[4]=50开始向下调整就可以了。然后再取A[3]=30，A[2] = 17，A[1] = 12，A[0] = 9分别作一次向下调整操作就可以了。
def HeapAdjust(seq, index, length):
temp = seq[index]
childIndex = index * 2 + 1
while childIndex < length:
# 找出左右节点中最大的数
if childIndex + 1 < length and seq[childIndex] < seq[childIndex + 1]:
childIndex += 1
if seq[childIndex] <= temp:
break
seq[index] = seq[childIndex]
index = childIndex
childIndex = childIndex * 2 + 1
seq[index] = temp
def heap_sort(data):
m = len(data) / 2 - 1
for i in range(m, -1, -1):
HeapAdjust(data, i, len(data))
for n in range(len(data) - 1, 0, -1):
data[0], data[n] = data[n], data[0]
HeapAdjust(data, 0, n)
print data
6、归并排序
def mergeSort(seq):
if len(seq) <= 1:
return seq
mid = len(seq) / 2
left = mergeSort(seq[:mid])
right = mergeSort(seq[mid:])
return merge(left, right)
def merge(left, right):
res = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
res += left[i:]
res += right[j:]
return res
归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。
7、快速排序
def quickSort(seq):
if not seq:
return []
base = seq[0]
left = [item for item in seq if item < base]
right = [item for item in seq if item > base]
return quickSort(left) + [base] + quickSort(right)
上面的程序是需要格外o(n)的空间，因此程序比较简洁。如果采用inplace，会比较复杂点。
8、计数排序
计数排序的时间复杂度为o(n)，以空间换时间。建立一个min-max长度的数组。
https://blog.csdn.net/liyuming0000/article/details/46913357
9、桶排序
桶排序的基本思想：
假设有一组长度为N的待排关键字序列K[1....n]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数 ，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]….B[M]中的全部内容即是一个有序序列
10、基数排序
https://www.jianshu.com/p/a1012fab9161
import random
def radixSort():
A=[random.randint(1,9999) for i in xrange(10000)]
for k in xrange(4): #4轮排序
s=[[] for i in xrange(10)]
for i in A:
s[i/(10**k)%10].append(i)
A=[a for b in s for a in b]
return A
基数排序很独特。建立10个桶，首先根据个位数将数据丢进桶里，然后从取出数据作为新的序列，再将该序列根据十位数进行排序，以此类推。
运用基数排序需要确定最大数的位数。基数排序对负数支持的话需要进一步处理。
