軟件環(huán)境：Python?3.7.0b4

一、分而治之

工作原理：

• 找出簡(jiǎn)單的基線條件；
• 確定如何縮小問題的規(guī)模，使其符合基線條件。

# 4.2 def count(list):if list == []:return 0return 1 + count(list[1:])# 4.3 def max(list):if len(list) == 2:return list[0] if list[0] > list[1] else list[1]sub_max = max(list[1:])return list[0] if list[0] > sub_max else sub_max

?

4.4：二分查找的基線條件是數(shù)組只包含一個(gè)元素。如果要查找的值與這個(gè)元素相同，就找到了！否則說明它不在數(shù)組中。遞歸條件為 把數(shù)組分成兩半，將其中一半丟棄，并對(duì)另一半執(zhí)行二分查找。

?

二、快速排序

def quicksort(array):if len(array) < 2:# 基線條件：為空或只包含一個(gè)元素的數(shù)組是“有序”的return arrayelse:# 遞歸條件pivot = array[0]# 由所有小于等于基準(zhǔn)值的元素組成的子數(shù)組less = [i for i in array[1:] if i <= pivot]# 由所有大于基準(zhǔn)值的元素組成的子數(shù)組greater = [i for i in array[1:] if i > pivot]return quicksort(less) + [pivot] + quicksort(greater)print(quicksort([10, 5, 2, 3])) # 需排序的數(shù)組

?

?

三、小結(jié)

• 分治法是將問題逐步分解。使用分治法處理列表時(shí)，基線條件很可能是空數(shù)組或只包含一個(gè)元素的數(shù)組。
• 實(shí)現(xiàn)快速排序時(shí)，請(qǐng)隨機(jī)地選擇用作基準(zhǔn)值的元素?？焖倥判虻钠骄\(yùn)行時(shí)間為O(nlog n)。

?

總結(jié)

以上是生活随笔為你收集整理的《算法图解》第四章笔记与课后练习_快速排序算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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