—希尔排序—
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，在每个间隔内进行简单插入排序。希尔排序又叫缩小增量排序。
算法描述
具体算法描述如下：
- <1>.选择gap，即间隔序列，一般为数组的一半。
- <2>.在各自gap上元素进行插入排序；
- <3>.重复步骤<1>,缩小gap，为原来的一半, 重复<2>，直至gap=0；
代码实现
void Xier_Sort(int a[],int n)
{
int gap = n / 2; //设置增量，即间隔为 数组长度的一半
while (gap > 0) //进入循环
{
for (int i = gap; i < n; ++i) //在每个增量间进行插入排序
{
int key = a[i];
int j = i - gap;
while (j >= 0 && a[j] > key)
{
a[j + gap] = a[j];
j -= gap;
}
a[j + gap] = key;
}
gap = gap / 2; // 缩小增量
}
}
算法分析
平均情况：T(n) =O(nlog n)
最佳情况：T(n) = O(nlog2 n)
最坏情况：T(n) = O(nlog2 n)
稳定性
- 不稳定
虽然插入排序稳定，但是由于设置了间隔，相同的元素若在不同的间隔上，可能会改变元素原来的顺序
例如：
arr[4] = {5 , 4, 4* , 6}
gap = 4/2 =2;
5 与 4* 在一个间隔内 ；4 与 6 在一个间隔内
第一次进行排序后：4* , 4, 5 , 6
相同元素4的顺序发生改变，故不稳定
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 351134995@qq.com
