随机化快速排序 |w397090770

winston

快速排序的算法的性能取决于划分的对称性。通过修改函数 Partition ，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在 a[p:r] 中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。

代码如下：

2.    #include <stdio.h>
4. #include <stdlib.h>
6. int a[]={15,56,2,51,1,59,3};  // 待排序数组 a
8.   
10. void Swap( int *a, int *b) {    // 函数 Swap 实现两数的对调操作
12. int temp;
14. temp=*a;*a=*b;*b=temp;
16. }
18.   
20. int Random(int p,int r) {        // 产生 p 和 r 之间的一个随机整数
22. int result=p+rand()%(r-p+1);
24. return result;
26. }
28.   
30. int Partition( int a[], int p, int r) {
32. int i=p,j=r+1; int x=a[p];
34. // 将 <x 的元素交换到左边区域
36. // 将 >x 的元素交换到右边区域
38. while ( true ) {
40. while (a[++i]<x&&i<=r); while (a[--j]>x&&j>=p);
42. if (i>=j) break ;
44. Swap (&a[i],&a[j]);
46. }
48. a[p]=a[j]; a[j]=x; return j;
50. }
52.   
54. int RandomizedPartition( int a[], int p, int r) {
56. int i=Random(p,r);
58. Swap (&a[i],&a[p]);
60. return Partition(a,p,r);
62. }
64.   
66. void RandomizedQuickSort( int a[], int p, int r) {
68. if (p<r) {
70. int q= RandomizedPartition (a,p,r);
72. RandomizedQuickSort (a,p,q-1); RandomizedQuickSort(a,q+1,r);
74. }
76. }
78.   
80. void main() {
82. for ( int i=0;i<7;i++)  printf("%d ",a[i]);
84. printf ("\n");
86. RandomizedQuickSort (a,0,6);
88. for (i=0;i<7;i++)  printf("%d ",a[i]);
90. printf ("\n");
92. }

复制代码

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

程序效果：

作者：w397090770 发表于2011-12-19 22:09:34 原文链接