引言
常用排序算法共有十种，堆排序在前面的章节已经介绍过，本章主要介绍九种常用排序算法。排序算法分为以下几种类型：
非线性时间比较类排序
1. 交换排序：冒泡排序和快速排序
2. 插入排序：简单插入和希尔排序
3. 选择排序：简单选择和堆排序
4. 归并排序：二路归并排序和多路归并排序线性时间非比较类排序
1. 基数排序
2. 计数排序
3. 桶排序
各大排序算法复杂度比较：
在正式开始排序算法讲解之前，准备好通用工具，以便后续算法测试
# 工具箱
from random import randint
# 生成随机序列
def generateRandomSequence(start, end):
output = [randint(start, end) for _ in range(100)]
return output
# 检验排序正确性
def testSorted(sorted_list):
if not sorted_list:
raise ValueError('数组为空，无法检测！')
for i in range(1, len(sorted_list)):
# 默认检测升序
if sorted_list[i] < sorted_list[i-1]:
return False
return True
此外，本文所有排序算法都默认为升序排列（包含思路解释），事实上降序原理一模一样。
冒泡排序
核心思想
对一个列表多次重复便利，比较相邻的两项，并且交换顺序排错的项。每对列表实现一次遍历，就有一个最大项排在了正确的位置，遍历到最后就完成了排序。
Python实现
利用for-loop结构，免去繁杂的边界问题，外循环倒序遍历，保证每轮循环的最后一项都是已排好的。此外，还增加了'剪枝'操作，如果在某一轮循环中不存在冒泡的行动，说明此时数组已完成排序。
def bubbleSort(nums):
size = len(nums)
for i in range(size-1, -1, -1):
flag = False
for j in range(i):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
flag = True
if not flag:
break
return nums
if __name__ == '__main__':
sample = generateRandomSequence(0, 100)
bubble_sorted = bubbleSort(sample)
testSorted(bubble_sorted)
快速排序
核心思想
四个字可以概括快排的思路——分而治之，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对两部分数据进行快速排序，递归地完成整个过程。
Python实现
def quickSort(nums):
size = len(nums) # 计算数组长度
def helper(left, right):
if left >= right: # 递归出口：当左指针大于右指针时，表明左右两侧均已调整完成
return nums
pivot = left # 设置基准值指针
i, j = left, right # 设置左右指针
while i < j:
# 指针滑动，保证右指针指向小于基准的元素，左指针指向大于基准的元素
while i < j and nums[j] > nums[pivot]:
j -= 1
while i < j and nums[i] <= nums[pivot]:
i += 1
nums[i], nums[j] = nums[j], nums[i]
# 调整基准点
nums[pivot], nums[j] = nums[j], nums[pivot]
helper(left, j-1) # 调整基准点左侧
helper(j+1, right) # 调整基准点右侧
return nums
return helper(0, size-1)
if __name__ == '__main__':
sample = generateRandomSequence(0, 100)
quick_sorted = quickSort(sample)
testSorted(quick_sorted)
简单插入排序
核心思想
将每个元素插入到前面已排序的部分，直到最后完成排序。
Python实现
这里给出for循环版本和while循环版本
def insertionSort(nums):
size = len(nums)
for i in range(1, size):
if nums[i] < nums[i-1]:
tmp = nums.pop(i)
for j in range(i):
if tmp < nums[j]:
nums.insert(j, tmp)
break
return nums
def insertionSort1(nums):
size = len(nums)
for i in range(1, size):
while i > 0 and nums[i-1] > nums[i]:
nums[i-1], nums[i] = nums[i], nums[i-1]
i -= 1
return nums
if __name__ == '__main__':
sample = generateRandomSequence(0, 100)
insertion_sorted = insertionSort(sample)
testSorted(insertion_sorted)
insertion_sorted1 = insertionSort1(sample)
testSorted(insertion_sorted1)
希尔排序
核心思想
插入排序的改进版，每次选取一定的间隔，然后对分割的子序列进行插入排序，直到分割间隔为0时终止。
Python实现
def shellSort(nums):
size = len(nums)
gap = size // 2
while gap:
for i in range(gap, size):
while i - gap >= 0 and nums[i-gap] > nums[i]:
nums[i-gap], nums[i] = nums[i], nums[i-gap]
i -= gap
gap //= 2
return nums
if __name__ == '__main__':
sample = generateRandomSequence(0, 100)
shell_sorted = shellSort(sample)
testSorted(shell_sorted)
选择排序
核心思想
在未排序的列表中选取一个最小值放到已排序数组的第一位，直到最后一个元素选择完毕。
Python实现
def selectionSort(nums):
size = len(nums)
start = 0
while start < size:
min_num = float('inf')
min_index = 0
for j in range(start, size):
if nums[j] < min_num:
min_num = nums[j]
min_index = j
nums[start], nums[min_index] = nums[min_index], nums[start]
start += 1
return nums
if __name__ == '__main__':
sample = generateRandomSequence(0, 100)
selection_sorted = selectionSort(sample)
testSorted(selection_sorted)
归并排序
核心思想
归并排序和快排同样采用了分而治之的思想，但它的算法思路是递归地将数组分割为几个子数组，再将子数组内部和外部排序，最后拼接。
Python实现
def mergeSort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = mergeSort(nums[:mid])
right = mergeSort(nums[mid:])
return merge(left, right)
def merge(left, right):
res = []
i, j = 0, 0
while i < len(left) or j < len(right):
if left[i] < right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
if i == len(left):
while j < len(right):
res.append(right[j])
j += 1
elif j == len(right):
while i < len(left):
res.append(left[i])
i += 1
return res
if __name__ == '__main__':
sample = generateRandomSequence(0, 100)
merge_sorted = mergeSort(sample)
testSorted(merge_sorted)
基数排序
核心思想
根据数字的位数进行排序，从最低位开始到最高位。
Python实现
def radixSort(nums):
if not nums:
return []
maxNum = max(nums)
maxDigit = len(str(maxNum))
bucketList = [[] for _ in range(10)]
div, mod = 1, 10
for i in range(maxDigit):
for num in nums:
bucketList[num % mod // div].append(num)
div *= 10
mod *= 10
idx = 0
for j in range(10):
for k in bucketList[j]:
nums[idx] = k
idx += 1
bucketList[j] = []
return nums
if __name__ == '__main__':
sample = generateRandomSequence(0, 100)
radix_sorted = radixSort(sample)
testSorted(radix_sorted)
计数排序
核心思想
计算除数组的最大值和最小值，根据最值开辟一个空间，然后空间种元素下标为数组种的值，元素值表示该元素的数量。最后将这个空间索引元素按顺序输出完成排序，这个方法的缺点是浪费了大量空间，且效率完全取决于最值之差。
Python实现
def countingSort(nums):
max_num, min_num = max(nums), min(nums)
tmp = [0] * (max_num-min_num+1)
for num in nums:
tmp[num-min_num] += 1
res = []
for i in range(len(tmp)):
while tmp[i] > 0:
res.append(i+min_num)
tmp[i] -= 1
return res
if __name__ == '__main__':
sample = generateRandomSequence(0, 100)
counting_sorted = countingSort(sample)
testSorted(counting_sorted)
桶排序
核心思想
基数排序的优化版，将每个数据放到一个桶里(桶是均匀分割的数据范围)，然后再对每个桶分别排序，递归地完成上述一系列操作。
Python实现
def bucketSort(nums, bucketSize):
if len(nums) < 2:
return nums
max_num, min_num = max(nums), min(nums)
bucketNum = (max_num-min_num) // bucketSize + 1
buckets = [[] for _ in range(bucketNum)]
for num in nums:
buckets[(num-min_num) // bucketSize].append(num)
res = []
for bucket in buckets:
if not bucket:
continue
if bucketSize == 1: # 如果桶间隔为1，等价于计数排序，直接扩展
res.extend(bucket)
else:
if bucketNum == 1: # 如果桶数为1，说明间隔过大
bucketSize -= 1
res.extend(bucketSort(bucket, bucketSize))
return res
if __name__ == '__main__':
sample = generateRandomSequence(0, 100)
bucket_sorted = bucketSort(sample, 5)
testSorted(bucket_sorted)
总结
这十个常用的排序算法各有优劣，需要针对特定的环境自行选择，但毫无疑问，性价比最高的还是快排。