forked from leo000leo/Algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathshell_sort.h
More file actions
55 lines (44 loc) · 1.45 KB
/
Copy pathshell_sort.h
File metadata and controls
55 lines (44 loc) · 1.45 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
//
// shell_sort
// Algorithm
//
// Created by dtysky on 16/9/13.
// Copyright © 2016 [email protected]. All rights reserved.
//
#ifndef ALGORITHM_SHELL_SORT_H
#define ALGORITHM_SHELL_SORT_H
#include <cstdio>
#include <vector>
namespace my_algorithm {
using std::vector;
// time: ......
// space: O(1)
template <typename T>
void shellSort(vector<T>& t_vector, const vector<uint32_t>& step_queue, const bool reverse = false) {
auto size = t_vector.size();
size_t current = 0;
T tmp;
for (auto step: step_queue) {
for (size_t start = 0; start < step; start++) {
for (auto end = 1 * step + start; end < size; end += step) {
tmp = t_vector[end];
current = end;
if (reverse) {
while (current > start && t_vector[current - step] < tmp) {
t_vector[current] = t_vector[current - step];
current -= step;
}
}
else {
while (current > start && t_vector[current - step] > tmp) {
t_vector[current] = t_vector[current - step];
current -= step;
}
}
t_vector[current] = tmp;
}
}
}
}
}
#endif //ALGORITHM_SHELL_SORT_H