快速排序不同于之前了解的分治，他是通過一系列操作劃分得到子問題，不同之前的劃分子問題很簡(jiǎn)單，劃分子問題的過程也是解決問題的過程

我們通常劃分子問題盡量保持均衡，而快排缺無(wú)法保持均衡

快排第一種劃分子問題實(shí)現(xiàn)方式，左右填空的雙指針方式

def partition_1(arr,low,high):# 把基準(zhǔn)元素取出來，留出一個(gè)空位，這里是在首位，這種留出空位的方式，比較容易理解pivot = arr[low]# 循環(huán)體終止條件，因?yàn)槭窍茸哂疫呍僮咦筮?#xff0c;終止的時(shí)候一定是兩個(gè)指針重合在一起# 也可以交叉，但是可以控制循環(huán)他們重合在一起跳出循環(huán)# 這里解釋以下low,high這兩個(gè)指針代表什么，low，high代表從其實(shí)到low都是小于基準(zhǔn)的元素# 從high到end都是大于基準(zhǔn)的元素，當(dāng)low和high重合時(shí)，那左邊都是小的，右邊都是大的# 重合的位置是空的（實(shí)際上有值），因?yàn)槊總€(gè)時(shí)刻都有一個(gè)位置都是空的，重合剩下最后一個(gè)位置，# 這個(gè)位置也必然是空的，也可以用一個(gè)小的實(shí)例分析一下while low < high:# 首先右邊一直往左走，直到遇到小于基準(zhǔn)的元素，這里控制一下，不讓他們交叉# 不添加的low <high，往左走不會(huì)越界，但是可能小于lowwhile arr[high] > pivot and low <high:high -=1# 避免他們兩交叉，只要相等就退出，右邊遇到小于基準(zhǔn)的元素，把左邊的那個(gè)空位填上，左邊的指針更新一下 if low <high: arr[low] = arr[high]low +=1# 左指針往左就是小于基準(zhǔn)的元素，這時(shí)右邊空出來一個(gè)位置，左指針往右掃描while arr[low] < pivot and low <high:low +=1# 找到大于基準(zhǔn)的元素，放到右邊空出來的位置，那右指針往右全部都是大于基準(zhǔn)元素的if low <high: arr[high] = arr[low]high -=1# 當(dāng)只剩下唯一的空位置時(shí)，把基準(zhǔn)元素放待空的位置上 arr[low] = pivotreturn low

快排第二種劃分子問題方式，單指針方式

def partition_2(arr,low,high):# 這時(shí)另外一種考慮方式，而且他是不需要額外空間的，他只使用一個(gè)指針來區(qū)分小于基準(zhǔn)和大于基準(zhǔn)的# pointer_less_than代表這個(gè)指針的左邊全部都是小于基準(zhǔn)的（包括自己，不包括首元素）# 然后從左往右掃描，遇到小于基準(zhǔn)的元素，就把小于基準(zhǔn)元素區(qū)域的后面緊接著的一個(gè)元素和他交換# 那么小于基準(zhǔn)元素區(qū)域就多了一個(gè)元素，。。。就這樣小于基準(zhǔn)的元素就連在了一起# 首元素是基準(zhǔn)元素，小于基準(zhǔn)元素區(qū)域塊，大于基準(zhǔn)元素區(qū)域塊，現(xiàn)在分成了三個(gè)部分# 把首元素和小于基準(zhǔn)元素區(qū)域塊最后一個(gè)元素交換，那三部分就變成，小于的，基準(zhǔn)，大于的# 剛開始小于基準(zhǔn)的元素為0，暫且指向首位值pointer_less_than = low# 然后一次掃描后面所有元素for i in range(pointer_less_than +1,high+1):# 遇到小于基準(zhǔn)的，就把小于基準(zhǔn)元素區(qū)域的后面緊接著的一個(gè)元素和他交換，小于的塊相當(dāng)于也更新了if arr[i] < arr[low] :pointer_less_than +=1arr[pointer_less_than],arr[i]=arr[i],arr[pointer_less_than]# 把首元素和小于基準(zhǔn)元素區(qū)域塊最后一個(gè)元素交換，那三部分就變成，小于的，基準(zhǔn)，大于的 arr[low],arr[pointer_less_than] = arr[pointer_less_than],arr[low]return pointer_less_than

