python八大排序算法速度實(shí)例對(duì)比

更新時(shí)間：2017年12月06日 17:00:05 作者：woider

這篇文章主要介紹了Python八大排序算法速度實(shí)例對(duì)比，具有一定參考價(jià)值，需要的朋友可以參考下。

這篇文章并不是介紹排序算法原理的，純粹是想比較一下各種排序算法在真實(shí)場(chǎng)景下的運(yùn)行速度。

算法由 Python 實(shí)現(xiàn)，可能會(huì)和其他語(yǔ)言有些區(qū)別，僅當(dāng)參考就好。

測(cè)試的數(shù)據(jù)是自動(dòng)生成的，以數(shù)組形式保存到文件中，保證數(shù)據(jù)源的一致性。

排序算法

直接插入排序

時(shí)間復(fù)雜度：O(n²)
空間復(fù)雜度：O(1)
穩(wěn)定性：穩(wěn)定

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

希爾排序

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n√n)
穩(wěn)定性：不穩(wě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

簡(jiǎn)單選擇排序

時(shí)間復(fù)雜度：O(n²)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定

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

堆排序

時(shí)間復(fù)雜度：O(nlog₂n)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定

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

冒泡排序

時(shí)間復(fù)雜度：O(n²)
空間復(fù)雜度：O(1)
穩(wěn)定性：穩(wěn)定

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

快速排序

時(shí)間復(fù)雜度：O(nlog₂n)
空間復(fù)雜度：O(nlog₂n)
穩(wěn)定性：不穩(wě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

歸并排序

時(shí)間復(fù)雜度：O(nlog₂n)
空間復(fù)雜度：O(1)
穩(wěn)定性：穩(wěn)定

def merge_sort(array):
  def merge_arr(arr_l, arr_r):
    array = []
    while len(arr_l) and len(arr_r):
      if arr_l[0] <= arr_r[0]:
        array.append(arr_l.pop(0))
      elif arr_l[0] > arr_r[0]:
        array.append(arr_r.pop(0))
    if len(arr_l) != 0:
      array += arr_l
    elif len(arr_r) != 0:
      array += arr_r
    return array

  def recursive(array):
    if len(array) == 1:
      return array
    mid = len(array) // 2
    arr_l = recursive(array[:mid])
    arr_r = recursive(array[mid:])
    return merge_arr(arr_l, arr_r)

  return recursive(array)

基數(shù)排序

時(shí)間復(fù)雜度：O(d(r+n))
空間復(fù)雜度：O(rd+n)
穩(wěn)定性：穩(wěn)定

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

速度比較

from random import random
from json import dumps, loads
# 生成隨機(jī)數(shù)文件
def dump_random_array(file='numbers.json', size=10 ** 4):
  fo = open(file, 'w', 1024)
  numlst = list()
  for i in range(size):
    numlst.append(int(random() * 10 ** 10))
  fo.write(dumps(numlst))
  fo.close()
# 加載隨機(jī)數(shù)列表
def load_random_array(file='numbers.json'):
  fo = open(file, 'r', 1024)
  try:
    numlst = fo.read()
  finally:
    fo.close()
  return loads(numlst)

from _datetime import datetime
# 顯示函數(shù)執(zhí)行時(shí)間
def exectime(func):
  def inner(*args, **kwargs):
    begin = datetime.now()
    result = func(*args, **kwargs)
    end = datetime.now()
    inter = end - begin
    print('E-time:{0}.{1}'.format(
      inter.seconds,
      inter.microseconds
    ))
    return result
  return inner

如果數(shù)據(jù)量特別大，采用分治算法的快速排序和歸并排序，可能會(huì)出現(xiàn)遞歸層次超出限制的錯(cuò)誤。

解決辦法：導(dǎo)入 sys 模塊（import sys），設(shè)置最大遞歸次數(shù)（sys.setrecursionlimit(10 ** 8)）。

@exectime
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
array = load_random_array()
print(bubble_sort(array) == sorted(array))

↑ 示例：測(cè)試直接插入排序算法的運(yùn)行時(shí)間，@exectime 為執(zhí)行時(shí)間裝飾器。

算法執(zhí)行時(shí)間