一、排序算法概览
插入排序：直接插入排序，二分法插入排序
选择排序：直接选择排序，堆排序
交换排序：冒泡排序，快速排序
归并排序
二、代码实现
1.直接插入排序
最简单直接的一种方式，序列在排序中可分为左边已排序部分和右边未排序部分。每次从未排序部分取出一个数，通过与已排序部分逐次比较，移动，最终放到正确的位置。这个算法不使用辅助空序列，空间复杂度为O(1)，平均时间复杂度为O(n^2)。当序列为基本有序时，插入排序能做到O(n)。
def inset_sort(lst):
for i in range(1, len(lst)):
x = lst[i]
j = i
while j > 0 and lst[j-1] > x:
lst[j] = lst[j-1]
j -= 1
lst[j] = x
2.二分法插入排序
在直接插入的基础上，通过二分法可以快速找到应该插入的位置，优化了比较次数。但仍需要逐步移动数据。因此，和直接插入排序比较，复杂度没有质的改变。
def bisect_inset_sort(lst):
for i in range(1, len(lst)):
x = lst[i]
left = 0
right = i-1
mid = int(right / 2)
# 找到最终位置
while left < right:
if lst[mid] > x:
right = mid-1
elif lst[mid] <= x:
left = mid+1
mid = int((left + right) / 2)
if lst[mid] <= x:
index = mid+1
else:
index = mid
# 通过交换移动到最终位置
for j in range(i, index, -1):
lst[j-1], lst[j] = lst[j], lst[j-1]
3.直接选择排序
每次从未排序的部分选择最大/小值插入已排序末尾。时间复杂度O(n^2），空间复杂度O(1)
def select_sort(lst):
for i in range(len(lst)-1):
k = i
for j in range(i, len(lst)):
if lst[j] < lst[k]:
k = j
if i != k:
lst[i], lst[k] = lst[k], lst[i]
4.冒泡排序
每一遍检查，都是两两比较并交换位置。最终导致该次最大元素放到正确位置，同时，较大元素可能移动一定位置。平均时间复杂度O(n^2)，空间复杂度O(1)。这个算法对已排序的序列不友好，比如逆序序列要顺序排列，每个元素都需要移动最大距离。
def bubble_sort(lst):
n = len(lst)
for i in range(n):
found = False
# 可以理解为从0到n-i-1中找到最大值放在n-i-1这个位置
for j in range(0, n - i - 1):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
found = True
# 如果一轮排序下来没有遇到逆序排列，说明已经全部排好
if not found:
break
5.快速排序
（1）方法1，以一个元素为基准，将序列划分为大于和小于该基准两部分，分列左右两边，基准在中间。然后对左右两部分再次进行相同操作。易知，如果每次都能选择中间值作为基准，保证划分的两部分大小相同，此时效率最高。平均时间复杂度O(nlogn)，对于空间复杂度，虽然快排也没有使用额外辅助（只有几个临时变量），但使用了递归，有了额外花销。与具体实现有关。
def quick_sort(lst):
base_sort(lst, 0, len(lst)-1)
def base_sort(lst, left, right):
if left >= right:
return
i, j = left, right
k = lst[i]
while i < j:
while i < j and lst[j] >= k:
j -= 1
if i < j:
lst[i] = lst[j]
i += 1
while i < j and lst[i] <= k:
i += 1
if i < j:
lst[j] = lst[i]
j -= 1
lst[i] = k
base_sort(lst, left, i-1)
base_sort(lst, i+1, right)
（2）方法2，将序列根据基准划分为小记录，大记录，未排序。每次从未排序中选第一个元素，如果大于等于基准，指针往后移；若小于基准，交换大记录第一个和本元素
def quick_sort2(lst):
def qsort(lst, begin, end):
if begin >= end:
return
k = lst[begin]
i = begin
for j in range(begin+1, end+1):
if lst[j] < k:
i += 1
lst[i], lst[j] = lst[j], lst[i]
lst[begin], lst[i] = lst[i], lst[begin]
# 递归，再对小于k和大于k的两段序列进行排序
qsort(lst, begin, i-1)
qsort(lst, i+1, end)
qsort(lst, 0, len(lst)-1)
(3) 三路快排，即将数据划分为小于基准、等于基准、大于基准三部分，等于基准的部分不参与下一轮排序。这个方法在数组中存在大量相同元素时会非常高效。
def quick_sort3(lst):
def sort(l, r):
if l >= r:
return
lt = l
gt = r+1
i = l+1
# 基准的选择也可以随机
v = lst[l]
while i < gt:
if lst[i] < v:
lt += 1
i += 1
elif lst[i] > v:
lst[i], lst[gt-1] = lst[gt-1], lst[i]
gt -= 1
else:
i += 1
lst[l], lst[lt] = lst[lt], lst[l]
sort(l, lt-1)
sort(gt, r)
sort(0, len(lst)-1)
6.归并排序
一开始，一个元素看作一个排好序的段，相邻段合并成包含两个元素的有序段，以此类推。直至段的长度等于序列长度。时间复杂度O(nlogn)，这里使用了辅助列表，长度和原序列相同，因此，空间复杂度为O(n)。
def merge_sort(lst):
"""负责合并两个子序列"""
def merge(lfrom, lto, low, mid, high):
i, j, k = low, mid, low
while i < mid and j < high:
if lfrom[i] <= lfrom[j]:
lto[k] = lfrom[i]
i += 1
else:
lto[k] = lfrom[j]
j += 1
k += 1
# 复制第一段剩余记录
while i < mid:
lto[k] = lfrom[i]
i += 1
k += 1
# 复制第二段剩余记录
while j < high:
lto[k] = lfrom[j]
j += 1
k += 1
"""完成一遍合并，将子序列两两合并"""
def merge_pass(lfrom, lto, llen, slen):
i = 0
while i + 2 * slen < llen:
merge(lfrom, lto, i, i+slen, i+2*slen)
i += 2*slen
# 剩两段，最后一段长度小于slen
if i + slen < llen:
merge(lfrom, lto, i , i+slen, llen)
# 只剩一段，直接复制
else:
for j in range(i, llen):
lto[j] = lfrom[j]
slen, llen = 1, len(lst)
# 和原表等长的辅助表
tmp_lst = [None] * llen
while slen < llen:
merge_pass(lst, tmp_lst, llen, slen)
slen *= 2
# 在原表和辅助表之间来回进行归并
merge_pass(tmp_lst, lst, llen, slen)
slen *= 2
7.总结
各种排序算法各有适用场景，实际使用中也并非只用一种。比如在使用快速排序和归并排序时，针对短序列（比如当被排序序列长度小于15）可以使用直接插入排序这样的简单稳定算法。
