Python實現(xiàn)快速排序的方法詳解

更新時間：2019年10月25日 11:40:26 作者：鯨落丶

這篇文章主要介紹了Python實現(xiàn)快速排序的方法,結(jié)合實例形式詳細(xì)分析了快速排序的思路、原理及Python具體實現(xiàn)技巧與相關(guān)操作注意事項,需要的朋友可以參考下

本文實例講述了Python實現(xiàn)快速排序的方法。分享給大家供大家參考，具體如下：

說起快排的Python實現(xiàn)，首先談一下，快速排序的思路：

1、取一個參考值放到列表中間，初次排序后，讓左側(cè)的值都比他小，右側(cè)的值，都比他大。

2、分別對左側(cè)和右側(cè)的部分遞歸第1步的操作

實現(xiàn)思路：

兩個指針left，right分別指向列表的第一個元素和最后一個元素，然后取一個參考值，默認(rèn)為第一個列表的第一個元素list[0]，稱為K
然后left指向的值先和參考值K進(jìn)行比較，若list[left]小于或等于K值，left就一直向右移動，left+1，直到移動到大于K值的地方，停住
right指向的值和參考值K進(jìn)行比較，若list[right]大于K值，right就一直向左移動，right-1，直到移動到小于K值的地方，停住
此時，left和right若還沒有相遇，即left還小于right，則二者指向的值互換
若已經(jīng)相遇則說明，第一次排序已經(jīng)完成，將list[right]與list[0]的值進(jìn)行互換，進(jìn)行之后的遞歸

編程實現(xiàn)：

#快排的主函數(shù)，傳入?yún)?shù)為一個列表，左右兩端的下標(biāo)
def QuickSort(list,low,high):
  if high > low:
    #傳入?yún)?shù)，通過Partitions函數(shù)，獲取k下標(biāo)值
    k = Partitions(list,low,high)
    #遞歸排序列表k下標(biāo)左側(cè)的列表
    QuickSort(list,low,k-1)
    # 遞歸排序列表k下標(biāo)右側(cè)的列表
    QuickSort(list,k+1,high)
def Partitions(list,low,high):
  left = low
  right = high
  #將最左側(cè)的值賦值給參考值k
  k = list[low]
  #當(dāng)left下標(biāo)，小于right下標(biāo)的情況下，此時判斷二者移動是否相交，若未相交，則一直循環(huán)
  while left < right :
    #當(dāng)left對應(yīng)的值小于k參考值，就一直向右移動
    while list[left] <= k:
      left += 1
    # 當(dāng)right對應(yīng)的值大于k參考值，就一直向左移動
    while list[right] > k:
      right = right - 1
    #若移動完，二者仍未相遇則交換下標(biāo)對應(yīng)的值
    if left < right:
      list[left],list[right] = list[right],list[left]
  #若移動完，已經(jīng)相遇，則交換right對應(yīng)的值和參考值
  list[low] = list[right]
  list[right] = k
  #返回k值
  return right
list_demo = [6,1,2,7,9,3,4,5,10,8]
print(list_demo)
QuickSort(list_demo,0,9)
print(list_demo)

運行結(jié)果：