Quicksort是一个很好的排序算法，但是其最坏情况运行时间是O(n^2), 还不如Mergesort的O(nlgn),
如何改进Quicksort? 引进随机化思想
一种方法： 对给定的待排序序列，随机地重排列
另一种方法：随机选取pivot
给出第二种方法的代码
1
/**//**
2
* 2010.1.24
3 * 随机快速排序法
4 * pivot元素并不是简单地取第一个元素，而是随机生成一个下标，以对应的元素为pivot
5
*/
6
7#include <iostream>
8#include <cstdlib>
9#include <ctime>
10
11using namespace std;
12
13//交换两个元素值
14void swap(int& a , int& b)
15
{
16 int temp = a;
17 a = b;
18 b = temp;
19}
20
21//输出数组
22void print(int* a , int n)
23{
24 for(int i = 0; i < n ; i++)
25 cout << a[i]<<",";
26 cout << endl;
27}
28
29//返回属于[p,q)的随机整数
30int rand(int p,int q)
31{
32 int size = q-p+1;
33 return p+ rand()%size;
34}
35
36//分割
37int RandPartition(int* a, int p , int q)
38{
39 //普通的分割方法和随机化分割方法的区别就在于下面三行
40 swap(a[rand(p,q)], a[p]);
41 int key = a[p];
42 int i = p;
43
44 for(int j = p+1; j <= q; j++)
45
{
46 if(a[j] <= key)
47 {
48 i = i+1;
49 if(i != j)
50 swap(a[i], a[j]);
51
}
52 }
53
54 swap(a[i],a[p]);
55
56 return i;
57}
58
59//逐步分割排序
60void RandQuickSortMid(int* a, int p, int q)
61{
62 if(p<q)
63 {
64 int i = RandPartition(a,p,q);
65 RandQuickSortMid(a,p,i-1);
66 RandQuickSortMid(a,i+1,q);
67 }
68}
69
70//调用
71void RandQuickSort(int* a, int n)
72{
73 //记录运行时间
74 clock_t start,end;
75 start = clock();
76
77 RandQuickSortMid(a,0,n-1);
78
79 end = clock();
80 cout << "Running time: " << (double)(end-start)/CLOCKS_PER_SEC << endl;
81}
82
83
84int main()
85{
86 const int N = 20;
87 int *a = new int[N];
88 for(int i = 0; i < N; i++)
89 a[i] = rand();
90
91 print(a,N);
92 RandQuickSort(a,N);
93 print(a,N);
94
95 system("pause");
96 return 0;
97}