随机快速排序

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

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

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

普通快速排序

real	1m30.968s
user	1m30.810s
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。

real	0m0.061s
user	0m0.060s
sys	0m0.000s

gprof统计的性能

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
100.00      0.01     0.01    66784     0.00     0.00  partition_rand
  0.00      0.01     0.00  1055536     0.00     0.00  swap
  0.00      0.01     0.00        1     0.00    10.00  quicksort_rand
  0.00      0.01     0.00        1     0.00    10.00  test_quicksort

int test_quicksort(int number)
{
    int i;

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

    printf("----------------------------------------before quicksort----\n");
    srand(time(NULL));
    for(i = 0;i<number;i++)
    {
         array[i] = number - i;

        if(number < 100)
         printf("\tarray[%-6d] = %-6d\n",i,array[i]);
    }

    printf("----------------------------------------after quicksort-----\n");

    quicksort(array,0,number-1);

    if(number < 25)
    {
        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("number is 0,please input a big number \n");
         return -2;
    }

    test_quicksort(number);
}

 void  swap(int  *a ,int *b)

 {

int t = *a;

*a   = *b;

*b = t;

 }

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

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

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

}

  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);

}

  }

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

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

      int pivot = array[right];
      int curpos = left;

      for(i = left;i< right; i ++)
      {
           if(array[i] < pivot)
           {
                swap(&array[curpos], &array[i]);

          curpos++;
   }
      }

      swap(&array[curpos], &array[right]);
      return curpos;
}



void quicksort_rand(int array[] , int left ,int right)

{
        int interval;
       	if(left
        {
            interval = partition_rand(array,left,right);
            quicksort_rand(array,left,interval-1);
            quicksort_rand(array,interval+1,right);
        }
}

阅读(5003) | 评论(0) | 转发(0) |

0

上一篇：封装一个通用的C函数链表

下一篇：海量数据处理算法设计