python八大排序算法速度实例对比

这篇文章并不是介绍排序算法原理的，纯粹是想比较一下各种排序算法在真实场景下的运行速度。

算法由 Python 实现，可能会和其他语言有些区别，仅当参考就好。

测试的数据是自动生成的，以数组形式保存到文件中，保证数据源的一致性。

排序算法

直接插入排序

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定

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

希尔排序

时间复杂度：O(n)
空间复杂度：O(n√n)
稳定性：不稳定

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

简单选择排序

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定

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

堆排序

时间复杂度：O(nlog₂n)
空间复杂度：O(1)
稳定性：不稳定

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

冒泡排序

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定

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

快速排序

时间复杂度：O(nlog₂n)
空间复杂度：O(nlog₂n)
稳定性：不稳定

def quick_sort(array):  def recursive(begin, end):    if begin > end:      return    l, r = begin, end    pivot = array[l]    while l < r:      while l < r and array[r] > pivot:        r -= 1      while l < r and array[l] <= pivot:        l += 1      array[l], array[r] = array[r], array[l]    array[l], array[begin] = pivot, array[l]    recursive(begin, l - 1)    recursive(r + 1, end)  recursive(0, len(array) - 1)  return array