排序是老生常谈了，但是不写来了又总会忘记。之前写过用C++实现的少部分排序，这一次写一下Python实现的八大排序。
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 插入排序 | O(n²) | O(n) | O(n²) | O(1) | In-place | 稳定 |
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | In-place | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | In-place | 不稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | In-place | 不稳定 |
| 希尔排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | In-place | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | In-place | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | Out-place | 稳定 |
直接插入排序：
def insert_sort(array): for i in range(len(array)): for j in range(i): if array[i] < array[j]: array.insert(j, array.pop(i)) break return array
希尔排序：
def shell_sort(array): gap = len(array) while gap > 1: gap = gap // 2 for i in range(gap, len(array)): for j in range(i % gap, i, gap): if array[i] < array[j]: array[i], array[j] = array[j], array[i] return array
选择排序：
def select_sort(array): for i in range(len(array)): x = i # min index for j in range(i, len(array)): if array[j] < array[x]: x = j array[i], array[x] = array[x], array[i] return array
堆排序：
def heap_sort(nums): # 调整堆 # 迭代写法 def adjust_heap(nums, startpos, endpos): newitem = nums[startpos] pos = startpos childpos = pos * 2 + 1 while childpos < endpos: rightpos = childpos + 1 if rightpos < endpos and nums[rightpos] >= nums[childpos]: childpos = rightpos if newitem < nums[childpos]: nums[pos] = nums[childpos] pos = childpos childpos = pos * 2 + 1 else: break nums[pos] = newitem # 递归写法 def adjust_heap(nums, startpos, endpos): pos = startpos chilidpos = pos * 2 + 1 if chilidpos < endpos: rightpos = chilidpos + 1 if rightpos < endpos and nums[rightpos] > nums[chilidpos]: chilidpos = rightpos if nums[chilidpos] > nums[pos]: nums[pos], nums[chilidpos] = nums[chilidpos], nums[pos] adjust_heap(nums, pos, endpos)
def heap_sort(array): def heap_adjust(parent): child = 2 * parent + 1 # left child while child < len(heap): if child + 1 < len(heap): if heap[child + 1] > heap[child]: child += 1 # right child if heap[parent] >= heap[child]: break heap[parent], heap[child] = heap[child], heap[parent] parent, child = child, 2 * child + 1 heap, array = array.copy(), [] for i in range(len(heap) // 2, -1, -1): heap_adjust(i) while len(heap) != 0: heap[0], heap[-1] = heap[-1], heap[0] array.insert(0, heap.pop()) heap_adjust(0) return array
冒泡排序：
def bubble_sort(array): for i in range(len(array)): for j in range(i, len(array)): if array[i] > array[j]: array[i], array[j] = array[j], array[i] return array
快速排序：
def Quick_sort(num_list): ''' 快速排序，时间复杂度：O(nlog₂n)，空间复杂度：O(nlog₂n)，不是稳定排序 ''' if len(num_list)<2: return num_list left_list = [] #存放比基准结点小的元素 right_list = [] #存放比基准元素大的元素 base_node = num_list.pop(0) #在这里采用pop()方法的原因就是需要移除这个基准结点，并且赋值给base_node这个变量 #在这里不能使用del()方法，因为删除之后无法再赋值给其他变量使用，导致最终数据缺失 #快排每轮可以确定一个元素的位置，之后递归地对两边的元素进行排序 for one_num in num_list: if one_num < base_node: left_list.append(one_num) else: right_list.append(one_num) return Quick_sort(left_list) + [base_node] + Quick_sort(right_list)
归并排序：
def merge_sort(nums): if len(nums) <= 1: return nums mid = len(nums) // 2 # 分 left = merge_sort(nums[:mid]) right = merge_sort(nums[mid:]) # 合并 return merge(left, right) def merge(left, right): res = [] i = 0 j = 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
基数排序：
def radix_sort(array): bucket, digit = [[]], 0 while len(bucket[0]) != len(array): bucket = [[], [], [], [], [], [], [], [], [], []] for i in range(len(array)): num = (array[i] // 10 ** digit) % 10 bucket[num].append(array[i]) array.clear() for i in range(len(bucket)): array += bucket[i] digit += 1 return array
参考：
Python 实现七大排序算法
https://juejin.im/post/6844903873392410631
leetcode
Python 八大排序算法速度比较