演算法設計與分析（3）——快速排序過程、時間複雜度分析及改進
前言
之前介紹的插入排序與氣泡排序演算法存在一個很明顯的問題，就是基於比較和交換的排序策略，從根本上無法對平均時間複雜度進行最佳化，沒有改進的餘地和空間。
但是如果我們摒棄插入排序與氣泡排序的思想，另闢蹊徑是否能夠提升排序效果呢？
答案是肯定的。下面將介紹基於分治策略的兩種排序演算法，分別是快速排序演算法和歸併排序演算法，並對其進行時間複雜度分析和改進。
一、分治策略
首先，我們先了解一下什麼是分治策略。
分治策略：如果一個規模為n的問題，若該問題可以很容易地解決（n較小）時，則直接解決；否則將其分解為k個規模較小的子問題，這些子問題相互獨立且與原問題形式相同，遞迴地解這些子問題，然後將各子問題的解進行合併得到原問題的解。
如果子問題不獨立有公共子問題，那麼我們則使用動態規劃的思想求解該問題。
分治策略分成三個步驟：
分解：將原問題分解為若干個規模較小的子問題，相互獨立，與原問題形式形同的子問題。
解決：若子問題規模較小而容易被解決則直接解決，否則遞迴地解決各個子問題。
合併：將各個子問題的解合併為原問題的解。
分治法步驟
分治法時間複雜度如下
當採用分治法時，
時，時間複雜度等於”分解+解決+組合“三部分的和。
分治與遞迴是一對“孿生兄弟”，經常搭配在一起使用，解決很多問題。
採用分治策略主要有兩種演算法：
快速排序：hard division， easy combination。
歸併排序：easy division， hard combination。
二、快速排序過程
快速排序——圖片來源：https：//blog。csdn。net/engineerhe/article/details/104131452
上圖是一個快速排序演算法的動態演示，略顯抽象，我們可以透過另一幅圖片來看。
快排過程分解——圖片來源：https：//blog。csdn。net/engineerhe/article/details/104131452
上圖的過程是快速排序的基本過程，快排會先選擇一個元素作為樞軸，小的放在他的左邊，大的放在他的右邊，從而經過n-1次比較，將原問題劃分為兩個相同的子問題。進而再對兩個子問題進行相同的求解過程。
示例程式碼如下：
public
class
quicksort
{
public
static
void
Quicksort
（
int
［］
array
，
int
start
，
int
stop
）{
int
m
；
if
（
start
<
stop
）
{
m
=
partition
（
array
，
start
，
stop
）；
Quicksort
（
array
，
start
，
m
-
1
）；
Quicksort
（
array
，
m
+
1
，
stop
）；
}
}
public
static
int
partition
（
int
［］
array
，
int
first
，
int
last
）{
int
tmp
=
array
［
first
］；
while
（
first
<
last
）{
while
（
first
<
last
&&
array
［
last
］>
tmp
）
last
——；
if
（
first
<
last
）
array
［
first
］
=
array
［
last
］；
while
（
first
<
last
&&
array
［
first
］<
tmp
）
first
++；
if
（
first
<
last
）
array
［
last
］
=
array
［
first
］；
}
array
［
first
］=
tmp
；
return
first
；
}
public
static
void
main
（
String
［］
args
）
{
int
［］
array
=
new
int
［］{
6
，
9
，
1
，
10
，
3
，
2
，
8
，
4
，
7
，
5
}；
Quicksort
（
array
，
0
，
array
。
length
-
1
）；
for
（
int
item
：
array
）{
System
。
out
。
println
（
item
）；
}
}
}
三、快排時間複雜度分析
有了程式碼實現，下面我們要進行快排的時間複雜度分析。
還是按照我們的脈絡，先分析最壞情況，再分析最好情況。
最壞情況時間複雜度
最壞情況是選取的樞軸是最小的元素，導致劃分後的問題規模是0和n-1，然後接下來樞軸仍然是最小值。給出一個例子，”1， 2， 3， 4， 5， 6， 7， 8， 9， 10“，假設每次選取第一個元素作為樞軸，那麼這個序列就對應著最壞情況。
我們遞推求得該問題的最壞情況時間複雜度為
。
2。 平均時間複雜度
h設所有的可能的輸入序列都是等可能性出現的。
我們將所有可能的情況加和起來，進一步可以得到
可以透過將上式展開得到下式。
進而我們有兩種方法來得到A（n），一種是估演算法，一種是直接推理法。
①估演算法
估算快排時間複雜度為
根據定理3。7的第二個條件，進而我們可以得到
②直接推理計算
這裡直接給出過程，大家可以按照過程推導一遍，此處並不做特殊要求。
四、快速排序演算法的改進
改進措施：
遞迴：因為遞迴呼叫過程是要消耗計算資源的，因此可以改為非遞迴
小排序問題：小排序可以使用其他排序演算法
樞軸的選取——隨機打亂、隨機選擇等等方法
但是隨機打亂、隨機選擇還是無法避免最壞情況的出現。如果快排策略不改變，無論如何選用樞軸，都存在最壞情況
。
上一篇:身無片瓦，無依弱女何處安身？