精通八大排序算法系列一快速排序算法(7)

完。一月五日补充。

OK,上述俩种算法，明白一种即可。

-------------------------------------------------------------

五、快速排序的最坏情况和最快情况。

最坏情况发生在划分过程产生的俩个区域分别包含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^2）。

因此，如果在算法的每一层递归上，划分都是最大程度不对称的，那么算法的运行时间就是O（n^2）。 亦即，快速排序算法的最坏情况并不比插入排序的更好。

此外，当数组完全排好序之后，快速排序的运行时间为O（n^2）。

而在同样情况下，插入排序的运行时间为O（n）。

//注，请注意理解这句话。我们说一个排序的时间复杂度，是仅仅针对一个元素的。

//意思是，把一个元素进行插入排序，即把它插入到有序的序列里，花的时间为n。

再来证明，最快情况下，即PARTITION可能做的最平衡的划分中，得到的每个子问题都不能大于n/2. 因为其中一个子问题的大小为|_n/2_|。另一个子问题的大小为|-n/2-|-1.

在这种情况下，快速排序的速度要快得多。为，

T(n)<=2T（n/2）+O（n）.可以证得，T（n）=O（nlgn）。

直观上，看，快速排序就是一颗递归数，其中，PARTITION总是产生9:1的划分，

总的运行时间为O（nlgn）。各结点中示出了子问题的规模。每一层的代价在右边显示。 每一层包含一个常数c。

=============================================

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库精通八大排序算法系列一快速排序算法(7)在线全文阅读。