行百裡者半九十，此言得之。
當看完快速排序之後，我了解了它的思想，我也會實作它的代碼，可是，這就是我所需要的quicksort算法嗎？顯然不是。
習題7-1-2問道：如果數組中元素都相同，該怎麼辦？
如果采用僞代碼直接實作的程式，時間複雜度為n的平方；作者提供了思路，當A[p..r]中的元素相同時，傳回的q為(p+r)/2，這樣就能保持最好的性能。
習題7-4-5問道：難道一路quicksort遞歸到底，性能最好嗎？能不能改進？
作者又提供了思路：當輸入數組已經幾乎有序時，插入排序的速度非常快；在實際應用中，我們對一個長度為k的子數組調用快速排序時，讓它直接傳回；最後對整個數組運作插入排序；
習題7-2問道：我們可不可以實作對于A[p..r]調用劃分時，獲得A[p..q-1]小于主元；A[q...t]等于主元；A[t+1..r]大于主元？
習題7-4說：其實消除尾遞歸是能提高程式性能的。。。
習題7-5問：怎麼選擇主元？如果随機選擇實作的太慢，且效果不一定很好；而直接選最後一個元素又太容易出現最壞情況。
作者說：最常用的改進RANDOM-QUICKSORT的方法是：從子數組中更細緻的選擇主元而非随機選擇。常用做法是三數取中法：
從子數組中随機選擇三個元素，取其中位數作為主元；
習題7-6問：其實區間模糊排序也可以采用向quicksort一樣的排序手法，如何寫擴充性好的quicksort算法？
一個算法背後隐藏着這麼多的細節或者說是技巧，雖然我們做題目的時候寫的都是簡單的，不考慮這麼多問題的，但是實際應用中自然是要考慮這些細節的，是以本篇的目的是-------如何實作一個實用的排序算法？
程式說明：取材于STL。命名的規則是：隻在函數中調用而非面向使用者的接口的函數均為 _xxxx（除sort外都是。。）
//----------------------------------------------------------------------------------------------------
//這裡的插入排序跟《算法導論》的僞代碼一緻
//對疊代器[first,last)範圍内的元素按遞增排序
template<typename RandomIterator>
void _insertion_sort(RandomIterator first,RandomIterator last)
{
typedef typename iterator_traits<RandomIterator>::value_type value_type;
if(first==last) return;
for(RandomIterator i=first+1;i!=last;++i){
RandomIterator j=i-1;
value_type key=*i;
while(j>=first && key<*j){
*(j+1)=*j;
--j;
}
*(j+1)=key;
}
}
//對疊代器[first,last)範圍内的元素按函數對象進行排序
template<typename RandomIterator,typename Compare>
void _insertion_sort(RandomIterator first,RandomIterator last,Compare comp)
{
typedef typename iterator_traits<RandomIterator>::value_type value_type;
if(first==last) return;
for(RandomIterator i=first+1;i!=last;++i){
RandomIterator j=i-1;
value_type key=*i;
while(j>=first && comp(key,*j)){
*(j+1)=*j;
--j;
}
*(j+1)=key;
}
}
//-------------------------------------------------------------------------------------------------
quicksort在平均情況下複雜度為O(nlgn)，不過我們這兒采用的改進版的時間複雜度最壞情況下為O(nlgn)
//政策一：三點中值做主元
//三點取中值
template<typename T>
inline const T& _median(const T& a,const T& b,const T& c)
{
if(a<b){
if(b<c)//a<b<c
return b;
else if(a<c) //a<b,a<c,b>=c
return c;
else //a<b,b>=c,a>=c
return a;
}
else if(a<c)//a>b,a<c
return a;
else if(b<c)//a>b,a>c,b<c
return c;
else //a>b,a>c,b>c
return b;
}
//------------------------------------------------------------------------
然後是quicksort的劃分代碼，這裡的劃分實作選擇了《算法導論》書中的僞代碼，而非習題7-1的實作方式（STL中采用的是習題7-1的實作方式）
//------------------------------------------------------------------------
//兩個輔助性工具函數，用于交換兩疊代器所指元素的值
template<typename RandomIterator>
inline void iter_swap(RandomIterator& i,RandomIterator& j)
{
swap(*i,*j);
}
template<typename T>
inline void swap(T& L,T& R)
{
T tmp=R;
R=L;
L=tmp;
}
//--------------------------------------------------------------------------
//--------------------------------------------------------------------------
//partition函數，劃分成兩段[first,i)小于等于pivot[i+1,last)大于等于pivot
template<typename RandomIterator,typename T>
RandomIterator _partition(RandomIterator first,RandomIterator last,T pivot)
{
for(RandomIterator i=first;i!=last;++i){
if(*i==pivot){RandomIterator tmp=last-1;iter_swap(i,tmp);break;}
}
RandomIterator i=first-1;
RandomIterator r=last-1;
for(RandomIterator j=first;j!=r;++j){
if(*j<=pivot){
++i;
iter_swap(i,j);
}
}
++i;
iter_swap(i,r);
return i;
}
//這裡按照傳入的函數對象進行劃分，
//如果傳入的是大于号的話，那麼左邊子數組大于pivot，右邊小于等于pivot
template<typename RandomIterator,typename T,typename Compare>
RandomIterator _partition(RandomIterator first,RandomIterator last,T pivot,Compare comp)
{
for(RandomIterator i=first;i!=last;++i){
if(*i==pivot){RandomIterator tmp=last-1;iter_swap(i,tmp);break;}
}
RandomIterator i=first-1;
RandomIterator r=last-1;
for(RandomIterator j=first;j!=r;++j){
if(comp(*j,pivot)){
++i;
iter_swap(i,j);
}
}
++i;
iter_swap(i,r);
return i;
}
總的程式來了：
//-----------------------------------------------------------------------------------------
//政策二：與插入排序結合使用，如習題7-4-5
//政策三：消除尾遞歸
//政策四：混合式排序：内省式排序；當分割行為有惡化為N^2次行為的傾向時，能夠自我偵測，轉而
//使用堆排序，使效率維持在NlgN
const int threshold=16;//當子數組元素數小于此值時，調用快速排序則直接傳回
//預設情況下按升序排序
template<typename RandomIterator>
inline void sort(RandomIterator first,RandomIterator last)
{
if(first!=last){
//控制遞歸調用的層數最多為__lg(last-first)*2層
_intro_sort(first,last,value_type(first),__lg(last-first)*2);
_insertion_sort(first,last);
}
}
//按照傳入的函數對象進行排序
template<typename RandomIterator,typename Compare>
inline void sort(RandomIterator first,RandomIterator last,Compare comp)
{
if(first!=last){
_intro_sort(first,last,value_type(first),__lg(last-first)*2,comp);
_insertion_sort(first,last,comp);
}
}
//---------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------
//__lg是為了控制分割惡化
//找到2^k<=n的最大k值
//在sort程式中我們傳入__lg(last-first)*2，意為如果元素為40的話，那麼k=5；層數最多為10層
template<typename Size>
inline Size __lg(Size n)
{
Size k;
for(k=0;n>1;n>>=1)++k;
return k;
}
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//按升序排序
template<typename RandomIterator,typename T,typename Size>
void _intro_sort(RandomIterator first,RandomIterator last,T*,Size depth_limit)
{
while(last-first>threshold){
if(depth_limit==0){//分割惡化
_heap_sort(first,last);
return;
}
--depth_limit;
//主元采用三點中值選擇
RandomIterator cut=_partition(first,last,T(_median(*first,
*(first+(last-first)/2),*(last-1))));
//消除尾遞歸
_intro_sort(cut+1,last,value_type(first),depth_limit);
last=cut;
}
}
//按函數對象排序
template<typename RandomIterator,typename T,typename Size,typename Compare>
void _intro_sort(RandomIterator first,RandomIterator last,T*,Size depth_limit,Compare comp)
{
while(last-first>threshold){
if(depth_limit==0){//分割惡化
_heap_sort(first,last,comp);
return;
}
--depth_limit;
//主元采用三點中值選擇
RandomIterator cut=_partition(first,last,T(_median(*first,
*(first+(last-first)/2),*(last-1))),comp);
//消除尾遞歸
_intro_sort(cut+1,last,value_type(first),depth_limit,comp);
last=cut;
}
}
//--------------------------------------------------------------------------------------------
現在的主要程式大綱都基本實作了，但是堆排序又是一個大頭，這裡仍然是采用《算法導論》僞碼：
//------------------------------------------------------------------------------------
//輔助程式
template<typename Size>
inline Size _parent(Size i){return (i-1)>>1;}
template<typename Size>
inline Size _left(Size i){return (i<<1)+1;}
template<typename Size>
inline Size _right(Size i){return (i<<1)+2;}
以下函數都在《算法導論》第六章實作過，可以看看我以前寫的代碼；
//----------------------------------------------------------------------------------------
//保持堆性質，預設最大堆，
template<typename RandomIterator,typename Distance>
void _heapify(RandomIterator first,RandomIterator i,Distance len)
{
Distance i_index=i-first;
Distance largest=i_index;
Distance current_index=i_index;
while(current_index<len){
Distance i_left_child=_left(current_index);
Distance i_right_child=_right(current_index);
if(i_left_child<len&&(*(first+i_left_child)>*(first+current_index))){
largest=i_left_child;
}
if(i_right_child<len &&(*(first+i_right_child)>*(first+largest))){
largest=i_right_child;
}
if(largest!=current_index){
RandomIterator tmp1=first+current_index,tmp2=first+largest;
iter_swap(tmp1,tmp2);
current_index=largest;
}else{
break;
}
}
}
//保持堆性質，按函數對象，如：傳入小于号，那麼就是建立最小堆
template<typename RandomIterator,typename Distance,typename Compare>
void _heapify(RandomIterator first,RandomIterator i,Distance len,Compare comp)
{
Distance i_index=i-first;
Distance compest=i_index;
Distance current_index=i_index;
while(current_index<len){
Distance i_left_child=_left(current_index);
Distance i_right_child=_right(current_index);
if(i_left_child<len&&comp(*(first+i_left_child),*(first+current_index))){
compest=i_left_child;
}
if(i_right_child<len &&comp(*(first+i_right_child),*(first+compest))){
compest=i_right_child;
}
if(compest!=current_index){
RandomIterator tmp1=first+current_index,tmp2=first+compest;
iter_swap(tmp1,tmp2);
current_index=compest;
}else{
break;
}
}
}
//------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------
//對[first,last)建堆，預設為最大堆
template<typename RandomIterator>
inline void build_heap(RandomIterator first,RandomIterator last)
{
typedef iterator_traits<RandomIterator>::difference_type difference_type;
typedef iterator_traits<RandomIterator>::value_type value_type;
if(last-first<2) return;//如果長度為0或1，不必重新排列
difference_type len=last-first;
for(RandomIterator it=first+(len/2)-1;it!=first-1;--it){
_heapify(first,it,len);
}
}
//建堆，按函數對象來建
template<typename RandomIterator,typename Compare>
inline void build_heap(RandomIterator first,RandomIterator last,Compare comp)
{
typedef iterator_traits<RandomIterator>::difference_type difference_type;
typedef iterator_traits<RandomIterator>::value_type value_type;
if(last-first<2) return;//如果長度為0或1，不必重新排列
difference_type len=last-first;
for(RandomIterator it=first+(len/2)-1;it!=first-1;--it){
_heapify(first,it,len,comp);
}
}
//----------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------
//堆排序，預設建立最大堆，按升序排序
template<typename RandomIterator>
void _heap_sort(RandomIterator first,RandomIterator last)
{
typedef iterator_traits<RandomIterator>::difference_type difference_type;
difference_type len=last-first;
build_heap(first,last);
for(difference_type i=len-1;i>=1;--i){
RandomIterator tmp=(first+len-1);
iter_swap(first,tmp);
--len;
_heapify(first,first,len);
}
}
下面是按函數對象版本堆排序的，但是這兒有一些細節，首先對于升序排序，我們傳入小于号，但是我們需要建立最大堆，是以在建堆過程中我們卻需要大于号，這裡需要一個函數對象的取反功能，要對一個函數對象取反（配接器），我們建立配接器需要建立在大家都得遵守的約定上，即定義二進制函數對象時，應該繼承基本的binary_function：
//輔助程式
template<typename Arg1,typename Arg2,typename Result>
struct binary_function
{
typedef Arg1 first_argument_type;
typedef Arg2 second_argument_type;
typedef Result result_type;
};
template<typename Predicate>
class binary_negate :public binary_function<typename Predicate::first_argument_type,
typename Predicate::second_argument_type,bool>
{
protected:
Predicate _pred;
public:
explicit binary_negate(const Predicate& x):_pred(x){ }
bool operator()(const typename Predicate::first_argument_type& x,
const typename Predicate::second_argument_type& y) const
{return !_pred(x,y);}
};
這樣我們使用時，就可以binary_negate<Compare>(comp)對函數對象取反啦
//按函數對象進行堆排序
template<typename RandomIterator,typename Compare>
void _heap_sort(RandomIterator first,RandomIterator last,Compare comp)
{
typedef iterator_traits<RandomIterator>::difference_type difference_type;
difference_type len=last-first;
build_heap(first,last,binary_negate<Compare>(comp));
for(difference_type i=len-1;i>=1;--i){
RandomIterator tmp=(first+len-1);
iter_swap(first,tmp);
--len;
_heapify(first,first,len,binary_negate<Compare>(comp));
}
}
好，如此我們的程式就完成了，這就是使用的快速排序算法！
下面是一些測試：
需要包含的頭檔案：
#include<iostream>
#include<cstdlib>
//升序排列
int main()
{
int A[10];
for(int i=0;i<10;++i){
A[i]=rand()%100;
}
sort(A,A+10);
for(int* it=A;it!=A+10;++it){
std::cout<<*it<<" ";
}
char c=getchar();
}
結果：
首先定義一個大于号的函數對象：
template<typename T>
struct greater :public binary_function<T,T,bool>
{
bool operator()(const T& x,const T& y)const{return x>y;}
};
然後降序排列：
//降序排列
int main()
{
int A[10];
for(int i=0;i<10;++i){
A[i]=rand()%69;
}
sort(A,A+10,greater<int>());
for(int* it=A;it!=A+10;++it){
std::cout<<*it<<" ";
}
char c=getchar();
}
由于我寫的代碼不是很好，是以對于一個可以排序的類至少要定義四種關系操作符：
struct student
{
int id;
char name;
student(int a=0,char b=0):id(a),name(b){ }
bool operator<(const student& r)const{return id<r.id;}
bool operator<=(const student& r)const {return id<=r.id;}
bool operator==(const student& r)const {return id==r.id;}
bool operator>(const student& r)const {return id>r.id;}
};
這裡隻是為了測試，是以student類地設計非常粗糙，隻是為了證明正确性，測試程式也寫得很糟糕。。。。請諒解
：
int main()
{
student A[10];
for(int i=0;i<10;++i){
int x=rand()%120;
A[i].id=x;
A[i].name=x+'a';
}
sort(A,A+10);
for(student* it=A;it!=A+10;++it){
std::cout<<(*it).id<<" ";
}
char c=getchar();
}
最後一個，就是我在第六章的一個問題，對于非常大的衛星資料，對于優先隊列來說，我們更多的是使用句柄（指針）而非直接用資料，是以對于指向某一類型資料的句柄或指針，我們也要讓他能夠在優先隊列中工作，借此契機，我用heap_sort來說明，我對于這個問題的解法。。我覺得應該把這個問題轉移到句柄的設計而非是優先隊列的設計。
如果student是非常大的資料類型，那麼我在優先隊列中處理的是指向student的句柄，如何讓這個句柄工作，這個問題的解答和如何讓student句柄在堆排序算法中工作是一樣的。
我定義了指向student的句柄---疊代器，再次聲明，疊代器設計的非常糟糕，隻是為了測試正确性。。。。
struct student_iter
{
student* p;
student_iter():p(0){}
student_iter(student* x):p(x){ }
student_iter(const student_iter& x):p(x.p){ }
student_iter& operator=(student_iter& x){p=(x.p);return *this;}
bool operator<(const student_iter& r)const{return p->id<(r.p)->id;}
bool operator<=(const student_iter& r)const {return p->id<=(r.p)->id;}
bool operator==(const student_iter& r)const {return p->id==(r.p)->id;}
bool operator>(const student_iter& r)const {return p->id>(r.p)->id;}
int& operator*() const {return (*p).id;}
};
定義好這些，就可以工作了：
int main()
{
student A[10];
for(int i=0;i<10;++i){
int x=rand()%124;
A[i].id=x;
A[i].name=x+'a';
}
student_iter B[10];
for(int i=0;i<10;++i){
B[i]=student_iter(&A[i]);
}
for(student* it=A;it!=A+10;++it){
std::cout<<(*it).id<<" ";
}
std::cout<<'\n';
_heap_sort(B,B+10);
for(student_iter* it=B;it!=B+10;++it){
std::cout<<*(*it)<<" ";
}
char c=getchar();
}
對于這個程式的擴充，例如如果排序有大量重複元素的序列，這樣我們就可以按《算法導論》7-2設計算法了：
//當後面多一個bool型參數時，可以選擇分三段式
template<typename RandomIterator,typename T>
iter_pair<RandomIterator> _partition(RandomIterator first,RandomIterator last,T pivot,bool)
{
typedef iterator_traits<RandomIterator>::difference_type size_type;
for(RandomIterator i=first;i!=last;++i){
if(*i==pivot){RandomIterator tmp=last-1;iter_swap(i,tmp);break;}
}
RandomIterator i=first-1;
RandomIterator r=last-1;
size_type count=1;//等于pivot元素的個數,初始時為1
RandomIterator tmp=r;
//[tmp,last)中的元素的值等于pivot
for(RandomIterator j=first;j!=tmp;++j){
if(*j<pivot){
++i;
iter_swap(i,j);
}else if(*j==pivot){//如果兩者相等，交換(r-count)和j，此時j的值未知，需要重新判斷
//是故--j，主元數目增加一
tmp=r-count;
iter_swap(j,tmp);
++count;
--j;
}
}
size_type count_=count;
//此時[i+1,i+count+1)中的元素的值大于pivot，[i+count+1,last)中元素的值等于pivot
if(ptrdiff_t(r-(i-count))<count){//此時等于pivot的元素多于大于pivot的元素
count_=ptrdiff_t(r-(i-count));
}
//交換
for(int j=0;j<count_;++j){
RandomIterator L=i+1+j,R=r-j;
iter_swap(L,R);
}
//此時[first,i]小于pivot，[i+1,i+count]等于pivot，[i+count+1,r]大于pivot
return iter_pair<RandomIterator>(i+1,i+count);
}
然後再設計多一個bool類型參數的對應的sort函數進行寬展，這裡就不寫了。。。