Python實現快速排序的方法詳解

 更新時間:2019年10月25日 11:40:26   作者:鯨落丶   我要評論
這篇文章主要介紹了Python實現快速排序的方法,結合實例形式詳細分析了快速排序的思路、原理及Python具體實現技巧與相關操作注意事項,需要的朋友可以參考下

本文實例講述了Python實現快速排序的方法。分享給大家供大家參考,具體如下:

說起快排的Python實現,首先談一下,快速排序的思路:

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

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

實現思路:

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

編程實現:

#快排的主函數,傳入參數為一個列表,左右兩端的下標
def QuickSort(list,low,high):
  if high > low:
    #傳入參數,通過Partitions函數,獲取k下標值
    k = Partitions(list,low,high)
    #遞歸排序列表k下標左側的列表
    QuickSort(list,low,k-1)
    # 遞歸排序列表k下標右側的列表
    QuickSort(list,k+1,high)
def Partitions(list,low,high):
  left = low
  right = high
  #將最左側的值賦值給參考值k
  k = list[low]
  #當left下標,小于right下標的情況下,此時判斷二者移動是否相交,若未相交,則一直循環
  while left < right :
    #當left對應的值小于k參考值,就一直向右移動
    while list[left] <= k:
      left += 1
    # 當right對應的值大于k參考值,就一直向左移動
    while list[right] > k:
      right = right - 1
    #若移動完,二者仍未相遇則交換下標對應的值
    if left < right:
      list[left],list[right] = list[right],list[left]
  #若移動完,已經相遇,則交換right對應的值和參考值
  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)

運行結果:

[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

PS:這里再為大家推薦一款關于排序的演示工具供大家參考:

在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具:
http://tools.jb51.net/aideddesign/paixu_ys

更多關于Python相關內容感興趣的讀者可查看本站專題:《Python數據結構與算法教程》、《Python列表(list)操作技巧總結》、《Python編碼操作技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程

希望本文所述對大家Python程序設計有所幫助。

相關文章

最新評論

福建体育彩票时时彩11