欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python八大排序算法速度實例對比

 更新時間:2017年12月06日 17:00:05   作者:woider  
這篇文章主要介紹了Python八大排序算法速度實例對比,具有一定參考價值,需要的朋友可以參考下。

這篇文章并不是介紹排序算法原理的,純粹是想比較一下各種排序算法在真實場景下的運行速度。

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

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

排序算法

直接插入排序

時間復(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

希爾排序

時間復(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

簡單選擇排序

時間復(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

堆排序

時間復(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

冒泡排序

時間復(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

快速排序

時間復(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

歸并排序

時間復(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ù)排序

時間復(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
# 生成隨機數(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()
# 加載隨機數(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í)行時間
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ù)量特別大,采用分治算法的快速排序和歸并排序,可能會出現(xiàn)遞歸層次超出限制的錯誤。

解決辦法:導(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))

↑ 示例:測試直接插入排序算法的運行時間,@exectime 為執(zhí)行時間裝飾器。

算法執(zhí)行時間

算法速度比較

總結(jié)

以上就是本文關(guān)于Python八大排序算法速度實例對比的全部內(nèi)容,希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站:

Python3簡單實例計算同花的概率代碼

Python語言描述最大連續(xù)子序列和

Python實現(xiàn)調(diào)度算法代碼詳解

如有不足之處,歡迎留言指出。感謝朋友們對本站的支持!

相關(guān)文章

  • Python字符串格式化輸出代碼實例

    Python字符串格式化輸出代碼實例

    這篇文章主要介紹了Python字符串格式化輸出代碼實例,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2019-11-11
  • 學(xué)會Python數(shù)據(jù)可視化必須嘗試這7個庫

    學(xué)會Python數(shù)據(jù)可視化必須嘗試這7個庫

    數(shù)據(jù)可視化是使用一些繪圖和圖形更詳細地理解數(shù)據(jù)的過程.最著名的庫之一是 matplotlib,它可以繪制幾乎所有您可以想象的繪圖類型.matplotlib 唯一的問題是初學(xué)者很難掌握.在本文中,我將介紹七個數(shù)據(jù)可視化庫,你可以嘗試使用它們來代替 matplotlib ,需要的朋友可以參考下
    2021-06-06
  • Python pandas用法最全整理

    Python pandas用法最全整理

    在本篇文章里小編給大家分享的是關(guān)于Python pandas用法以及相關(guān)實例代碼,需要的朋友們可以學(xué)習(xí)下。
    2019-08-08
  • python 統(tǒng)計代碼耗時的幾種方法分享

    python 統(tǒng)計代碼耗時的幾種方法分享

    本文實例講述了Python中統(tǒng)計代碼片段、函數(shù)運行耗時的幾種方法,分享給大家,僅供參考。
    2021-04-04
  • python math模塊的基本使用教程

    python math模塊的基本使用教程

    這篇文章主要介紹了python math模塊的基本使用教程,幫助大家更好的理解和使用python,感興趣的朋友可以了解下
    2021-01-01
  • Windows系統(tǒng)下cython_bbox庫的正確安裝步驟

    Windows系統(tǒng)下cython_bbox庫的正確安裝步驟

    Cython-bbox一般無法直接通過pip直接安裝,那么如何安裝呢?下面這篇文章主要給大家介紹了關(guān)于Windows系統(tǒng)下cython_bbox庫的正確安裝步驟,文中通過圖文介紹的非常詳細,需要的朋友可以參考下
    2023-05-05
  • python中__init__方法知識點詳解

    python中__init__方法知識點詳解

    Python中常會看到在很多類中都有一個__init__函數(shù),該函數(shù)有什么作用,又該如何使用呢,下面這篇文章主要給大家介紹了關(guān)于python中__init__知識點的相關(guān)資料,需要的朋友可以參考下
    2023-04-04
  • Python隨機生成均勻分布在三角形內(nèi)或者任意多邊形內(nèi)的點

    Python隨機生成均勻分布在三角形內(nèi)或者任意多邊形內(nèi)的點

    這篇文章主要為大家詳細介紹了Python隨機生成均勻分布在三角形內(nèi)或者任意多邊形內(nèi)的點,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2017-12-12
  • python+mediapipe+opencv實現(xiàn)手部關(guān)鍵點檢測功能(手勢識別)

    python+mediapipe+opencv實現(xiàn)手部關(guān)鍵點檢測功能(手勢識別)

    這篇文章主要介紹了python+mediapipe+opencv實現(xiàn)手部關(guān)鍵點檢測功能(手勢識別),本文僅僅簡單介紹了mediapipe的使用,而mediapipe提供了大量關(guān)于圖像識別等的方法,需要的朋友可以參考下
    2022-01-01
  • 用python 繪制莖葉圖和復(fù)合餅圖

    用python 繪制莖葉圖和復(fù)合餅圖

    這篇文章主要介紹了用python 繪制莖葉圖和復(fù)合餅圖,幫助大家更好的理解和學(xué)習(xí)使用python,感興趣的朋友可以了解下
    2021-02-02

最新評論