希尔排序是插入排序的一种优化,其思想为将无序数组分割为若干个子序列,子序列不是逐段分割的,而是相隔特定的增量的子序列,对各个子序列进行插入排序;然后再选择一个更小的增量,再将数组分割为多个子序列进行排序......最后选择增量为1,即使用直接插入排序,使最终数组成为有序。增量的选择上比较普遍是一半一半递减选取,10个数字无序序列,增量是len/2,然后不断缩短,最后一次增量为1.
void ShellSort()
{
int gap = len/ 2;//初始增量为数组长度的一半
while (1 <= gap)
{
for (int i = gap; i < len ; i++)
{
int j = 0;
int temp = iRawBuff[i];
for (j = i - gap; j >= 0 && temp < iRawBuff[j]; j = j - gap)
{
iRawBuff[j + gap] = iRawBuff[j];
}
iRawBuff[j + gap] = temp;
}
gap = gap / 2; 增量为上次的二分之一
}
for (int k = 0; k < len; k++)
{
cout << iRawBuff[k] << " ";
}
cout << endl;
}