快速排序的四種python實現(xiàn)（推薦）

更新時間：2019年04月03日 10:13:37 作者：lookupheaven

這篇文章主要介紹了python實現(xiàn)快速排序算法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

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

本文用python語言介紹四種不同的快排實現(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)求得長度，但是后邊遞歸調用的時候必須使用分片，而分片執(zhí)行的原列表的復制操作，這樣就達不到原地排序的目的了，所以還是要傳上邊界和下邊界的。

3.《算法導論》中的快排程序

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)非遞歸的快排程序

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

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

1）棧里邊保存什么？

2）迭代結束的條件是什么？

棧里邊保存的當然是需要迭代的函數(shù)參數(shù)，結束條件也是跟需要迭代的參數(shù)有關。對于快速排序來說，迭代的參數(shù)是數(shù)組的上邊界low和下邊界high，迭代結束的條件是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])

另外，當數(shù)組下標為-1時，C++、Java等語言中會報錯，但python中訪問的是最后一個元素，所以如果程序寫錯了，可能其他語言會報錯，但python會輸出一個錯誤的結果。

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

您可能感興趣的文章: