快速排序法的C++實作

快速排序法：

快速排序法的最壞時間代價為O(n2),最壞空間代價為O(n);

最優和平均時間代價為O(nlogn),空間代價為O(logn);

快速排序法采用分治的思想，取定一個軸值,此處取中間值,然後将該值放于臨時變量temp中,然後将最右邊的值放于中間位置處，此時，最右邊的位置便空閑出來索引為jIndex，最左邊的索引為iIndex初始為0

然後就從左邊iIndex處開始向右找大于temp的數，每次iIndex自加1,當找到時，将其值放于jIndex處,然後jIndex--,從jIndex開始從右往左找小于temp的數,當iIndex與jIndex相等時，在iIndex處放置temp值，此時temp值左邊的值均小于temp，temp值右邊的值均大于temp，然後遞歸排序temp左邊和右邊的序列即可

#ifndef RAPIDSORT_H
#define RAPIDSORT_H
#include <iostream>
using namespace std;
template<typename T>
class RapidSort{
public:
 void rapidSort( T*,int );
 void printArr( T*,int );
};
/**
 * 遞歸實作快速排序法
 */
template<typename T> void RapidSort<T>::rapidSort( T *sortedArr,int arrLength )
{
 if( arrLength==1 || arrLength==0 )
  return;
 int lIndex=0,rIndex=arrLength-1;
 int middle=( lIndex+rIndex )/2;
 int temp=sortedArr[middle];
 sortedArr[middle]=sortedArr[rIndex];
 bool ltor=true;
 while( lIndex!=rIndex )
 {
  if( ltor )
  {
   if( sortedArr[lIndex]>temp )
   {
    sortedArr[rIndex--]=sortedArr[lIndex];
    ltor=false;
   }
   else
    ++lIndex;
  }else{
   if( sortedArr[rIndex]<temp )
   {
    sortedArr[lIndex++]=sortedArr[rIndex];
    ltor=true;
   }
   else
    --rIndex;
  }
  
 }
 sortedArr[lIndex]=temp;
 // 排序左半部分
 rapidSort( &sortedArr[0],lIndex+1 );
 // 排序右半部分
 rapidSort( &sortedArr[lIndex+1],arrLength-lIndex-1 );
}
template<typename T> void RapidSort<T>::printArr( T *sortedArr,int arrLength )
{
 for( int i=0;i<arrLength;++i )
 {
  cout<<sortedArr[i]<<"   ";
 }
}
#endif
           

優化的快速排序算法：

快速排序算法的優化主要可以從軸值的選取和遞歸着手，其中遞歸可以通過以下方式優化:

對于快速排序算法，每次遞歸均會開辟一塊空間，是以當序列長度較小時，可以不再排序，最後将序列用插入排序法排列一次即可