-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsort.cpp
More file actions
79 lines (73 loc) · 1.71 KB
/
sort.cpp
File metadata and controls
79 lines (73 loc) · 1.71 KB
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
77
78
79
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <list>
#include <algorithm>
#include <random>
#include <ctime>
using namespace std;
int randomRange(int start, int end) {
return (rand() % (end - start + 1) + start);
}
typedef struct node {
int val;
struct node *next;
}ListNode;
int partition(vector<int>& nums, int start, int end) {
int target = randomRange(start, end);
swap(nums[start], nums[target]);
int tmp = nums[start];
while(start < end) {
while(start < end && nums[end] > tmp) --end;
nums[start] = nums[end];
while(start < end && nums[start] <= tmp) ++start;
nums[end] = nums[start];
}
nums[start] = tmp;
return target;
}
void quickSort1(vector<int>& nums, int start, int end) {
if(start >= end)
return ;
int target = partition(nums, start, end);
quickSort1(nums, start, target - 1);
quickSort1(nums, target + 1, end);
}
void heapAdjust(vector<int> &nums, int i, int len) {
int child, tmp;
for(tmp = nums[i]; 2 * i + 1 < len; i = child) {
child = 2 * i + 1;
if(child + 1 < len && nums[child + 1] > nums[child]) ++child;
if(tmp < nums[child]) {
nums[i] = nums[child];
nums[child] = tmp;
}
else break;
}
}
void heapSort(vector<int>& nums) {
int len = nums.size();
for(int i = (len - 1) / 2;i >= 0; --i)
heapAdjust(nums, i, len);
for(int i = len - 1; i >= 0; --i) {
swap(nums[0], nums[i]);
heapAdjust(nums, 0, i);
}
}
int main() {
time_t t;
srand((unsigned int)time(&t));
vector<int> nums;
for(int i = 0; i < 100; ++i) {
nums.push_back(randomRange(0, 100));
}
for(auto num : nums)
cout << num << " ";
cout<<endl;
//quickSort1(nums, 0, nums.size() - 1);
heapSort(nums);
cout<<"new"<<endl;
for(auto num : nums)
cout << num << " ";
}