使用python實現四種快速排序

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

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

1. 一行代碼實現的簡潔版本

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 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)求得長度，但是后邊遞歸調用的時候必須使用分片，而分片執行的原列表的復制操作，這樣就達不到原地排序的目的了，所以還是要傳上邊界和下邊界的。

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

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

4. 用棧實現非遞歸的快排程序

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

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

1）棧里邊保存什么？

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

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

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

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