DDR爱好者之家

python八大排序算法速度实例对比
站长资源 2024/11/26 佚名
65 1538
DDR爱好者之家 Design By 杰米

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

算法由 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"htmlcode"> 

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"htmlcode"> 

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

归并排序

时间复杂度：O(nlog"htmlcode"> 

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)

基数排序

时间复杂度：O(d(r+n))
空间复杂度：O(rd+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
# 生成随机数文件
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()
# 加载随机数列表
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
# 显示函数执行时间
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

如果数据量特别大，采用分治算法的快速排序和归并排序，可能会出现递归层次超出限制的错误。

解决办法：导入 sys 模块（import sys），设置最大递归次数（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))

↑ 示例：测试直接插入排序算法的运行时间，@exectime 为执行时间装饰器。

算法执行时间

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

算法速度比较

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

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

总结

以上就是本文关于Python八大排序算法速度实例对比的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站：

Python3简单实例计算同花的概率代码

Python语言描述最大连续子序列和

Python实现调度算法代码详解

如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

DDR爱好者之家 Design By 杰米
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
DDR爱好者之家 Design By 杰米
ddrfans.com DDR爱好者之家
8,675无损音乐
1,324高清电影
213破解软件
70,141收录资讯

稳了！魔兽国服回归的3条重磅消息！官宣时间再确认！

昨天有一位朋友在大神群里分享，自己亚服账号被封号之后居然弹出了国服的封号信息对话框。

这里面让他访问的是一个国服的战网网址，com.cn和后面的zh都非常明白地表明这就是国服战网。

而他在复制这个网址并且进行登录之后，确实是网易的网址，也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情，因为以前都没有出现这样的情况，现在突然提示跳转到国服战网的网址，是不是说明了简体中文客户端已经开始进行更新了呢？

更新日志

友情链接

杰晶网络 DDR爱好者之家 南强小屋 黑松山资源网 白云城资源网
DDR爱好者之家 Design By 杰米