1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include<bits/stdc++.h>
using namespace std;
void qs(vector<int> &nums,int left,int right){
if(left>=right) return;
int pivot_index = (left+right)/2;
int pivot = nums[pivot_index];
int i = 0;
int j = right;
while(i<j){
while(nums[i]<pivot){
i++;
}
while(nums[j]>pivot){
j--;
}
if(i<=j)
{
swap(nums[i],nums[j]);
i++;
j--;
}
}
qs(nums,left,j);
qs(nums,i,right);
}
void quick_sort(vector<int> &num,int left,int right){
if (left>= right) return ;
srand(time(nullptr));
int index = rand()%(right-left);
index += left;
int target_num = num[index];
int i = left;
int j = left;
int k = right;
while(i<k){
if(num[i]>target_num){
swap(num[i],num[--k]);
}else if(num[i]<target_num){
swap(num[i++],num[j++]);
}else i++;
}
quick_sort(num,left,j);
quick_sort(num,k,right);
}
int main(){
int n;
cin>>n;
vector<int> nums;
for(int i = 0;i<n;i++){
int temp;
cin>>temp;
nums.push_back(temp);
}
qs(nums,0,nums.size()-1);
return 0;
}
|
