使用python實現(xiàn)四種快速排序

這篇文章給大家分享的是有關(guān)使用python實現(xiàn)四種快速排序的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

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

1. 一行代碼實現(xià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)上常見的快排實現(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如果是個列表的話，可以通過len(array)求得長度，但是后邊遞歸調(diào)用的時候必須使用分片，而分片執(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

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

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

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

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

1）棧里邊保存什么？

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

棧里邊保存的當(dāng)然是需要迭代的函數(shù)參數(shù)，結(jié)束條件也是跟需要迭代的參數(shù)有關(guān)。對于快速排序來說，迭代的參數(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時，C++、Java等語言中會報錯，但python中訪問的是最后一個元素，所以如果程序?qū)戝e了，可能其他語言會報錯，但python會輸出一個錯誤的結(jié)果。

感謝各位的閱讀！關(guān)于“使用python實現(xiàn)四種快速排序”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！