谢尔排序（shellSort）:

        通过比较一定间隔的元素进行工作，各趟比较随着算法的进行而减小，直到只比较相邻元素的最后一趟元素排序结束，因此谢尔排序有时也称缩减增量排序（diminishing increment sort）.

行为描述：

算法描述：

        谢尔排序使用一个序列，叫做增量序列（increment sequence）。 只要,任何增量序列都是可行，不过有些增量序列比另一些增量序列好（如shell增量，Hibbard增量，sedgewick增量）。在使用增量的一趟排序之后，对于每一个有：，此时称文件为的排序。

谢尔排序的性质：

        一个排序的文件保持它的排序性；

        定理：使用谢尔增量排序的最坏情形运行时间为。【当时，将第个元素恢复到正确位置需要移动-1次 】

        定理：使用Hibbard增量排序的最坏情形运行时间为。【增量序列：1 ， 3， 5， 7， ... ， 。当对排序时，已经为有序序列，而且。

总的运行时间：】

        定理：使用sedgewick增量排序的最坏情形运行时间为【增量序列：1, 5，19，41， ...， 或】。

谢尔增量排序实例：

//shellSort.cpp
#include<iostream>
#include<vector>

using namespace std;

template<class Compareable>
void shellSort(vector<Compareable> &v){
	//update gap
	for(int gap = v.size() / 2; gap > 0; gap /= 2){
		//traverse vector
		for(int i = gap; i < v.size(); i++){
			Compareable temp = v[i];
			int j = i;
			//find the proper location
			for(; j >= gap && temp < v[j - gap]; j -= gap){
				v[j] = v[j - gap];
			}
			//insert into the proper location;
			v[j] = temp;
		}
	}
}

int main(){
	int arr[] = {81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15};
	int len = sizeof(arr) / sizeof(arr[0]);
	vector<int> v;
	for(int i = 0 ; i < len; i++){
		v.push_back(arr[i]);
	}
	
	cout << "******* the original data ***********" << endl;
	for(typename vector<int>::iterator itr = v.begin(); itr != v.end(); ++itr){
		cout << *itr << " ";
	}
	cout << endl;
	
	cout << "******* the sorted data ***********" << endl;
	shellSort(v);
	for(typename vector<int>::iterator itr = v.begin(); itr != v.end(); ++itr){
		cout << *itr << " ";
	}
	cout << endl;
	
	cout << " done ." << endl;
	return 0;
}

practice makes perfect !