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

1.利用匿名函數lambda

匿名函數的基本用法func_name  = lambda x:array，冒號左邊的x代表傳入的參數，冒號右邊的array代表返回值，當然名字是可以自己取的。

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.將匿名函數拆解封裝為函數

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.網上常見的

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.算法導論里面的

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.利用棧實現非遞歸版本

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內置的

sorted(array)

本來是想利用裝飾器來測一下每個函數的運行時間的，但是由于快排里面存在遞歸，使用裝飾器會報錯，就只好一個個計算了。這里還是貼一下用裝飾器計算時間的代碼：

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

這里我們的輸入是隨機生成的在0-100間的整數，我們測試一下在不同數量下的消耗時間：

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