快速排序新算法

快速排序

1 該快速排序以末尾值為基準值，進行排序。

     【 p，i】之間的數均小于a[r] ，
      （i-j）之間的數均大于a[r]   ，
    【j---r）之間的數未確定

2 代碼如下：

#include <iostream>

【 p，i】之間的數均小于a[r]

（i-j）之間的數均大于a[r]

【j---r）之間的數未確定

using namespace std ;

int partition(int * a , int p , int r) ;

void qsort(int * a , int p , int n) ;

int main()

{

int a [] = {13 , 19 ,9 ,5 , 12 , 8 , 7 ,4 ,21 , 2 , 6 , 11} ;

int x = partition(a , 0 ,11) ;

cout<<"pos:"<<x<<endl;

qsort(a , 0 , 11) ;

for(int i = 0 ; i < 12 ; i++)

cout<<a[i]<<" " ;

cin.get() ;

return 0 ;

}

int partition(int * a , int p , int r)

{

int i = p - 1 , j;

for(j = p ; j < r ;j++) //當a[j] > a[r] 時，只需要增加j的值

{ //當a[j] <= a[r]時，首先自增i的值，然后交換a[j]與a[i]，最后自增i的值

if(a[j] <= a[r])

{

i++ ;

swap(a[i] , a[j]) ;

}

swap(a[i + 1] , a[r]) ;

return i + 1 ;

}

void qsort(int * a , int p , int n)

{

if(p < n)

{

int q = partition(a , p , n);

qsort(a , p , q - 1) ;

qsort(a , q + 1 , n) ;

}

2 以數組首數字為基準值的快排

int beginPartition(int * a , int p , int q)

{

int i = p ;

int j = q ;

int x = a[p] ;

while(i <= j)

{

while(i <= j && a[i] <= x ) i++;

while(i <= j && a[j] >= x ) j-- ;

if(i < j )

swap(a[i] , a[j]) ;

}

return j ;

}

注意：循環內的兩個子循環的判斷條件，均有 i <= j 的條件。
因為 i 與 j 必然有重合的一次，若沒有重合，則j就不會有小于i的情況。

注意返回j的值。第二種方法只需要交換一次。

posted on 2011-04-01 19:59 kahn 閱讀(212) 評論(0) 編輯收藏引用所屬分類: 算法相關

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 9-24MTK一面二面微軟筆試總結 2011-09-07xx移動創業公司筆試題編程之美2.7 最大公約數 O(n)實現刪除兩個數組中的共同元素編程之美1.9(二) 高效率地安排會面分組背包問題（六）二維背包問題（五）多重背包（三）完全背包問題 <二>

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

快速排序新算法

快速排序