快捷導(dǎo)航

python快速排序的實(shí)現(xiàn)及運(yùn)行時(shí)間比較

更新時(shí)間：2019年11月22日 09:24:14 作者：西西嘛呦

這篇文章主要介紹了python快速排序的實(shí)現(xiàn)及運(yùn)行時(shí)間比較，本文通過兩種方法給大家介紹，大家可以根據(jù)自己需要選擇適合自己的方法,對(duì)python實(shí)現(xiàn)快速排序相關(guān)知識(shí)感興趣的朋友一起看看吧

快速排序的基本思想：首先選定一個(gè)數(shù)組中的一個(gè)初始值，將數(shù)組中比該值小的放在左邊，比該值大的放在右邊，然后分別對(duì)左邊的數(shù)組進(jìn)行如上的操作，對(duì)右邊的數(shù)組進(jìn)行如上的操作。（分治+遞歸）

1.利用匿名函數(shù)lambda

匿名函數(shù)的基本用法func_name = lambda x:array，冒號(hào)左邊的x代表傳入的參數(shù)，冒號(hào)右邊的array代表返回值，當(dāng)然名字是可以自己取的。

quick_sort = lambda array: \
  array if len(array) <= 1 \
    else quick_sort([item for item in array[1:] if item <= array[0]]) \
       + [array[0]] + \
       quick_sort([item for item in array[1:] if item > array[0]])

2.將匿名函數(shù)拆解封裝為函數(shù)

def func2(array):
  if len(array)<=1:
    return array
  tmp = array[0]
  left = [x for x in array[1:] if x<=tmp]
  right = [x for x in array[1:] if x>tmp]
  return func2(left) + [tmp] + func2(right)

3.網(wǎng)上常見的

def func2(array,left,right):
  if left>=right:
    return
  low=left
  high=right
  tmp=array[low]
  while left<right:
    while left<right and array[right]>tmp:
      right-=1
    array[left] = array[right]
    while left<right and array[left]<=tmp:
      left+=1
    array[right]=array[left]
  array[right]=tmp
  func2(array,low,left-1)
  func2(array,left+1,high)

4.算法導(dǎo)論里面的

def func3(array, l, r):
  if l < r:
    q = partition(array, l, r)
    func3(array, l, q - 1)
    func3(array, q + 1, r)
def partition(array, l, r):
  x = array[r]
  i = l - 1
  for j in range(l, r):
    if array[j] <= x:
      i += 1
      array[i], array[j] = array[j], array[i]
  array[i + 1], array[r] = array[r], array[i + 1]
  return i + 1

5.利用棧實(shí)現(xiàn)非遞歸版本

def func4(array, l, r):
  if l >= r:
    return
  stack = []
  stack.append(l)
  stack.append(r)
  while stack:
    low = stack.pop(0)
    high = stack.pop(0)
    if high - low <= 0:
      continue
    x = array[high]
    i = low - 1
    for j in range(low, high):
      if array[j] <= x:
        i += 1
        array[i], array[j] = array[j], array[i]
    array[i + 1], array[high] = array[high], array[i + 1]
    stack.extend([low, i, i + 2, high])

6.python內(nèi)置的

sorted(array)

本來是想利用裝飾器來測(cè)一下每個(gè)函數(shù)的運(yùn)行時(shí)間的，但是由于快排里面存在遞歸，使用裝飾器會(huì)報(bào)錯(cuò)，就只好一個(gè)個(gè)計(jì)算了。這里還是貼一下用裝飾器計(jì)算時(shí)間的代碼：

def count_time(func):
  @wraps(func)
  def helper(func,*args,**kwargs):
    start=time()
    result = func(*args,**kwargs)
    end=time()
    print("函數(shù)：", func.__name__, "運(yùn)行時(shí)間：", round(end - start, 4), "s")
    return result
  return helper

這里我們的輸入是隨機(jī)生成的在0-100間的整數(shù)，我們測(cè)試一下在不同數(shù)量下的消耗時(shí)間：

from functools import wraps
from random import randint
from time import time
func1_start =time()
res = quick_sort(array)
func1_end =time()
print("函數(shù)：func1 運(yùn)行時(shí)間：", round(func1_end - func1_start, 4), "s")
func2_start =time()
func2(array)
func2_end =time()
print("函數(shù)：func2 運(yùn)行時(shí)間：", round(func2_end - func2_start, 4), "s")
func3_start =time()
func3(array,0,len(array)-1)
func3_end =time()
print("函數(shù)：func3 運(yùn)行時(shí)間：", round(func3_end - func3_start, 4), "s")
func4_start =time()
func4(array,0,len(array)-1)
func4_end =time()
print("函數(shù)：func4 運(yùn)行時(shí)間：", round(func4_end - func4_start, 4), "s")
func5_start =time()
func5(array,0,len(array)-1)
func5_end =time()
print("函數(shù)：func5 運(yùn)行時(shí)間：", round(func5_end - func5_start, 4), "s")
func6_start =time()
sorted(array)
func6_end =time()
print("函數(shù)：func6 運(yùn)行時(shí)間：", round(func6_end - func6_start, 4), "s")

輸入array的定義：

array = [randint(0,100) for i in range(5000)]

需要注意的是，隨著數(shù)據(jù)量的增加，方法4，也就是算法導(dǎo)論中的會(huì)出現(xiàn)以下問題：

這是因?yàn)閜ython中的遞歸深度是有一定限制的，可以使用如下方法暫時(shí)解決該問題：

import sys
sys.setrecursionlimit(100000)

同時(shí)，方法4還會(huì)出現(xiàn)內(nèi)存溢出問題，方法4也太坑了。

最后對(duì)比一下這些方法消耗的時(shí)間：

總結(jié)：

方法一、方法二速度較快，同時(shí)也較好理解，想要學(xué)會(huì)快速排序，只要記住方法二即可；

python內(nèi)置的排序速度還是最快的呀；

以上所述是小編給大家介紹的python快速排序的實(shí)現(xiàn)及運(yùn)行時(shí)間比較，希望對(duì)大家有所幫助，如果大家有任何疑問請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
如果你覺得本文對(duì)你有幫助，歡迎轉(zhuǎn)載，煩請(qǐng)注明出處，謝謝！

您可能感興趣的文章: