jake1036

My Links

Blog Stats

Posts - 101
Stories - 0
Comments - 23
Trackbacks - 0

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

閱讀排行榜

評論排行榜

快速排序新算法

快速排序

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 )