快速排序

快速排序是在等待排序的n個記錄中隨機取出一個元素作為基準，比基準小的元素放到基準左邊，比基準大的放到基準的右邊。

然后分別對基準兩邊的子序列進行上一步的操作。遞歸的進行，直到排序完成。

可以設置兩個游標分別對序列左右兩端的元素進行跟蹤。以方便和基準比較大小進行移動。

?

?

如圖所示，low 和 heigh分別代表序列的兩端。

設置兩個游標，初始值均放在兩端。

假設我們取得 基準元素就是該序列的最后一個元素 ，將其放在 一個臨時變量上 如：temp ?temp=4?

游標 i 的作用自左向右移動，找出比基準大的元素，

游標 j 的作用就是自右向左，找到比基準小的元素。

排序開始：
率先移動 i ?發現 i 當前指向的元素為 8 ，且 8>4 因此把 8 放到序列的最右邊，也就是 j 所在的位置。

i 已經找到了比 基準小的元素，并實現了元素的交換，那么 i 就暫時停在此處 ，移動 j?

?

?

j 當前元素為8，8>4 ,向左移動 j ，j = 6 ，6>4，繼續向左移動 j ，j=3 <4, 停止移動 j ，并且把 j 所指向的元素放到 i 的位置，準備移動 i

?

向右移動 i ，i =2， 2<4 , 繼續向右移動，i=7, 7>4，停止移動 i ，并將 i 所指向的元素放到 j 的位置。準備移動 j

?

向左移動 j ，j = 1,1<4, 停止移動 j ?將 j 指向的元素放到 i 的位置。準備移動 i

向右移動 i ，i = 5，5>4 ,停止移動 i， 將 i 所指向的值，放到 j 的位置。向左移動 j?

向左移動 j ，發現 i == j 停止移動 i 和 j ，該位置即為 基準元素應該在的位置。

這就是一趟快排的過程。然后分別對基準左右兩端遞歸的進行上述操作。直至完成。

?

?

?代碼如下：

def quickSort(A,low,heigh):i = low # 初始化 i 位于最左邊j = heigh #初始化 j 位于最右邊if low< heigh:temp = A[j] # 取最右邊為基準while i != j: #只要 i！= j ，就循環的移動 i 和 jwhile i<j and A[i] <=temp: # 只要 i 比 j 小，且 i 所指向的變量小于基準變量，那么就不斷的向右移動 ii +=1A[j]= A[i] #當碰到 比temp 大的變量時，那么就將 當前變量放到 j 所在的位置。while j>i and A[j]>=temp: # 只要 j 比 i 大，且，j 所指向的變量大于 基準變量，那么就不斷向左移動 jj -= 1A[i]=A[j] #直到 碰到比temp 小的變量，那么就向 當前變量放到 i 當前的位置。 A[i] = temp #當 i==j 時，i、j指向了同一個元素。表示i，j都已經對各自半邊遍歷完成，并實現了大小元素間的互換，當前位置即基準變量應該在的位置。quickSort(A,low,i-1) #遞歸的對 A的左半部分進行以上動作，只是此時A的范圍不再是整個序列了，而是 [0 ,i-1] 序列最左邊到基準變量左側元素quickSort(A,i+1,heigh) #遞歸的對A 的有半部分進行上述動作，此時A的范圍為 [i+1,heigh] 基準變量右側到 序列最右邊return AA=[8,2,7,5,1,3,6,4] low=0 heigh = len(A)-1 print(quickSort(A,low,heigh)) View Code

?

轉載于:https://www.cnblogs.com/jijizhazha/p/6121650.html

總結

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

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