希尔的定义:希尔排序是插入算法的一种,也叫缩小增量排序。是直接插入排序算法的一种改良版。
希尔算法是把数据序列按下标的一定增量分组,对每组使用直接插入排序算法进行排序;然后依次缩减增量再进行排序,待整个序列中的元素基本(注:没有全部完成排序)有序时,再对全体元素进行一次直接插入排序。
基本思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所以距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后取第二个增量d2<d1重复上述的分组和排序,直至所取的
增量
=1(
<
…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
时间复杂度为:最大O(n^2),最小O(n*log2n)。
实例:
int arr[] = { 35, 28, 58, 10, 61, 58, 97, 17 };
int k = sizeof(arr) / sizeof(arr[0]);
//根据当前增量进行插入排序
void shellInsert(int array[], int n, int dk)
{
int i, j, temp;
for (i = dk; i<n; i++)//分别向每组的有序区域插入
{
temp = array[i];
for (j = i - dk; (j >= i%dk) && array[j]>temp; j -= dk)//比较与记录后移同时进行
array[j + dk] = array[j];
if (j != i - dk)
array[j + dk] = temp;//插入
}
}
//希尔排序
void shellSort(int array[], int n, int t)
{
int i;
while(t >= 1)
{
shellInsert(array, n, t);
t = t / 2;
}
for (int f = 0; f < n; f++)
{
std::cout << array[f] << " ";
}
}