// ShellSort.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include <iostream>

using namespace std;

#define ARRAY_LENGTH 10

///////////////////////////////////////////////////////////////////////////////////////////

///

/// 希尔排序：就是优化版的直接插入排序

///

/// 将数组分成n组，对每组数据进行直接排序;

/// 然后继续将数组分成n/2组 在进行直接排序；直到n/2 = 0

///

//////////////////////////////////////////////////////////////////////////////////////////

//

void ShellSort(int Array[], int nLength)

{

// 步长 分多少次组

for (int grap = nLength/2; grap > 0; grap /= 2)

{

// 多少组数组（每组数组的数据第一个数据的Index）

for (int i = 0; i < grap; ++i)

{

///////////////////////////////////////////////////////

// //

// 直接插入排序 //

// //

//////////////////////////////////////////////////////

// 每组数据（从第二个开始取，然后插入前面的序列中）

for (int j = i+grap; j < nLength; j+=grap)

{

// 待插入数

int nWaitInsert = Array[j];

int nComparePos = j-grap;

while (nComparePos >= 0 && nWaitInsert < Array[nComparePos])

{

Array[nComparePos +grap] = Array[nComparePos];

nComparePos = nComparePos - grap;

}

Array[nComparePos+grap] = nWaitInsert;

}

}

}

}

// 输出数组数据

void PrintArray(int Array[], int nLength)

{

for(int i = 0; i < nLength; ++i)

{

cout << Array[i] << ", ";

}

cout << endl;

}

int _tmain(int argc, _TCHAR* argv[])

{

int arr[ARRAY_LENGTH] = { 2, 9, 1, 5, 6, 8, 7, 3, 0, 11 };

// 1.排序算法1

cout << "排序前数据：" << endl;

PrintArray(arr, ARRAY_LENGTH);

ShellSort(arr, ARRAY_LENGTH);

cout << "排序后数据：" << endl;

PrintArray(arr, ARRAY_LENGTH);

system("pause");

return 0;

}