快速排序解釋

快速排序 Quick Sort 與歸併排序一樣，也是典型的分治法的應用。 (如果有對 歸併排序還不瞭解的童鞋，可以看看這裡喲~ 歸併排序)❤❤❤

快速排序的分治模式

1、選取基準值，獲取劃分位置。將原陣列 a[l, r] 劃分為兩個子陣列 a[l, mid - 1] 和 a[mid + 1, r]。在前一個陣列中所有元素都小於等於 a[mid]，後一個陣列中所有元素都大於等於 a[mid]。而此時的 a[mid] 的值就是我們所取的基準值，mid 就每次劃分的位置；

2、遞迴呼叫快速排序函數，分別對兩個子陣列 a[l, mid - 1] 和 a[mid + 1, r] 排序；

3、快速排序我們是在原陣列上進行操作的，所以我們並不需要合併，最後 a[l, r] 已經有序。

快速排序的三種寫法

快速排序比較普及的有三種寫法，分別是 左右指標法 挖坑法 和 前後指標法。主要是取得劃分位置實現的方法有所不同。
接下來會逐個介紹這三種快速排序的寫法。

左右指標法

左右指標法步驟

1、首先 我們一般選取最左邊的元素作為基準值 key。

2、然後我們需要定義兩個變數 i 和 j。
其中 i 為左指標(其實不是指標啦，只是為了方便這麼叫它