【算法导论】C++实现的随机化的快速排序

【算法导论】C++实现的随机化的快速排序

C++实现的随机化的快速排序：

1. #include <iostream>  
2. #include <set>  
3. #include <string>  
4. void swap(int * a,int * b); 
5. int partition(int * array_list,int left,int right); 
6. void Print(); 
7. int random_partition(int * array_list,int left,int right); 
8. void random_quick_sort(int * array_list,int left,int right); 
9. const int size = 100; 
10. //int array_list [] ={2,8,7,1,3,5,6,4};  
11. int * array_list; 
12. int main() 
13. { 
14.     //const int size = 10;  
15.     array_list = new int [sizeof(int)*size]; 
16.     srand(0); 
17.     for(int i=0;i<size;i++) 
18.     {/*随即的填充数组元素*/ 
19.         int ran_num=rand()% size; 
20.         array_list[i] = ran_num; 
21.     } 
22.     random_quick_sort(array_list,0,size - 1); 
23.     Print(); 
24.     return 0; 
25. } 
26.  
27. void random_quick_sort(int * array_list,int left,int right) 
28. { 
29.     if(left >= right) 
30.     { 
31.         return ; 
32.     } 
33.     int index = random_partition(array_list,left,right); 
34.     random_quick_sort(array_list,left,index - 1); 
35.     random_quick_sort(array_list,index + 1,right); 
36. } 
37. /*随机化的快速排序对于输入的元素加入随机化的成分，使之获得较好的平均性能*/ 
38. int random_partition(int * array_list,int left,int right) 
39. { 
40.     srand(left); 
41.     int ran_num=( rand())% right; 
42.     if((ran_num < left )) 
43.     {/*防止出现因为取模后随机数为0的情况*/ 
44.         ran_num = left; 
45.     } 
46.     /*如果，不交换排序区间内的数据，则成为普通的快速排序*/ 
47.     swap(&array_list[right],&array_list[ran_num]); 
48.     return partition(array_list,left,right); 
49. } 
50. int partition(int * array_list,int left,int right) 
51. { 
52.     int index = left; 
53.     int pivot = array_list[right]; 
54.     for(int i= left ; i< right; i++) 
55.     { 
56.         if(array_list[i] < pivot) 
57.         { 
58.             swap(&array_list[index],&array_list[i]); 
59.             index ++; 
60.         } 
61.     } 
62.     swap(&array_list[right],&array_list[index]); 
63.     //Print();  
64.     return index; 
65. } 
66. void swap(int * a,int * b) 
67. { 
68.     int  tmp = *a; 
69.     *a = *b; 
70.     *b = tmp; 
71. } 
72. void Print() 
73. { 
74.     for(int i=0;i< size;i++) 
75.     { 
76.         std::cout<<array_list[i]<<"\t"; 
77.     } 
78.     std::cout<<std::endl; 
79. }