十大排序算法整理
总体分类
首先解释一个概念，算法的稳定性：指序列中两相同的相邻元素在两趟排序的过程中相对位置是否发生改变，不改变为稳定的排序算法。
根据这个概念，我们可以对排序算法进行分类：
- 稳定的排序算法：插入排序，冒泡排序， 归并排序， 基数排序，计数排序，桶排序
- 不稳定的排序算法；选择排序， 希尔排序， 快速排序， 堆排序
再根据算法的时间复杂度，我们可以再对算法进行一次排序：
- $O(n^2)$:插入排序， 选择排序，冒泡排序
- $O(nlog_2(n))$:快速排序，归并排序，堆排序
- $O(n^ {1+§}), 0≤§≤1$:希尔排序
- $O(n)$:基数排序，计数排序，桶排序
下面对上述十种常用算法一一分析。
代码详解
选择排序
分析
先从最简单的选择排序开始，这个算法的思想没有什么好说的，就是每一趟从未排序的序列中选出一个最大（小）值，然后放在序列末尾即可。
代码
def select_sort(arr):
n = len(arr)
for i in range(n):
max_idx = 0
for j in range(n-i):
if arr[j] > arr[max_idx]:
max_idx = j
arr[max_idx], arr[n-i-1] = arr[n-i-1], arr[max_idx]插入排序
分析
插入排序的思路也很直观，将序列分为排序和未排序的部分，每次从未排序的部分中选择一个，插入到已排序的序列中的合适的位置即可。
代码
def insert_sort(arr):
n = len(arr)
for i in range(1, n): # a[0]视为已排序序列
for j in range(i):
if arr[i] < arr[j]: # arr[i]是未排序序列中选取的那个 arr[j]是已排列的序列
arr.insert(j, arr[i])
arr.pop(i+1)希尔排序
分析
希尔排序是对插入排序的一种改进。插入排序对于完全有序的序列效率最高，对于完全无序的序列效率最低。希尔排序的思想就是先让序列部分有序，然后再进行插入排序，以此提高效率。为此，希尔排序中设计了增量的概念（个人理解就是分组大小），这个序列也不是随便选择的。希尔排序中使用的序列是${1, 4, 13, …, a_{n-1}*3+1}$，为什么不能使用如{1, 2, 4, 8}或其他的序列呢？因为希尔排序的复杂度是和增量序列的选择有关系的，经过数学证明，最好的一个序列为1，4， 13这样的序列。
代码
def shell_sort(arr):
gap = 1
n = len(arr)
while gap < n//3: # 动态生成间隔序列
gap = gap*3+1
while gap > 0: # 间隔为1即为对整体进行插入排序
for i in range(gap, n): # 将arr[0,gap,gap*2,..]分为一组 开始元素分别为0,1,gap-1
tmp = arr[i] # 当前分组第i//gap个元素
j = i-gap # 当前序列的逻辑索引 gap在逻辑上等于‘1’ 即 j=i-1 即j为arr[i]的上个元素
while j >= 0 and arr[j] > tmp: # 升序排列 尽量将小元素向前排列
# 插入排序 当tmp较小时，需要向前插入 这里是将arr[j]向后移动一位，为tmp插入做准备
arr[j+gap] = arr[j]
j -= gap # 此处的插入排序为倒序遍历
arr[j+gap] = tmp # 确定插入位置后 在此处插入
gap = gap//3 # 缩小gap值，最终退化为插入排序希尔排序中有一点不好理解的是，在排序过程中，每个单独的子序列并不是一次性排序完成的，而是按照原序列的顺序，一步一步的排序完成的。举个例子，若arr[i]属于子序列s1，当s1排序了一步后，总的序列将遍历到arr[i+1]（属于s2），此时则继续对s2进行插入排序。直到最后一个gap，主序列（外层循环）每推进1，就会完成一个子序列的插入排序。个人认为将每个子序列单独出来，完全排序完成后再处理下一个序列也是可行的，但是网络上见到的大多数希尔排序都是这样实现的，可能和性能有关？
冒泡排序
分析
冒泡排序也是一种非常常见的排序方法，每次比较两个元素，如果顺序错误就将其翻转。
代码
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n-i):
if arr[j]>arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]归并排序
分析
归并排序是使用分治思想的一个经典的算法。算法的主要思想就是将长序列化短，短序列化元，元序列（单个元素）自身看作有序，然后再进行合并即可。
代码
def merge_sort(arr):
n = len(arr)
if n < 2:
return arr
m = n//2
left, right = arr[:m], arr[m:]
return merge(merge_sort(left), merge_sort(right))
def merge(left, right):
l, L = 0, len(left)
r, R = 0, len(right)
res = []
while l < L and r < R:
if left[l] < right[r]:
res.append(left[l])
l += 1
else:
res.append(right[r])
r += 1
if l < L:
res += left
if r < R:
res += right
return res快速排序
分析
快速排序使用的也是一种分治的思想。正如名称，快速排序的实际表现比大多数复杂同为$O(nlog_2(n))$的算法更加高效。本质上看，快速排序是在冒泡排序的基础上的递归分治。算法的思想是首先从序列中选出一个元素作为“pivot”，将所有小于pivot的元素放在其左边，大于pivot的放在其右边。对于pivot左右两边，再递归的重复上述操作即可。
代码
def quick_sort(arr, left=None, right=None):
n = len(arr)
if left < right:
m = partition(arr, left, right)
quick_sort(arr, left, m-1)
quick_sort(arr, m+1, right)
def partition(arr, l, r):
x = arr[l]
i = l
j = r
while i < j:
while arr[j] >= x and i<j:
j -= 1
while arr[i] <= x and i<j:
i += 1
if i < j:
arr[i], arr[j] = arr[j], arr[i]
arr[l], arr[i] = arr[i], arr[l]
return i堆排序
分析
堆排序是利用了堆这种数据结构来进行。这里是将序列构建为一个大（小）根堆，然后每次将堆顶的元素与
堆尾交换。然后将堆的大小减小1，重新构建堆。多次重复上述过程，即可完成排序。
代码
def build_max_heap(arr):
for i in range(len(arr)//2, -1, -1):
heapity(arr, i)
def heapify(arr, i):
left = 2*i+1
right = 2*i+2
largest = i
if left < arrLen and arr[left] > arr[largest]:
largest = left
if right < arrLen and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, largest)
def heap_sort(arr):
global arrLen
arrLen = len(arr)
build_max_heap(arr)
for i in range(len(arr)-1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
arrLen -= 1
heapify(arr, 0)
return arr计数排序
分析
计数排序的原理是将序列中的数值都映射到额外的计数数组中去，当计数完成后，排序也完成了，只要按照所需的顺序复原立刻。计数排序要求序列中的值最大不能超过max_value
代码
def count_sort(arr):
n = len(arr)
max_value = 10000
cnt = [0]*max_value
for i in range(n):
cnt[arr[i]] += 1
res = []
for j in range(max_value):
while cnt[j]:
res.append(j)
cnt[j] -= 1
return res桶排序
分析
桶排序是计数排序的一种更加通用的形式，他的原理是利用一个hash函数将序列中的元素映射到各个桶中去，然后再对桶中元素进行排序。当每个元素都均匀的分到每个桶中时，效率最高（极端情况退化为计数排序）。反之，所有元素都分配到同一个桶中的时候，效率最低。因此，桶排序的效率和hash函数有很大的关联。
代码
def bucket_sort(arr, bucketSize=5): # 默认桶的大小为5 越大越好
n = len(arr)
if n < 2:
return arr
max_value = max(arr)
min_value = min(arr)
bucketCnt = (max_value-min_value)//bucketSize+1 # 计算需要多少桶
buckets = [[] for _ in range(bucketCnt)]
# 此处即为hash函数的实现 f(arr[i])=(arr[i]-min_value)//bucketSize 可设计不同函数
for i in range(n):
buckets[(arr[i]-min_value)//bucketSize].append(arr[i])
arr = []
# 对每个桶内的元素进行排列
for i in range(bucketCnt):
insert_sort(buckets[i]) # 此处直接调用插入排序
for j in range(len(buckets[i])):
arr.append(buckets[i][j]) # 将排序后的结果写到arr中作为结果
return arr基数排序
分析
基数排序是一种非比较型的整数排序算法，其原理是将整数按照位分割，然后对应每个位进行比较，比如说，同时比较所有数的个位，然后是十位，以此类推，这里同样运用了桶的概念。基数排序的桶是固定的，将0～9作为桶，每次都按照不同位将数字映射到这些桶中，以达到排序的目的。可以说基数排序是一种特殊的桶排序。
代码
def radix_sort(arr):
digit = 0 # 记录当前排序到第几位
max_digit = 1 # 记录最大位数
max_value = max(arr)
while 10**max_digit < max_value: # 计算最大位数
max_digit += 1
while digit < max_digit:
tmp = [[] for _ in range(10)] # 对每一位 进行一次桶排序
for i in arr:
t = (i//10**digit)%10 # 此处为该桶排序的hash函数 较为特殊
tmp[t].append(i)
col = []
for bucket in tmp: # 统计当前位的排序结果 基于此对下一位进行排序 达到整体排序的目的
for i in bucket:
col.append(i)
arr = col
digit += 1
return arr
