快速排序算法，簡(jiǎn)稱(chēng)快排，是最實(shí)用的排序算法，沒(méi)有之一，各大語(yǔ)言標(biāo)準(zhǔn)庫(kù)的排序函數(shù)也基本都是基于快排實(shí)現(xiàn)的。

本文用python語(yǔ)言介紹四種不同的快排實(shí)現(xiàn)。

1. 一行代碼實(shí)現(xiàn)的簡(jiǎn)潔版本

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. 網(wǎng)上常見(jiàn)的快排實(shí)現(xiàn)

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

由于快排是原地排序，因此不需要返回array。

array如果是個(gè)列表的話，可以通過(guò)len(array)求得長(zhǎng)度，但是后邊遞歸調(diào)用的時(shí)候必須使用分片，而分片執(zhí)行的原列表的復(fù)制操作，這樣就達(dá)不到原地排序的目的了，所以還是要傳上邊界和下邊界的。

3.《算法導(dǎo)論》中的快排程序

def quick_sort(array, l, r):
  if l < r:
    q = partition(array, l, r)
    quick_sort(array, l, q - 1)
    quick_sort(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

這個(gè)版本跟上個(gè)版本的不同在于分片過(guò)程不同，只用了一層循環(huán)，并且一趟就完成分片，相比之下代碼要簡(jiǎn)潔的多了。

4. 用棧實(shí)現(xiàn)非遞歸的快排程序

先說(shuō)兩句題外話，一般意義上的棧有兩層含義，一層是后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)棧，一層是指函數(shù)的內(nèi)存棧，歸根結(jié)底，函數(shù)的內(nèi)存棧的結(jié)構(gòu)就是一個(gè)后進(jìn)先出的棧。匯編代碼中，調(diào)用一個(gè)函數(shù)的時(shí)候，修改的也是堆棧指針寄存器ESP，該寄存器保存的是函數(shù)局部棧的棧頂，另外一個(gè)寄存器EBP保存的是棧底。不知道與棧存儲(chǔ)空間相對(duì)的堆存儲(chǔ)空間，其組織結(jié)構(gòu)是否也是一個(gè)完全二叉樹(shù)呢？

高級(jí)語(yǔ)言將遞歸轉(zhuǎn)換為迭代，用的也是棧，需要考慮兩個(gè)問(wèn)題:

1）棧里邊保存什么？

2）迭代結(jié)束的條件是什么？

棧里邊保存的當(dāng)然是需要迭代的函數(shù)參數(shù)，結(jié)束條件也是跟需要迭代的參數(shù)有關(guān)。對(duì)于快速排序來(lái)說(shuō)，迭代的參數(shù)是數(shù)組的上邊界low和下邊界high，迭代結(jié)束的條件是low == high。

def quick_sort(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])

另外，當(dāng)數(shù)組下標(biāo)為-1時(shí)，C++、Java等語(yǔ)言中會(huì)報(bào)錯(cuò)，但python中訪問(wèn)的是最后一個(gè)元素，所以如果程序?qū)戝e(cuò)了，可能其他語(yǔ)言會(huì)報(bào)錯(cuò)，但python會(huì)輸出一個(gè)錯(cuò)誤的結(jié)果。

以上所述是小編給大家介紹的python實(shí)現(xiàn)快速排序算法詳解整合，希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！

最新評(píng)論