快速排序
1 該快速排序以末尾值為基準(zhǔn)值，進(jìn)行排序。
【 p，i】之間的數(shù)均小于a[r] ，
（i-j） 之間的數(shù)均大于a[r] ，
【j---r）之間的數(shù)未確定
2 代碼如下：
#include <iostream>
/**//*
【 p，i】之間的數(shù)均小于a[r]
（i-j） 之間的數(shù)均大于a[r]
【j---r）之間的數(shù)未確定
*/
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++) //當(dāng)a[j] > a[r] 時(shí)，只需要增加j的值
{ //當(dāng)a[j] <= a[r]時(shí)，首先自增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 以數(shù)組首數(shù)字為基準(zhǔn)值的快排
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 ;
}
注意：循環(huán)內(nèi)的兩個(gè)子循環(huán)的判斷條件，均有 i <= j 的條件。
因?yàn)?i 與 j 必然有重合的一次，若沒(méi)有重合，則j就不會(huì)有小于i的情況。
注意 返回j的值。 第二種方法只需要交換一次。