算法介绍
希尔排序 = 等差数列 + 普通版插入排序
循环数组
第一次每n/2为间隔分为4组，然后组内排序。
第二次每n/4为间隔分为2组。然后组内排序
第三次n/8为间隔分为一组。然后组内排序。
组内排序用插入排序来排序。
注：也可以第一次为n/3为间隔，第二次为n/3^2,，第三次为n/3^3.这个随你定义。
上面这个图片是讲采用3的分法的话最坏算法时间复杂度只有O(n*开平方n)。
c++中的sort = 快排 + 插排
算法题目
算法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;
}算法复杂度
时间复杂度：
要看你是按照啥规矩分的组，不同分组的时间复杂度不一样，如果是按照“2”的话时间复杂度为O（N^2）
空间复杂度
O(1)
稳定性：
原先的元素的相对位置会不一样，所以不稳定。
快排和希尔排序时间复杂度最坏情况是不考虑的，其发生这样的情况的概率就如小型星球撞地球的概率一样，可以忽略不计。
本文链接：https://my.lmcjl.com/post/11804.html
展开阅读全文
4 评论