【排序算法】希尔排序

ORZ,似乎还能用
不是很符合希尔排序,对每组元素的排序不是严格的插入排序
嵌套了4层for…
下周看看能不能优化下

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
80
81
// ShellSort.cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <cassert>
using namespace std;

template <typename T>
void mySwap(T &a, T &b)
{
T t(a);
a = b;
b = t;
}

template <typename T>
void mySwap(typename T::iterator *a, typename T::iterator *b)
{
T t(*a);
*a = *b;
*b = t;
}

template <typename T>
void myDisplay(typename T::const_iterator begin, typename T::const_iterator end, ostream &os = std::cout)
{
while (begin != end - 1)
{
os << *begin << " ";
begin++;
}
os << *begin;
}


template <typename T>
int shellSort(vector<T> &data)
{
typedef vector<T> container_type;
typedef typename container_type::size_type container_size_type;
container_size_type times = static_cast<container_size_type>(floor(log(data.size() + 1) / log(2)));
// 分组间隔减少直到1,即所有数据分成1组
for (container_size_type cnt = 1; cnt <= times; ++cnt)
{
container_size_type gap = static_cast<container_size_type>(pow(2, times - cnt + 1) - 1);
// 对所有组进行逐组排序
for (container_size_type i = 0; i < gap; ++i)
{
// 对当前组的元素a[j+n*gap]逐个进行排序
for (container_size_type j = i; j < data.size(); j += gap)
{
// 比较当前元素a[j]与当前组其他元素a[j+n*gap]
for (container_size_type k = j + gap; k < data.size(); k += gap)
{
if (data[j] > data[k])
{
mySwap(data[j], data[k]);
}
}
}
}
}
return 0;
}

int main()
{
vector<int> data;
int t;
while (cin >> t)
{
data.push_back(t);
}
shellSort(data);
myDisplay< vector<int> >(data.begin(), data.end());
#ifdef _DEBUG
cin.get();
#endif
return 0;
}

写了一个随机生成数据来测试算法正确性的函数模板,也顺便一起贴了吧

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
#include <random>
#include <limits>
template <typename T>
bool testSort(int (*func)(vector<T> &data), int times = 5, int amount = 1000, T rangeMin = std::numeric_limits<T>::min(), T rangeMax = std::numeric_limits<T>::max())
{
typedef vector<T> container_type;
typedef typename container_type::size_type container_size_type;

default_random_engine generator;
uniform_int_distribution<T> distribution(rangeMin, rangeMax);

for (int i = 0; i <= times; ++i)
{
// start new turn
container_type dataGroup;
// generate test data group
for (int j = 0; j < amount; ++j)
{
T random = distribution(generator);
dataGroup.push_back(random);
}

// test func
func(dataGroup);

// check sort result
container_size_type len = dataGroup.size();
if (len > 1)
{
for (container_size_type j = 1; j < len; ++j)
{
if (dataGroup[j - 1] > dataGroup[j])
{
// failed at some data
cerr << "test failed at: " << endl;
myDisplay< container_type >(dataGroup.begin(), dataGroup.end(), cerr);
return false;
}
}
}
}
clog << "pass all test" << endl;
// pass all test
return true;
}

int main()
{
// for example
assert( true == testSort<int>( shellSort ) );
}
Donate
  • Copyright: Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2014-2021 听寒
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信