三者取中快速排序

    本文实现三者取中快速排序，所谓三者取中的含义是[left,right]区间内的，选择 最左，最右和中间，三个元素中中间的那个元素作为主元。

    本实现方法为了减少递归掉用，对于 数组长度低于M =10的数组，不再进行快速排序了，而是直接返回。这样做的好处是减少函数调用的次数。返回之后，得到宏观上已序，微观上不是已序的数组。

    所谓宏观上已序，微观上不是已序的含义是指，[0， M-1] 中的任何个元素，都会小于[M,2M-1] 范围内的任何元素， 同理，[M,2M-1]范围内的任何元素都会小于[2M ,3M-1]范围内的任何元素，依次类推，所谓微观不是已序的含义，是指，[0,M-1]之内的元素，不一定已序，同理[M,2M-1]之内的元素不一定已序。

    对于这种队列，插入排序就可以派上用场了，前文提到过，插入排序并不是一无是处，这种队列上，判断和交换的次数不多，各位可以推算，判断交换的次数大概是多少。插入排序速度很快。

    本文算法源自算法C语言实现（向Sedgewick 致敬），但是本文利用宏观已序，微观非已序的性质，对后面的插入排序做了一点点修正，减少了一次遍历整个数组的时间。各位看官可以仔细看下本文中的insertsort和前文的标准insertsort有何不同。

     

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

#define M 10

inline void swap(int *a,int *b)
{
     int temp = *a;
     *a   = *b;
     *b   = temp;

}


inline void cmpswap(int *a,int *b)
{
     if(*a > *b)
        swap(a,b);
}

int  partition(int array[],int l,int r)
{
     int pivot =  array[r];
     int curpos = l;
     int j ;

     for( j = l;j<r;j++)
     {
          if(array[j] < pivot)
          {
               swap(&array[j],&array[curpos]);
               curpos++;
          }
     }

     swap(&array[r],&array[curpos]);
     return curpos;


}

void quicksort_m(int array[],int left,int right)
{
      if(right - left < M)
         return ;

      int mid = (left+right)/2;
      swap(&array[mid],&array[right-1]);

      cmpswap(&array[left],&array[right-1]);
      cmpswap(&array[left],&array[right]);
      cmpswap(&array[right-1],&array[right]);

      int interval = partition(array,left+1,right-1);
      quicksort_m(array,left,interval-1);
      quicksort_m(array,interval+1,right);

}

void insertsort(int array[],int left,int right)
{
      int i;
      int j;
      int cur;

      for(i = left + M -1;i>left;i--)  /*和标准插入排序比，有点点修改，加快了插入排序                {                                 *的速度*/
          if(array[i] < array[i-1])
             swap(&array[i],&array[i-1]);
      }

      for( i = left + 2; i <= right;i++)
      {
           cur = array[i];
           j = i;

           while(cur < array[j-1])
           {
                 array[j] = array[j-1];
                 j--;
           }
           array[j] = cur;
      }
}

int quicksort(int array[],int left,int right)
{
       if(array == NULL)
           return -1;
       if(right < left)
           return -2;
       if (right == left)
           return 0;

       quicksort_m(array,left,right);
       insertsort(array,left,right);
       return 0;
}


int test_quicksort(int number)
{

       int print_flag = 0;
       int *array = malloc(number*sizeof(int));
       if(array == NULL)
       {
           printf("malloc failed\n");
           return -1;
       }
       int i;

       printf("-------------------------before quick sort--------------\n");
       srand(time(NULL));
       if(number <= 50)
          print_flag = 1;

       for(i = 0;i<number;i++)
       {
           array[i] = rand();
           if(print_flag == 1)
              printf("\tarray[%6d] = %6d\n",i,array[i]);
       }

       printf("--------------------------after quick sort--------------\n");

       quicksort(array,0,number-1);

       if(print_flag == 1)
       {
            for(i = 0;i<number;i++)
            {
                printf("\tarray[%-6d] = %-6d\n",i,array[i]);
            }
       }

       for( i = 0 ; i < number-1;i++)
       {
            if(array[i] > array[i+1])
            {
                printf("quick sort failed \n");
                break;
            }
       }

       free(array);
       return 0;
}
int main(int argc,char* argv[])
{
      if(argc != 2)
      {
           printf("usage: ./test number \n");
           return -1;
      }

      int number = atoi(argv[1]);
      if(number < 0 )
      {
           printf("input a unsigned int type number\n");                                         return -2;
      }
      test_quicksort(number);
      return 0;
}