Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3851915
  • 博文数量: 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-28 12:14:22


     前文提到过,快速排序,主元的选择很重要,理想情况下是主元将数组平均分成两份,这样的话就是理想的分而治之的策略。但是由于每次选择最右边的元素作为主元pivot,很有可能不能将数组均匀的分成两份。特殊输入情况下,普通的快速排序就退化成O(N^2).比如逆序输入。

    对于快速排序在退化情况下到底有多慢大家可能没有直观的感受,我做了个实验.输入为逆序数组。第一次,我没有经验,直接输入了 100万的数组长度,结果,我出去烧了一壶水,水都烧开了,程序还没跑完。我实在没有耐心等了,就杀死了进程。

    接下来我学乖了点,用10万的规模测试,分别是普通快速排序。统计结果如下

普通快速排序
  1. real 1m30.968s
  2. user 1m30.810s
  3. sys 0m0.100s

gprof信息如下
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 66.91     37.70    37.70    99999     0.00     0.00  partition
 33.07     56.34    18.64 2500049999   0.00     0.00  swap
  0.02     56.35     0.01        1     0.01    56.35  quicksort
  0.00     56.35     0.00        1     0.00    56.35  test_quicksort

     上面的测试表明,某些情况下,普通快速排序就是个坑爹货,排10万个元素用91秒钟,你能忍受的了吗?所以要想在工程上使用快速排序,必须堆快速排序进行优化。

     改进策略:选择[left,right]中任意一个元素作为主元。只需要将选中的主元与right位置上的元素互换,其他都不变。

     改进之后,我再次对逆序数组测试了性能。性能如下,不用多说了,总时间61ms
  1. real 0m0.061s
  2. user 0m0.060s
  3. sys 0m0.000s
  4. gprof统计的性能
  5. Flat profile:

  6. Each sample counts as 0.01 seconds.
  7.   %   cumulative   self              self     total           
  8.  time   seconds   seconds    calls  ms/call  ms/call  name    
  9. 100.00      0.01     0.01    66784     0.00     0.00  partition_rand
  10.   0.00      0.01     0.00  1055536     0.00     0.00  swap
  11.   0.00      0.01     0.00        1     0.00    10.00  quicksort_rand
  12.   0.00      0.01     0.00        1     0.00    10.00  test_quicksort

  1. int test_quicksort(int number)
  2. {
  3.     int i;
  4.     
  5.     int *array = malloc(number*sizeof(int));
  6.     if(array == NULL)
  7.     {
  8.           printf("malloc failed\n");
  9.           return -1;
  10.     }
  11.    
  12.     printf("----------------------------------------before quicksort----\n");
  13.     srand(time(NULL));
  14.     for(i = 0;i<number;i++)
  15.     {
  16.          array[i] = number - i;
  17.         
  18.         if(number < 100)
  19.          printf("\tarray[%-6d] = %-6d\n",i,array[i]);
  20.     }

  21.     printf("----------------------------------------after quicksort-----\n");
  22.     
  23.     quicksort(array,0,number-1);
  24.      
  25.     if(number < 25)
  26.     {
  27.         for(i = 0;i<number;i++)
  28.         {
  29.             printf("\tarray[%-6d] = %-6d\n",i,array[i]);
  30.         }
  31.     }

  32.     for( i = 0 ; i < number-1;i++)
  33.     {
  34.          if(array[i] > array[i+1])
  35.          {
  36.              printf("quick sort failed \n");
  37.              break;
  38.          }
  39.     }
  40.     
  41.     free(array);
  42.     return 0;
  43.     
  44. }


  45. int main(int argc,char *argv[])
  46. {
  47.     if(argc != 2)
  48.     {
  49.         printf("usage : ./test number\n");
  50.         return -1;
  51.     }

  52.     int number = atoi(argv[1]);
  53.     if(number <= 0)
  54.     {
  55.          printf("number is 0,please input a big number \n");
  56.          return -2;
  57.     }

  58.     test_quicksort(number);
  59. }

 void  swap(int  *a ,int *b)
 {
int t = *a;
*a   = *b;
*b = t;
 }

  1. int  partition(int array[],int l,int r)
  2. {
  3. int pivot =  array[r];
  4.   int curpos = l;
  5.         int j ;

  6.   for( j = l;j
  7.   {
  8.   if(array[j] < pivot)
  9.   {
  10. swap(&array[j],&array[curpos]);
  11. curpos++;
  12.   }
  13. }

  14.   swap(&array[r],&array[curpos]);
  15.         return curpos;
  16. }

  void quicksort(int array[],int l,int r)
  {
int interval;
if(l
{
            interval = partition(array,l,r);
            quicksort(array,l,interval-1);
    quicksort(array,interval+1,r);
}
  }

/*-----------------------------------------------------------------------------*/

  1. int partition_rand(int array[], int left ,int right)
  2. {
  3.       int i = left + rand()%(right -left +1);
  4.       swap(&array[i],  &array[right]);

  5.       int pivot = array[right];
  6.       int curpos = left;

  7.       for(i = left;i< right; i ++)
  8.       {
  9.            if(array[i] < pivot)
  10.            {
  11.                 swap(&array[curpos], &array[i]);
  12.           curpos++;
  13.    }
  14.       }

  15.       swap(&array[curpos], &array[right]);
  16.       return curpos;  
  17. }

  18. void quicksort_rand(int array[] , int left ,int right)
  1. {
  2.         int interval;
  3.         if(left
  4.         {
  5.             interval = partition_rand(array,left,right);
  6.             quicksort_rand(array,left,interval-1);
  7.             quicksort_rand(array,interval+1,right);
  8.         }
  9. }
阅读(3334) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~