考研算法29天：希尔排序【希尔排序】-Toy模板网

这篇具有很好参考价值的文章主要介绍了考研算法29天：希尔排序【希尔排序】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

算法介绍

希尔排序 = 等差数列 + 普通版插入排序

循环数组

考研算法29天：希尔排序【希尔排序】

第一次每n/2为间隔分为4组，然后组内排序。

第二次每n/4为间隔分为2组。然后组内排序

第三次n/8为间隔分为一组。然后组内排序。

组内排序用插入排序来排序。

注：也可以第一次为n/3为间隔，第二次为n/3^2,，第三次为n/3^3.这个随你定义。

考研算法29天：希尔排序【希尔排序】

上面这个图片是讲采用3的分法的话最坏算法时间复杂度只有O(n*开平方n)。

考研算法29天：希尔排序【希尔排序】

c++中的sort = 快排 + 插排

算法题目

考研算法29天：希尔排序【希尔排序】

算法ac代码：

#include <iostream>

using namespace std;

const int N = 1000010;
int q[N];

void shell_sort(int n){
    for(int d=n/2;d>=1;d = d/2)//算出每次的公差
    {
        
        for(int start=0;start<d;start++)//每次的开始下标
        {
            //插入排序
            for(int i=start+d;i<n;i=i+d){
                int x = q[i],j=i;
                while(j>start&&q[j-d]>x){
                    q[j] = q[j-d];
                    j = j-d;
                }
                q[j] = x;
            }
            
        }
    }
    return;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)scanf("%d",&q[i]);
    shell_sort(n);
    for(int i=0;i<n;i++)printf("%d ",q[i]);
    return 0;
}