算法系列--排序算法之希尔排序

算法系列--排序算法之希尔排序

// mySort.cpp : 定义控制台应用程序的入口点。
//shellSort   使用增量来增加排序效率

#include "stdafx.h"
#include <vector>
#include <iostream>
#define random(x) (rand()%100)

using namespace std;

template <typename T>
void shellSort( vector<T>& vec)
{
    int gap = vec.size()/2;
    for (; gap > 0; gap = gap/2)
    {
        for (int i = gap; i < vec.size(); i++)
        {
            T  temp = vec[i];
            int j = i;
            for (; j >= gap && temp < vec[j - gap] ; j = j - gap)
            {
                vec[j] = vec[j-gap];
            }
            vec[j] = temp;
        }
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    vector<int> vecInt ;
    for (int i = 0; i < 10; i++)
    {
        vecInt.push_back( random(100));
        cout<< vecInt[i] <<"  ";
    }
    cout <<endl;
    shellSort(vecInt);
    for (int i = 0; i < 10; i++)
    {
        cout<< vecInt[i] <<"  ";
    }
    cout<<endl;
    return 0;
}