000 快速排序算法

一：概述

　　快速排序是東尼.霍爾所發展的一種快速排序算法。

　　對于n個項目的排序，平均O（n*logn）次比較，在比較糟糕的情況下是O（n²）次比較。

　　采用分治策略把一個串行分為兩個子串行。

?

二：步驟

1. 從數列中挑出一個元素，稱為 “基準”（pivot）。

2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。

3. 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

?

三：c語言程序

　　

四：最壞下的時間復雜度

　　假設當劃分區間的時候，一個區間n-1個元素，一個區間有0個元素。

　　并且繼續假設每次遞歸都出現這種情況。

　　劃分的代價是O（n）。

　　對0個元素的遞歸，T（0）=O（1）。

　　所以估計算法的運行時間的遞歸：T（n）=T（n-1）+T（0）+O（n）=T（n-1）+O（n）

　　可以證明T（n）=O（n²）

?

五：最快情況下的時間復雜度

　　劃分的每個區間不能大于n/2。

　　一個區間為n/2,另一個為n/2-1.

　　這種情況下快速算法就快速的多。

　　T（n）<=2T(n/2)+O(n)

　　可以證明T（n）=O（nlgn）。