Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3844400
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8584
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: C/C++

2011-08-31 19:47:58

    本文实现三者取中快速排序,所谓三者取中的含义是[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有何不同。

     
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<time.h>

  4. #define M 10

  5. inline void swap(int *a,int *b)
  6. {
  7.      int temp = *a;
  8.      *a = *b;
  9.      *b = temp;

  10. }


  11. inline void cmpswap(int *a,int *b)
  12. {
  13.      if(*a > *b)
  14.         swap(a,b);
  15. }

  16. int partition(int array[],int l,int r)
  17. {
  18.      int pivot = array[r];
  19.      int curpos = l;
  20.      int j ;

  21.      for( j = l;j<r;j++)
  22.      {
  23.           if(array[j] < pivot)
  24.           {
  25.                swap(&array[j],&array[curpos]);
  26.                curpos++;
  27.           }
  28.      }

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


  31. }

  32. void quicksort_m(int array[],int left,int right)
  33. {
  34.       if(right - left < M)
  35.          return ;

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

  38.       cmpswap(&array[left],&array[right-1]);
  39.       cmpswap(&array[left],&array[right]);
  40.       cmpswap(&array[right-1],&array[right]);

  41.       int interval = partition(array,left+1,right-1);
  42.       quicksort_m(array,left,interval-1);
  43.       quicksort_m(array,interval+1,right);

  44. }

  45. void insertsort(int array[],int left,int right)
  46. {        
  47.       int i;
  48.       int j;
  49.       int cur;

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

  54.       for( i = left + 2; i <= right;i++)
  55.       {
  56.            cur = array[i];
  57.            j = i;
  58.     
  59.            while(cur < array[j-1])
  60.            {
  61.                  array[j] = array[j-1];
  62.                  j--;
  63.            }
  64.            array[j] = cur;
  65.       }
  66. }

  67. int quicksort(int array[],int left,int right)
  68. {
  69.        if(array == NULL)
  70.            return -1;
  71.        if(right < left)
  72.            return -2;
  73.        if (right == left)
  74.            return 0;

  75.        quicksort_m(array,left,right);
  76.        insertsort(array,left,right);
  77.        return 0;
  78. }


  79. int test_quicksort(int number)
  80. {

  81.        int print_flag = 0;
  82.        int *array = malloc(number*sizeof(int));
  83.        if(array == NULL)
  84.        {
  85.            printf("malloc failed\n");
  86.            return -1;
  87.        }
  88.        int i;

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

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

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

  100.        quicksort(array,0,number-1);

  101.        if(print_flag == 1)
  102.        {
  103.             for(i = 0;i<number;i++)
  104.             {
  105.                 printf("\tarray[%-6d] = %-6d\n",i,array[i]);
  106.             }
  107.        }

  108.        for( i = 0 ; i < number-1;i++)
  109.        {
  110.             if(array[i] > array[i+1])
  111.             {
  112.                 printf("quick sort failed \n");
  113.                 break;
  114.             }
  115.        }

  116.        free(array);
  117.        return 0;
  118. }
  119. int main(int argc,char* argv[])
  120. {
  121.       if(argc != 2)
  122.       {
  123.            printf("usage: ./test number \n");
  124.            return -1;
  125.       }

  126.       int number = atoi(argv[1]);
  127.       if(number < 0 )
  128.       {
  129.            printf("input a unsigned int type number\n");                                         return -2;
  130.       }
  131.       test_quicksort(number);
  132.       return 0;
  133. }


阅读(6491) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~