設(shè)定一個(gè)中間值，如下所示:

low從開始位置找low是找比54小的，26比54小合格 ?high是從末尾位置找比54大的，如下所示:

low和high重合后第一輪循環(huán)結(jié)束

第一輪遞歸后的結(jié)果如下所示:

還需要處理值相等的情況，如下所示:

比如有一個(gè)值是54(也可能是多個(gè))，正好跟中間值也就是基準(zhǔn)值相等，解決思路就是54在一邊出現(xiàn)(或者說在一邊處理)，不是左邊出現(xiàn)就是右邊出現(xiàn)，把等于這個(gè)情況放到一邊去處理,不是在low這邊就是在high這邊。

上面的high繼續(xù)左移的時(shí)候，high和low就重合了。

上面的起始位置是動(dòng)態(tài)的，不是固定的0，low-1這樣的

代碼如下所示:

# coding=utf-8 def quick_sort(alist,first,last):"""快速排序"""if first >= last: #這兩個(gè)相等表示有一個(gè)元素，則終止循環(huán)即可。return#n = len(alist)#mid_value = alist[0]# low = 0# high = n - 1mid_value = alist[first]low = firsthigh = last#high對(duì)應(yīng)的值大于中間值的時(shí)候,high需要往左走，即high-=1,走到什么時(shí)候呢？即low和high沒有相遇的時(shí)候，high的值需要一直走，所以外面又加了一層循環(huán) while low<high:#流程是交替進(jìn)行的，先是high走，high走完了然后是low走，然后又是high走，即左移右移左移依次交替進(jìn)行,所以外面還需要套一層交替進(jìn)行的代碼while low<high:#這個(gè)是high往左移動(dòng)過程的代碼#中間值解決思路就是中間值54在一邊出現(xiàn)(或者說在一邊處理)，不是左邊出現(xiàn)就是右邊出現(xiàn)。 #把等于這個(gè)情況放到一邊去處理,不是在low這邊就是在high這邊，所以下面的alist[high] >= mid_value加了一個(gè)等號(hào)while low < high and alist[high] >= mid_value:high -= 1#代碼修改了一下，high往左移動(dòng)，跳出while循環(huán)的時(shí)候，可以查看一下while循環(huán)的條件，可能是high往左走的過程中遇到了比中間值小或者等于中間值的情況，則需要把high的值賦予到low上面,low上面存的是比中間值小的數(shù)值alist[low] = alist[high]#low+=1 #因?yàn)閘ow里面的值比中間值小，所以low需要加1，這樣寫有可能會(huì)錯(cuò)過low和high重合的情況，注釋掉# 這個(gè)是low往右邊移動(dòng)過程的代碼while low<high and alist[low]<mid_value:low+=1alist[high] = alist[low]#high -= 1，這樣寫有可能會(huì)錯(cuò)過low和high重合的情況，注釋掉#從循環(huán)退出時(shí),low == highalist[low] = mid_value#對(duì)low左邊的列表執(zhí)行快速排序#這塊low-1減的時(shí)候有可能比first小，所以停止執(zhí)行的條件我們修改為first>=lastquick_sort(alist,first,low-1)# 對(duì)low右邊的列表執(zhí)行快速排序quick_sort(alist,low+1,last) if __name__ == "__main__":li = [54, 26, 93, 17, 77, 31, 44, 55, 20]print(li)quick_sort(li, 0, len(li)-1)print(li) """ [54, 26, 93, 17, 77, 31, 44, 55, 20] [17, 20, 26, 31, 44, 54, 55, 77, 93] """

?

總結(jié)

以上是生活随笔為你收集整理的python算法与数据结构-快速排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。