第三種劃分子問題實(shí)現(xiàn)方式，左右同時(shí)交換,這種方式注意結(jié)束的情況

def partition_3(arr,start,end):# 這個(gè)方式也是不需要額外的輔助空間的# 他的思想是：從左（或者右也可以）掃描到第一個(gè)大于基準(zhǔn)的元素，然后從右往左掃描到第一個(gè)小于基準(zhǔn)的# 元素，將他們兩交換，然后再重復(fù)上述操作，直到兩個(gè)指針重合位置# 這兩個(gè)指針分別代表：前面（除了首元素）到low為小于基準(zhǔn)，high到end為大于基準(zhǔn)元素# 他們是可能會(huì)交叉的，也有可能重合，這時(shí)數(shù)組分成三個(gè)部分：首元素基準(zhǔn)，小于的，大于的# 這個(gè)地方可能會(huì)交叉的，也有可能重合，分3種情況：第一種情況[大于,小于]，然后他們兩個(gè)交換# [小于，大于]，low-->大于，high-->小于，這時(shí)首元素需要和high互換# [小于]，high-->小于，沒有大于的元素和他互換，low一直加直到等于high,這時(shí)這時(shí)首元素需要和high互換# [大于]，low-->大于，沒有小于的元素和他互換，high會(huì)一直減，直到比low小1，這時(shí)這時(shí)這時(shí)首元素需要和high互換# 不管是那種情況下，high指向肯定是最后一個(gè)小于基準(zhǔn)的元素 # 這里不能利用兩者指針重合，因?yàn)閮蓚€(gè)指針重合指向的元素，可能大于基準(zhǔn)也可能小于基準(zhǔn)，# 要使用high指向的元素# 初始化左指針和右指針low = starthigh = end +1# 循環(huán)體退出條件為兩指針重合或者交叉while True:# 需要先-1，因?yàn)榻粨Q之后，指針需要更新一下，不更新的話，循環(huán)體會(huì)多運(yùn)算一步high -=1# 這里就是需要兩指針交叉，這樣high才能指向小于區(qū)域里面的最后一個(gè)元素while arr[high] > arr[start] :high -=1low +=1 while arr[low] < arr[start] and low < end:low +=1# 在這個(gè)時(shí)候，數(shù)組分成三個(gè)部分：首元素是基準(zhǔn)元素，小于基準(zhǔn)元素區(qū)域塊，大于基準(zhǔn)元素區(qū)域塊if low >= high:break# 把這兩個(gè)元素交換，小的跑到左邊，大的跑到右邊arr[low],arr[high] = arr[high],arr[low]# 把首元素和小于基準(zhǔn)元素區(qū)域塊最后一個(gè)元素交換，那三部分就變成，小于的，基準(zhǔn)，大于的arr[start],arr[high] = arr[high],arr[start]return high

運(yùn)行結(jié)果

#%% def quickSort(arr,low,high): if low < high:index = partition_1(arr,low,high)quickSort(arr,low,index-1)quickSort(arr,index+1,high)def quickSort1(arr,low,high): if low < high:index = partition_2(arr,low,high)quickSort1(arr,low,index-1)quickSort1(arr,index+1,high)def quickSort2(arr,low,high): if low < high:index = partition_3(arr,low,high)quickSort2(arr,low,index-1)quickSort2(arr,index+1,high)arr = [7,3,66,33,22,66,99,0,1] print(arr) quickSort(arr,0,len(arr)-1) print(arr) arr1 = [7,3,66,33,22,66,99,0,1] #print(arr1) quickSort1(arr1,0,len(arr1)-1) print(arr1) arr2 = [7,3,66,33,22,66,99,0,1] #print(arr2) quickSort2(arr2,0,len(arr2)-1) print(arr2) [7, 3, 66, 33, 22, 66, 99, 0, 1] [0, 1, 3, 7, 22, 33, 66, 66, 99] [0, 1, 3, 7, 22, 33, 66, 66, 99] [0, 1, 3, 7, 22, 33, 66, 66, 99]

