1.說明

這個快速排序算法是對前面的?快速排序算法QuickSort??一種改進。

只是修改了int Partition(int arry[],int start,int end)這個方法。

2.思路

仔細觀察我們可以發(fā)現(xiàn)，我們前面Partition方法中，都需要swap(arry,start,end)，?但是這一步中有些步驟是可以省略的。?

在（<-end）過程中，碰到第一個小于等于pivot的元素時，只需要進行一次賦值arry[start]=arry[end];?因為當(dāng)前的arry[start]是值就是pivot?；

在（start->）過程中，碰到第一個大于等于pivot的元素之，只需要進行一次賦值arry[end]=arry[start];?因為當(dāng)前的arry[end]的值就是pivot的值。

整個過程中，不是start就是end指向pivot所存儲的單元?，所以在整個過程中，pivot沒有必要每次通過swap來保存，只需要在最后找到pivotkey的時候，?令arry[pivotkey]=pivot即可。?

具體修改如下代碼實例。

3.改進的快速排序QuickSort

View Code

PS：2012-5-4

今天發(fā)現(xiàn)以前一直以為對的快排寫錯了，因此沒有考慮需要排序的數(shù)相等的情況，如果排序的數(shù)組中有相同的數(shù)，那么就會出現(xiàn)死循環(huán)，一直沒有結(jié)果，要做的修改就是修改Partition函數(shù)，修改以后如下：

View Code

做的唯一修改就是將原來的arry[end]>pivot改為arry[end]>=pivot，arry[start]<pivot改為arry[start]<=pivot

快排練習(xí)（PS：2012-10-2）

View Code

?

本文轉(zhuǎn)自xwdreamer博客園博客，原文鏈接：http://www.cnblogs.com/xwdreamer/archive/2011/06/16/2296999.html，如需轉(zhuǎn)載請自行聯(lián)系原作者

總結(jié)

以上是生活随笔為你收集整理的快速排序算法QuickSort（二）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。