?

目錄

一、代碼

二、復雜度：O(nlog(n))

三、快速排序的劣勢

---

視頻參考鏈接：https://www.bilibili.com/video/BV1mp4y1D7UP?p=17

一、代碼

'''
思想：假設是對一個list進行排序
1、選取第一個元素作為p元素；
2、將p元素歸位，即將小于p元素的元素放在列表左邊，將大于p元素的元素放在列表右邊
3、通過2實現了p元素的歸位，這樣就將列表分成了兩個子列表，對左右兩個子列表重復使用1、2步驟，實現快速排序
'''
import timedef partition1(li:list,left:int,right:int)->int:'''這是根據路飛商城的思路來的將p元素歸位的函數：取第一個元素為p元素，移動right，若right指針的值大于P,則right繼續往左移動，否則停止移動，將值賦值給left所在的位置；然后再移動left，若left指針的值小于P,則left繼續往右移動，否則停止移動，將值賦值給right所在的位置；如此交替移動，直到left=right時，停止，并將P值賦值給left（right）:param li: 需要歸位的列表:param left: 列表左指針索引，初始值為0:param right: 列表右指針索引，初始值為len(li）-1:return: 返回p歸位的索引'''#得到要歸位的元素（第一個元素）p = li[left]#當列表有兩個元素時，才進行排序while left < right:# 保證有兩個元素#這里我們從列表的右邊開始進行元素的比較while left < right and p <= li[right]: # 至少兩個元素并且p元素值小于等于right指針指向的值時，右指針左移right -= 1 # right 左移一步li[left] = li[right] # 不滿足上述循環條件時，停止移動right，并且將right上的值賦值給left#右指針停止移動后，開始進行左指針的移動while left < right and p >= li[left]:left += 1li[right] = li[left]#當left = right時，說明已經歸位了，將p賦值給歸位位置li[left] = preturn leftdef quickSorted1(li,left,right):'''對列表進行快排:param li: 需要排序的列表:param left: 左索引:param right: 右索引:return: 返回排好序的列表'''if left < right:mid = partition1(li, left, right)  # 首先得到第一個歸位索引# 對左邊列表進行排序quickSorted1(li,left,mid-1)# 對右邊列表進行排序quickSorted1(li,mid + 1,right)#-----------------------------------------------------------------------def partition2(li,left,right):'''這個的主要思路是自己的思路主要思路就是左右交替進行比較,然后將沒有元素的位置賦值為None，如當p>右指針的值時，先將right的值賦值給left，再將right值賦值為None，:param li: :param left: :param right: :return: '''p = li[left]li[left] = Nonewhile left < right:if li[left] == None: # 若檢測到左指針為空時if p > li[right]: # 若p元素大于right指向的值時li[left] = li[right] # 將right值賦值給leftli[right] = None # 此時right為空print(li,"right")else:right -= 1 # 若p元素小于right值，則right左移else:if p < li[left]: # 若p元素小于left指向的值時li[right] = li[left] # 將left值賦值給rightli[left] = None # 此時left為空print(li, "left")else:left += 1 # 若p元素大于left值，則left右移li[left] = preturn leftdef quickSorted2(li,left,right):'''對列表進行快排:param li: 需要排序的列表:param left: 左索引:param right: 右索引:return: 返回排好序的列表'''if left < right:mid = partition2(li, left, right)  # 首先得到第一個歸位索引# 對左邊列表進行排序quickSorted2(li,left,mid-1)# 對右邊列表進行排序quickSorted2(li,mid + 1,right)li = [5,7,4,6,3,1,2,9,8]
startTime1 = time.time()
quickSorted1(li,0,len(li)-1)
endTime1 = time.time()
print(li,"method1")
print("method1用時：%9f"%(endTime1-startTime1))#-----------------------------------------------------startTime2 = time.time()
quickSorted2(li,0,len(li)-1)
endTime2 = time.time()
print(li,"method2")
print("method2用時：%9f"%(endTime2-startTime2))

二、復雜度：O(nlog(n))

當需要排序的元素個數少的時候，二者的運算速度沒有什么區別，但是當數字為10000的時候，就會發生比較大的差別

第一種方法：0.04897332191467285

第二種方法：直接就報遞歸棧溢出的錯誤了。。。“進程已結束,退出代碼-1073741571 (0xC00000FD)”

三、快速排序的劣勢

1、對于Python會有遞歸最大深度的限制

2、在對一組倒序的列表進行正序時，其復雜度接近于O(n^2)

解決方法：

a、每一次隨機從列表中抽取一個元素作為p元素；

b、在進行排序前，先打亂列表再進行排序，這其實是很奇妙的，通過打亂順序來提高效率，第一次聽說，但是它就是達到了這種效果，amazing~