Randomized_QuickSort C++

算法导论(第三版)中文 P102

 //RANDOMIZED_QUICKSORT.h文件

 1 #pragma once
 2 #include"QUICKSORT.h"
 3 #include<iostream>
 4 #include<random>
 5 int Randomized_partition(std::vector<int>& A, const int& p, const int& r)
 6 {
 7     std::default_random_engine e; //引擎：生成随机无符号数
 8     std::uniform_int_distribution<unsigned> u(p, r);// 范围内的随机数
 9     int i = u(e);
10     std::swap(A[r], A[i]); //是随机数是主元
11     return Partition(A, p, r);
12 }
13 
14 void Randomized_QuickSort(std::vector<int> &A, const int& p, const int& r)
15 {
16     if (p < r)
17     {
18         int q = Randomized_partition(A, p, r);
19         Randomized_QuickSort(A, p, q-1);
20         Randomized_QuickSort(A, q + 1, r);
21     }
22 }

main.cpp

 1 #include"QUICKSORT.h"
 2 #include"RANDOMIZED_QUICKSORT.h"
 3 #include<iterator> //ostream_iterator
 4 void QuickSort()
 5 {
 6     vector<int> v = { 0,2,8,7,1,3,5,6 };//0 占位置 是 i = p-1;
 7     cout << "A is" << endl;
 8     std::ostream_iterator<int> out_iter(cout, " ");
 9     copy(v.begin() + 1, v.end(), out_iter);
10     cout << endl;
11     Randomized_QuickSort(v, 1, v.size()-1);
12     cout << " sorted A " << endl;
13     copy(v.begin() + 1, v.end(), out_iter);
14 }
15 int main()
16 {
17     QuickSort();
18 }