【算法導論】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. }
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. }