【排序算法】希尔排序

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

// 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;
}

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

#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