簡介
快速排序被評(píng)為20世紀(jì)十大算法之一，最早由圖靈獎(jiǎng)獲得者Tony Hoare設(shè)計(jì)出來查排，很牛凳枝。。跋核。
基本思想
（摘抄自《大話數(shù)據(jù)結(jié)構(gòu)》）
快速排序的基本思想是：
通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分岖瑰，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序砂代，以帶到整個(gè)序列有序的目的蹋订。
Python實(shí)現(xiàn)
以下給出Python實(shí)現(xiàn)版本，結(jié)合打印信息應(yīng)該就能看明白了刻伊。
遞歸版本
# coding=utf-8
'''遞歸版本
'''
def swap(lst, left, right):
lst[left], lst[right] = lst[right], lst[left]
def paritition(lst, left, right):
key = lst[left]
while left < right:
if left < right and key <= lst[right]:
right = right - 1
swap(lst, left, right)
if left < right and lst[left] <= key:
left = left + 1
swap(lst, left, right)
print 'left: {} right: {}'.format(left, right)
print lst
return left
def Qsort(lst, left, right):
piviot = 0
if left < right:
piviot = paritition(lst, left, right)
Qsort(lst, left, piviot - 1)
Qsort(lst, piviot + 1, right)
def Quicksort(lst):
Qsort(lst, 0, len(lst) - 1)
l = [1, 20, 3, 50, 40, 70, 23, 100, 23]
Quicksort(l)
Console輸出：
left: 0 right: 0
[1, 20, 3, 50, 40, 70, 23, 100, 23]
left: 2 right: 2
[1, 3, 20, 50, 40, 70, 23, 100, 23]
left: 6 right: 6
[1, 3, 20, 23, 40, 23, 50, 100, 70]
left: 3 right: 3
[1, 3, 20, 23, 40, 23, 50, 100, 70]
left: 5 right: 5
[1, 3, 20, 23, 23, 40, 50, 100, 70]
left: 8 right: 8
[1, 3, 20, 23, 23, 40, 50, 70, 100]
非遞歸版本
'''非遞歸版本 （區(qū)別僅為Qsort方法露戒，使用棧來保存中間結(jié)果），python3 執(zhí)行
'''
def swap(lst, left, right):
lst[left], lst[right] = lst[right], lst[left]
def paritition(lst, left, right):
key = lst[left]
while left < right:
if left < right and key <= lst[right]:
right = right - 1
swap(lst, left, right)
if left < right and lst[left] <= key:
left = left + 1
swap(lst, left, right)
print('left: {} right: {} lst: {}'.format(left, right, lst))
return left
def Qsort(lst, left, right):
piviots = [(left, right)]
while len(piviots) > 0:
piviot = piviots.pop(0)
if piviot[0] < piviot[1]:
piviot_num = paritition(lst, piviot[0], piviot[1])
if piviot_num - 1 > piviot[0]:
piviots.append((piviot[0], piviot_num-1))
if piviot_num + 1 < piviot[1]:
piviots.append((piviot_num+1, piviot[1]))
def Quicksort(lst):
Qsort(lst, 0, len(lst) - 1)
if __name__ == "__main__":
ll = [1, 20, 3, 50, 40, 70, 23, 100, 23]
Quicksort(ll)
