Python排序算法之快速排序

快速排序(quickSort)

快排的思想：首先任意選取一個數據(通常選用數組的第一個數)作為關鍵數據，然后將所有比它小的數都放到它前面，所有比它大的數都放到它后面，這個過程稱為一趟快速排序。

百度百科給的算法：

一趟快速排序的算法是：

1)設置兩個變量i、j，排序開始的時候：i=0，j=N-1；

2)以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；

3)從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個小于key的值A[j]，將A[j]和A[i]互換；

4)從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個大于key的A[i]，將A[i]和A[j]互換；

5)重復第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束)。

時間復雜度：O(nlgn)

# -*- coding: UTF-8 -*-

def QuickSort(myList, start, end):

# 判斷low是否小于high,如果為false,直接返回

if start < end:

i, j = start, end

# 設置基準數

base = myList[i]

while i < j:

# 如果列表后邊的數,比基準數大或相等,則前移一位直到有比基準數小的數出現

while (i < j) and (myList[j] >= base):

j = j - 1

# 同樣的方式比較前半區

while (i < j) and (myList[i] <= base):

i = i + 1

myList[i], myList[j] = myList[j], myList[i]

# 做完第一輪比較之后,列表被分成了兩個半區,并且i=j,需要將這個數設置回base

myList[i] = base

# 遞歸前后半區

QuickSort(myList, start, i - 1)

QuickSort(myList, j + 1, end)

return myList

myList = [49, 38, 65, 97, 76, 13, 27, 49]

print("Quick Sort: ")

QuickSort(myList, 0, len(myList)-1)

print(myList)

總結

以上是生活随笔為你收集整理的python写快排_python 实现快速排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。