找回密码
 用户注册

QQ登录

只需一步,快速开始

查看: 3488|回复: 0

随机化快速排序 |w397090770

[复制链接]
发表于 2011-12-19 23:24:01 | 显示全部楼层 |阅读模式
快速排序的算法的性能取决于划分的对称性。通过修改函数 Partition ,可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中,当数组还没有被划分时,可以在 a[p:r] 中随机选出一个元素作为划分基准,这样可以使划分基准的选择是随机的,从而可以期望划分是较对称的。


代码如下:

  1.    #include <stdio.h>
  2. #include <stdlib.h>
  3. int a[]={15,56,2,51,1,59,3};  // 待排序数组 a
  4.   
  5. void Swap( int *a, int *b) {    // 函数 Swap 实现两数的对调操作
  6. int temp;
  7. temp=*a;*a=*b;*b=temp;
  8. }
  9.   
  10. int Random(int p,int r) {        // 产生 p 和 r 之间的一个随机整数
  11. int result=p+rand()%(r-p+1);
  12. return result;
  13. }
  14.   
  15. int Partition( int a[], int p, int r) {
  16. int i=p,j=r+1; int x=a[p];
  17. // 将 <x 的元素交换到左边区域
  18. // 将 >x 的元素交换到右边区域
  19. while ( true ) {
  20. while (a[++i]<x&&i<=r); while (a[--j]>x&&j>=p);
  21. if (i>=j) break ;
  22. Swap (&a[i],&a[j]);
  23. }
  24. a[p]=a[j]; a[j]=x; return j;
  25. }
  26.   
  27. int RandomizedPartition( int a[], int p, int r) {
  28. int i=Random(p,r);
  29. Swap (&a[i],&a[p]);
  30. return Partition(a,p,r);
  31. }
  32.   
  33. void RandomizedQuickSort( int a[], int p, int r) {
  34. if (p<r) {
  35. int q= RandomizedPartition (a,p,r);
  36. RandomizedQuickSort (a,p,q-1); RandomizedQuickSort(a,q+1,r);
  37. }
  38. }
  39.   
  40. void main() {
  41. for ( int i=0;i<7;i++)  printf("%d ",a[i]);
  42. printf ("\n");
  43. RandomizedQuickSort (a,0,6);
  44. for (i=0;i<7;i++)  printf("%d ",a[i]);
  45. printf ("\n");
  46. }
复制代码


其中,函数 Random(p,r) 产生 p r 之间的一个随机整数,且产生不同整数的概率相同。随机化的快速排序算法通过调用 RandomizedPartition 来产生随机的划分。

程序效果:

作者:w397090770 发表于2011-12-19 22:09:34 原文链接
您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

Archiver|手机版|小黑屋|ACE Developer ( 京ICP备06055248号 )

GMT+8, 2024-3-29 04:04 , Processed in 0.019260 second(s), 6 queries , Redis On.

Powered by Discuz! X3.5

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表