Quicksort是一個很好的排序算法，但是其最壞情況運(yùn)行時間是O(n^2), 還不如Mergesort的O(nlgn),
如何改進(jìn)Quicksort? 引進(jìn)隨機(jī)化思想
一種方法： 對給定的待排序序列，隨機(jī)地重排列
另一種方法：隨機(jī)選取pivot
給出第二種方法的代碼
1
/**//**
2
* 2010.1.24
3 * 隨機(jī)快速排序法
4 * pivot元素并不是簡單地取第一個元素，而是隨機(jī)生成一個下標(biāo)，以對應(yīng)的元素為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//輸出數(shù)組
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)的隨機(jī)整數(shù)
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 //普通的分割方法和隨機(jī)化分割方法的區(qū)別就在于下面三行
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//調(diào)用
71void RandQuickSort(int* a, int n)
72{
73 //記錄運(yùn)行時間
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}