級(jí)別： ★☆☆☆☆
標(biāo)簽：「算法」「D&C」「quickSort」
作者： MrLiuQ
審校： QiShare團(tuán)隊(duì)
前一篇介紹了遞歸與尾遞歸捂龄，本篇將基于遞歸介紹快速排序等相關(guān)內(nèi)容光绕。
閱讀本文你將收獲：
- 分而治之思想：簡(jiǎn)稱
D&C谱秽，一種遞歸式解決問題方案咧最。 - 快速排序：利用
D&C思想于未，實(shí)現(xiàn)的一種高效排序方法莱褒。
一、“分而治之”思想（D&C）
分而治之：（
divide and conquer做盅，D&C）是一種著名的遞歸式解決問題的方法乖杠。
某一種解決問題的算法用處有限萝毛，而D&C為我們提供的是一種思路。
當(dāng)我們面對(duì)一個(gè)復(fù)雜問題手足無措時(shí)滑黔，我們應(yīng)該自問：“D&C能解決該問題么？”
那么环揽，D&C是什么略荡？
1.1 什么是D&C？
使用D&C解決問題的過程分為兩個(gè)步驟：
- 找出基線條件歉胶，這個(gè)條件盡可能簡(jiǎn)單汛兜。（基線條件的定義見上篇）
- 不斷將問題分解（縮小規(guī)模），直到全部符合基線條件通今。
1.2 D&C的實(shí)例
場(chǎng)景：假設(shè)你是一位農(nóng)場(chǎng)主粥谬，你有一塊長方形（168m x 64m）的地。
問題：現(xiàn)在你需要把這塊地分成若干個(gè)正方形的地（方便管理和種菜）辫塌，問最大能拆分成多大的小正方形漏策。（注意：不能留空地哦，最大利用土地資源）
方案一：找出“長”和“寬”中臼氨，相同的最大的公約數(shù)即可掺喻。（我的第一反應(yīng)是這樣算）
方案二：使用D&C思想，先從大長方形中去掉幾個(gè)最大的正方形储矩，再去掉小長方形的幾個(gè)最大正方形感耙，不斷尋找，直到?jīng)]有小長方形為止持隧。
步驟：
- 找到基線條件：長是寬的整數(shù)倍
- 不斷分解：去除所有最大正方形后即硼，對(duì)小長方形進(jìn)行分解
圖解如圖：
第一次：找到兩個(gè)邊長為64m的大正方形，去除后屡拨，留下64m x 40m的小長方形只酥。
第二次：找到一個(gè)邊長為40m的小正方形褥实，去除后，留下40m x 24m的小長方形层皱。
第三次：找到一個(gè)邊長為24m的小正方形性锭，去除后，留下24m x 16m的小長方形叫胖。
第四次：找到一個(gè)邊長為16m的小正方形草冈，取出后，留下16m x 8m的小長方形瓮增。
第五次：找到兩個(gè)邊長為8m的小正方形怎棱，正好分完。
因此绷跑，該農(nóng)場(chǎng)分為小正方形田地的最大邊長為8m拳恋。
而這個(gè)解決問題的思想，就是D&C思想砸捏。
我們?cè)賮砘仡櫼幌翫&C思想的核心：
- 找出簡(jiǎn)單的基線條件谬运。
- 確定如何縮小問題的規(guī)模，使其符合基線條件垦藏。
二梆暖、快速排序
快速排序（QuickSort）利用的就是D&C思想。它是一種高效的排序方案掂骏。
2.1 快排的思想（基于D&C）
- 基線條件：當(dāng)排序數(shù)組元素個(gè)數(shù)小于2個(gè)時(shí)轰驳，直接返回。
- 縮小規(guī)模：每次從待排序數(shù)組中選取一個(gè)元素（基準(zhǔn)值）弟灼，把小于等于該元素的元素放在一側(cè)级解，把大于該元素的元素放在另一側(cè)。再對(duì)兩邊的小數(shù)組做重復(fù)操作田绑。
2.2 快排的示例
基于Python勤哗，實(shí)現(xiàn)了一個(gè)快排：
代碼如下：
def quickSort(arr):
if len(arr) < 2:
return arr
else:
pivot = arr[0]
less = [i for i in arr[1:] if i <= pivot]
greater = [i for i in arr[1:] if i > pivot]
return quickSort(less) + [pivot] + quickSort(greater)
print quickSort([10, 2, 6, 4, 7, 2])
解讀一下代碼：
PS：基準(zhǔn)值一般可以選取第一個(gè)元素，也可以選擇最后一個(gè)元素掩驱。
2.3 快排的動(dòng)畫演示
本Demo中俺陋，選取的數(shù)組的最后一個(gè)元素為基準(zhǔn)值，把小于等于基準(zhǔn)值的元素放在左側(cè)昙篙，大于基準(zhǔn)值的元素放在右側(cè)腊状。
推薦文章：
iOS 避免常見崩潰（二）
算法小專欄：選擇排序
iOS Runloop（一）
iOS 常用調(diào)試方法：LLDB命令
iOS 常用調(diào)試方法：斷點(diǎn)
iOS 常用調(diào)試方法：靜態(tài)分析
iOS 消息轉(zhuǎn)發(fā)
