希尔排序

  1. —希尔排序—
    1. 算法描述
    2. 代码实现
    3. 算法分析
    4. 稳定性

—希尔排序—

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,在每个间隔内进行简单插入排序。希尔排序又叫缩小增量排序。

算法描述

具体算法描述如下:

  • <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

×

喜欢就点赞,疼爱就打赏