一个推荐的博客，里面有详细的动图介绍。
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 快速排序 | 不稳定 | ||||
| 冒泡排序 | 稳定 | ||||
| 插入排序 | 稳定 | ||||
| 选择排序 | 不稳定 | ||||
| 归并排序 | 稳定 | ||||
| 希尔排序 | 不稳定 | ||||
| 堆排序 | 不稳定 |
快速排序
思想：
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分进行排序，也就是分治法的思想。
步骤：
- 从数列中挑选出一个元素，作为基准
- 重新遍历数列，将比基准小的放在前面，比基准大的放在后面，相同的可以放在任意一边
- 然后对刚才左边的和右边的，分别递归上面的操作
不稳定，这个时候不是双重循环，时间复杂度O(nlogn).
# ------ coding:utf-8 -----
'''
快速排序
从数组中选择一个数作为基准，然后将数组分成三部分，小于、等于、大于这个基准的
然后对小于、大于基准的数组重复上面的操作
O(nlogn),不稳定
'''
def quickSort(nums):
if len(nums) <= 1:
return nums
base = nums[0]
left = []
equal = []
right = []
for num in nums:
if num < base:
left.append(num)
elif num > base:
right.append(num)
else:
equal.append(num)
left = quickSort(left)
right = quickSort(right)
return left + equal + right
print quickSort([2,3,1,9,0,4,7,8,5])
还有另外一种常见的原地排序的实现方法：
def quickSort2(nums, left, right):
if left >= right:
return
low = left
high = right
base = nums[left]
while left < right:
while left < right and nums[right] > base:
right -= 1
nums[left] = nums[right]
while left < right and nums[left] <= base:
left += 1
nums[right] = nums[left]
nums[right] = base
quickSort2(nums, low, left-1)
quickSort2(nums, left+1, high)
冒泡排序
思想：
重复走访待排的序列，一次比较两个元素，比如它们之间的顺序错误了，就把它们进行交换。冒泡排序就是把小的元素往前调，把大的元素往后调。经过一次循环之后，最大的值将出现在最后。注意的是相邻的两个元素进行比较，而且是否需要交换也发生在这两个元素之间。
步骤：
- 比较相邻元素，如果第一个比第二个大，则交换它们
- 重复，直到序列末尾，这个时候序列最后的元素就是最大的数
- 重复，直到排序完成
当此次循环中，没有元素交换的时候，就停止，代表排序完成
如果两个元素相等，是不会去交换位置的。所以即使通过前面的两辆交换把两个元素放在的一起，也不会交换他们的位置，所以冒泡排序是稳定的。双重循环，时间复杂度O(n2).
# ------- coding:utf-8 ----
'''
冒泡排序
将大的元素向后调，则一次机就将最大的元素放在了最后
时间复杂度是O(n^2)，稳定
'''
def bubbleSort(nums):
# 外层循环控制从头到尾的次数
for i in range(len(nums)-1):
count = 0 # 记录一次循环中，交换元素的次数，如果为0的话，就停止了
# 内层循环控制走一次的过程
for j in range(len(nums)-1-i):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
count += 1
if count == 0:
break
return nums
print bubbleSort([1,2,7,8,3,1,9,0,5])
插入排序
思想：
通过构建有序序列，对于未排序数据，在已排序序列中，从后向钱扫描，找到相应的位置进行并插入。
步骤：
- 从第一个元素开始，这个时候是一个有序序列
- 取出下一个元素，在已经排序的序列中，从后向前扫描，如果有序序列中的当前元素大于待排元素，则该元素后移一个位置，直到找到有序序列中的元素小于等于待排元素，就在该位置进行插入（可能找不到这样的元素，则就在最前的位置插入）
- 重复上面的步骤，直到没有待排元素
相等元素的前后顺序没有改变，所以插入排序是稳定的。双重循环，时间复杂度O(n2).
# ------ coding:utf-8 -----
'''
插入排序
在已经有序的小序列的基础上，一次插入一个元素。最初状态只有1个元素
O(n^2)，稳定
'''
def insertSort(nums):
n = len(nums)
for i in range(1, n):
# 将当前元素放到前面有序序列的正确位置
for j in range(i, 0, -1):
# 如果当前当前元素比前面的元素小，则往前移动，与前面的元素交换
if nums[j] < nums[j-1]:
nums[j], nums[j-1] = nums[j-1], nums[j]
else:
break
return nums
print insertSort([1,2,8,9,0,3,6,7,4])
选择排序
思想：
首先在未排序的序列中找到最小的元素，存放在已排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列末尾。
选择排序即是给每个位置选择待排序元素中当前最小的元素。比如给第一个位置选择最小的，在剩余元素里面给第二个位置选择次小的。以此类推，直到第n-1个元素，第n个元素就不用选择了。
举例：5 8 5 2 9，首先会将5与2进行交换，那么两个5的顺序就交换了，所以，选择排序不稳定。
双重循环，时间复杂度O(n2).
# ------ coding:utf-8 -------
'''
选择排序
给每个位置选择待排序中当前最小的元素（交换）
O(n^2)，不稳定
'''
def selectSort(nums):
n = len(nums)
for i in range(n-1):
min_dix = i
for j in range(i+1, n):
# 寻找最小元素的下标
if nums[min_dix] > nums[j]:
min_dix = j
if i != min_dix:
# 交换当前元素和最小元素
nums[i], nums[min_dix] = nums[min_dix], nums[i]
return nums
print selectSort([1,2,0,4,9,8,5,4,7])
归并排序
思想：
采用分治法，将两个已经有序的序列合并成一个有序序列，得到完全有序的序列。即先使每个子序列有序，再使自序列之间有序。若将两个有序表合并成一个有序表，成为2-路归并。
步骤：
- 将长度为 n 的序列分成两个长度为 n/2 的子序列
- 将这两个自序列分别采用归并排序
- 将两个排序好的自序列合并成一个最终的排序序列
归并排序最初的状态，可以看成是 n 个长度为 1 的有序自序列。
在1个或2个元素时，1个元素不会交换，2个元素如果大小相等的话也不会交换，所以是稳定的
这个时候不是双重循环，时间复杂度O(nlogn)
# -------- coding:utf-8 ------
'''
归并排序
将两个有序序列合并成一个有序序列，初始状态是n个长度为1的有序序列
O(nlong), 稳定
'''
def mergeSort(nums):
# 先分解成n个长度为1的有序序列
if len(nums) <= 1:
return nums
mid_idx = len(nums) / 2
left_nums = mergeSort(nums[:mid_idx]) # 将左边的部分数据进行排序
right_nums = mergeSort(nums[mid_idx:]) # 右边的部分数据进行排序
return merge(left_nums, right_nums) # 将两个有序数组合并为一个有序书序
def merge(left_nums, right_nums):
result = []
left_idx, right_idx = 0, 0
# 逐个比较两个数组最前面的元素
while left_idx < len(left_nums) and right_idx < len(right_nums):
if left_nums[left_idx] < right_nums[right_idx]:
result.append(left_nums[left_idx])
left_idx += 1
else:
result.append(right_nums[right_idx])
right_idx += 1
# 将数组剩下部分加入
result += left_nums[left_idx:]
result += right_nums[right_idx:]
return result
print mergeSort([1,2,0,9,4,5,8,7,3])
希尔排序
思想：
希尔排序又叫做缩小增量排序。是简单插入排序的改进版，不同之处在于，它会优选比较距离较远的元素。
步骤：
- 选择增量序列：如 5 3 2 1
- 按增量序列个数 k，进行 k 趟排序，上面这个例子就是 4 趟排序
- 每趟排序，根据对应的增量，将器分成若干个长度为 m 的子序列，然后对各个子表进行直接插入排序
通常在实现的过程中，可以不用指定增量序列，初始增量 step = len(nums)/2，后面每一次 step/= 2.
def shellSort(nums):
n = len(nums)
step = n / 2
while step >= 1:
for i in range(step, n):
for j in range(i, 0, -step):
if nums[j] < nums[j - step]:
nums[j], nums[j - step] = nums[j - step], nums[j]
else:
break
step /= 2
return nums
因为相同的数在一次 step 中，可能不在同一个自序列，因此可能在这个过程中位置发生改变，所以希尔排序是不稳定的。
堆排序
思想：
堆排序是基于完全二叉树，以大顶堆为例，大顶堆表示每个节点都大于或等于自己的孩子节点。
步骤：
- 将长度为 n 的待排数组进行堆有序化构造成一个大顶堆
- 构造的过程是，假如有 n 个节点，则逐个检查 n/2-1 ~ 0 这些节点，因为只有这些节点有孩子节点，如果他们比孩子节点小，则跟孩子节点进行交换 - 将大顶堆的根节点与尾节点进行交换
- 检查剩下的 n-1 个节点
- 重复上面的步骤，直到大顶堆中只有一个节点
