排序算法——希尔排序

//============================================================================
// Name        : 希尔排序.cpp
// Author      : Lucas
// Version     :
// Copyright   : http://www.cnblogs.com/vestinfo/
// Description : 希尔排序
//============================================================================

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


template <class T>
void shellSort(vector<T> &a) {
	for (int gap = a.size()/2; gap > 0; gap /= 2) { 	//增量从a.size()开始，每次缩减为原来的1/2。每个gap排序后，相隔gap的元素保持有序。

		for (int i = gap; i < a.size(); i++) {			//从增量处开始，每次后移一个元素，结合下个循环，相当于插入排序。
			T tmp = a[i];
			int j = i;

			for (; j >= gap && tmp < a[j-gap]; j -= gap) {	//若当前元素比前一增量处元素小，则将当前元素前移（同时前一元素后移a[j]=a[j-gap]）,知道保持有序。
				a[j] = a[j-gap];
			}

			a[j] = tmp;
		}
	}
}


int main() {
	int a[] = {3, 1, 2, 5, 3, 7, 1, 9, 8, 0};
	vector<int> vec(a, a+10);
	shellSort(vec);


	for (vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
		cout << *iter << endl;
	}

	return 0;
}

本质是对基本有序的数列进行排序。