快速排序转冒泡排序的临界值

快速排序当数组的元素个数少于某个临界值（Threshold）时，采用冒泡排序可提高效率（此文不证明）,但这个临界值多少时，效率最高呢?

测试代码：

  


#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include <memory.h>

inline __int64 GetCpuCounter(){
   __asm _emit 0x0F
   __asm _emit 0x31
}

template <class Elem>
void swap(Elem &e1,Elem &e2){
   Elem temp = e2;
   e2 = e1;
   e1 = temp;
}

template <class Elem>
void bubSort(Elem A[], int n){
   for(int i =0; i <n-1; i++)
      for(int j = n-1; j > i; j--) //bubble up i'th element

         if(A[j] < A[j-1])
            swap<Elem>(A[j],A[j-1]);
}


template<class Elem>
int partition(Elem A[],int left, int right) //right一定大于left

{
   Elem temp = A[left];
   do{
      // 循环找出右边起第一个比temp小的数

      while((right > left)&&(A[--right] > temp));
      if(left < right)
         swap<Elem>(A[right], A[left]); // 将此数和A[left]交换

      // 循环找出左边起第一个比temp大的数

      while((left < right)&&(A[++left] < temp));
      if(left < right)
         swap<Elem>(A[right], A[left]);

   }
   while(left < right);
   return left;
}

template<class Elem, int THRESHOLD>
void qSort(Elem A[],int left,int right){
   if(left >= right)
      return;
   int size = right - left + 1;
   if(size <= THRESHOLD){
      bubSort<Elem>(&A[left], size);
      return;
   }
   if(A[left] > A[right]) //让A[left]和A[right-1]以前的元素比较

      swap<Elem>(A[right], A[left]);
   int k = partition<Elem>(A,left,right);
   qSort<Elem, THRESHOLD>(A,left,k-1);
   qSort<Elem, THRESHOLD>(A,k+1,right);
}

#define TestThreshold(a, size, startThreshold, conter1, counter2, passed) \
conter1 = GetCpuCounter(); \
qSort<int, startThreshold>(a, 0, size - 1); \
counter2 = GetCpuCounter(); \
passed = counter2 - conter1; \
printf("Threshold:%2d cpu Counter: %ld\n", startThreshold, passed);


int main(){
   const int arraySize = 100000;
   int origin[arraySize];
   srand(time(0));
   for(int n = 0; n < arraySize; n++){
      origin[n] = rand() % 10000000;
   }
   int a[arraySize];
  
   //

   __int64 counter1;
   __int64 counter2;
   __int64 passed;

   memcpy(a, origin, sizeof(int) * arraySize);
   const int threshold4 = 4;
   TestThreshold(a, arraySize, threshold4, counter1, counter2, passed);

   memcpy(a, origin, sizeof(int) * arraySize);
   const int threshold5 = 5;
   TestThreshold(a, arraySize, threshold5, counter1, counter2, passed);

   memcpy(a, origin, sizeof(int) * arraySize);
   const int threshold6 = 6;
   TestThreshold(a, arraySize, threshold6, counter1, counter2, passed);
   
   memcpy(a, origin, sizeof(int) * arraySize);
   const int threshold7 = 7;
   TestThreshold(a, arraySize, threshold7, counter1, counter2, passed);

   memcpy(a, origin, sizeof(int) * arraySize);
   const int threshold8 =8;
   TestThreshold(a, arraySize, threshold8, counter1, counter2, passed);

   memcpy(a, origin, sizeof(int) * arraySize);
   const int threshold9 = 9;
   TestThreshold(a, arraySize, threshold9, counter1, counter2, passed);
 
   memcpy(a, origin, sizeof(int) * arraySize);
   const int threshold10 = 10;
   TestThreshold(a, arraySize, threshold10, counter1, counter2, passed);
   
   memcpy(a, origin, sizeof(int) * arraySize);
   const int threshold11 = 11;
   TestThreshold(a, arraySize, threshold11, counter1, counter2, passed);

   memcpy(a, origin, sizeof(int) * arraySize);
   const int threshold12 = 12;
   TestThreshold(a, arraySize, threshold12, counter1, counter2, passed);

   memcpy(a, origin, sizeof(int) * arraySize);
   const int threshold13 = 13;
   TestThreshold(a, arraySize, threshold13, counter1, counter2, passed);
  
   memcpy(a, origin, sizeof(int) * arraySize);
   const int threshold14 = 14;
   TestThreshold(a, arraySize, threshold14, counter1, counter2, passed);

   memcpy(a, origin, sizeof(int) * arraySize);
   const int threshold15 = 15;
   TestThreshold(a, arraySize, threshold15, counter1, counter2, passed);

   memcpy(a, origin, sizeof(int) * arraySize);
   const int threshold16 = 16;
   TestThreshold(a, arraySize, threshold16, counter1, counter2, passed);

   memcpy(a, origin, sizeof(int) * arraySize);
   const int threshold17 = 17;
   TestThreshold(a, arraySize, threshold17, counter1, counter2, passed);

   
  getchar();
   return 0;
}


结果自己运行了看吧