希尔排序

希尔排序是插入排序的改进算法，编码实现如下：

#include <iostream>
#include <vector>

using namespace std;

template <typename Comparable>
void shellsort( vector<Comparable> &a )
{
    for ( int gap = a.size() / 2 ; gap > 0 ; gap /= 2 )               //增量每次除以2
        for ( int i = gap ; i < a.size() ; i++ ){                     //分出的每组使用插入排序
            Comparable tmp = a[i];
            int j = i;

            for ( ; j >= gap && tmp < a[ j - gap ] ; j -= gap )
                a[j] = a[j-gap];
            a[j] = tmp;
        }
}

int main()
{
    cout << "请输入一些数据：" << endl;

    vector<int> vec;
    int temp;

    while ( cin >> temp )
        vec.push_back( temp );

    shellsort( vec );

    cout << "按降序排列过的数据如下：" << endl;

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

    return 0;
}