前面提到快排的劃分不一定是均衡劃分，而快排的效率取決于劃分的對(duì)稱性，稍微改進(jìn)一下為隨機(jī)化算法，這類把某一步修改成隨機(jī)步驟的算法，叫做拉斯維加斯算法

import random def randomizedPartition(arr,low,high):def partition(arr,low,high):# 這時(shí)另外一種考慮方式，而且他是不需要額外空間的，他只使用一個(gè)指針來區(qū)分小于基準(zhǔn)和大于基準(zhǔn)的# pointer_less_than代表這個(gè)指針的左邊全部都是小于基準(zhǔn)的（包括自己，不包括首元素）# 然后從左往右掃描，遇到小于基準(zhǔn)的元素，就把小于基準(zhǔn)元素區(qū)域的后面緊接著的一個(gè)元素和他交換# 那么小于基準(zhǔn)元素區(qū)域就多了一個(gè)元素，。。。就這樣小于基準(zhǔn)的元素就連在了一起# 首元素是基準(zhǔn)元素，小于基準(zhǔn)元素區(qū)域塊，大于基準(zhǔn)元素區(qū)域塊，現(xiàn)在分成了三個(gè)部分# 把首元素和小于基準(zhǔn)元素區(qū)域塊最后一個(gè)元素交換，那三部分就變成，小于的，基準(zhǔn)，大于的# 剛開始小于基準(zhǔn)的元素為0，暫且指向首位值pointer_less_than = low# 然后一次掃描后面所有元素for i in range(pointer_less_than +1,high+1):# 遇到小于基準(zhǔn)的，就把小于基準(zhǔn)元素區(qū)域的后面緊接著的一個(gè)元素和他交換，小于的塊相當(dāng)于也更新了if arr[i] < arr[low] :pointer_less_than +=1arr[pointer_less_than],arr[i]=arr[i],arr[pointer_less_than]# 把首元素和小于基準(zhǔn)元素區(qū)域塊最后一個(gè)元素交換，那三部分就變成，小于的，基準(zhǔn)，大于的 arr[low],arr[pointer_less_than] = arr[pointer_less_than],arr[low]return pointer_less_thanindex = random.randint(low,high)arr[low],arr[index]=arr[index],arr[low]return partition(arr,low,high)def randomizedQuicksort(arr,low,high):if low < high:index = randomizedPartition(arr,low,high)randomizedQuicksort(arr,low,index-1)randomizedQuicksort(arr,index+1,high)arr3 = [7,3,66,33,22,66,99,0,1] print(arr3) randomizedQuicksort(arr3,0,len(arr3)-1) print(arr3) [7, 3, 66, 33, 22, 66, 99, 0, 1] [0, 1, 3, 7, 22, 33, 66, 66, 99]

快排快，還是歸并排序快？

按照理論上分析，快排平均時(shí)間復(fù)雜度O（nlogn）,最壞為n^2,歸并平均和最壞均為nlogn。
理論上應(yīng)該是歸并快才對(duì)，但是有好多人測(cè)試很大規(guī)模數(shù)據(jù)的情況下快排比歸并快。
可能的原因，歸并有空間開銷，有數(shù)組復(fù)制合并的操作，快排屬于原地排序，在數(shù)據(jù)規(guī)模大的情況下，差距就出來了。

總結(jié)

以上是生活随笔為你收集整理的分治法：快速排序，3种划分方式，随机化快排，快排快，还是归并排序快？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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