—希尔排序—
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,在每个间隔内进行简单插入排序。希尔排序又叫缩小增量排序。
算法描述
具体算法描述如下:
- <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