希尔排序(shell sort)学习笔记

什么是希尔排序

一种进阶版的插入排序，不稳定（因为多次插入了），适合大范围顺序不是太乱的数据排序（这点跟插入有点像）
首先先引入插入排序：

插入排序

这是一种稳定的排序算法（因为每次排序时只是把其他元素进行平移，相等大小的元素们的相对位置并没有改变）。
实现方法
就像整理扑克牌一样，将第i张牌与前i-1张牌面额逐个比较，如果找到最前面的那个大于第i张牌面额的牌的位置p，则先将从p开始到i-1的所有牌的位置后移一格，然后将这第i张牌插入到p位置，从第一张牌开始整理，到第n张牌结束，如此重复操作，最终实现排序。

具体实现方法如下：
1.将开头元素视作已排序
2.对于未排序的部分
1.取出未排序部分的开头元素给变量v
2.在已排序部分，将所有比v大的元素后移一个单位
3.将v插入空位

复杂度分析
优点：对于相对顺序变化不大的数列，插入排序有着极高的效率，比如：1 2 4 3 5
缺点：如果数列完全是反序排列，算法效率将很差很差。比如：6 5 4 3 2 1

在插入排序的基础上，改变插入排序循环里的迭代周期（插入排序中是1，shell sort中是g[i])
同时数组g（周期数组）的选取以g(i+1)=3*g(i)+1（注意无论怎么写边界条件一定要是g(1)=1)
然后shell sort就是不断循环间隔为for (int i=m-1; i>0; i++) insert_sort(n,g[i])的操作
这里m的取值为g[m]<=n的上限
其实g[i]也可以这么理解，就是仅处理数列里间隔为g[i]的部分
比如g[i]=2;数列为：1 2 3 6 5 4
那么这一轮处理的实际上是对2 6 4这个数列进行插入排序。
以下是一段AC的代码

#include<bits/stdc++.h>using namespace std;int g[1000001];int a[1000001];int n,cnt,m,t=1;bool f;void insertsort(int n,int s){int v,j;for (int i=s; i<n; i++){v=a[i];j=i-s;while (j>=0 && a[j]>v){a[j+s]=a[j];cnt++;j-=s;}a[j+s]=v;}}int main(){cin>>n;cnt=0; m=0; f=true;for (int i=0; i<n; i++){cin>>a[i];if (f){if (t<=n)g[m++]=t;else f=false;t=3*t+1;}}cout<<m<<endl;cout<<g[m-1];for (int i=m-2; i>=0; i--)cout<<\' \'<<g[i];cout<<endl;for (int i=m-1; i>=0; i--)insertsort(n,g[i]);cout<<cnt<<endl;for (int i=0; i<n; i++){cout<<a[i]<<endl;}return 0;}

OJ评测地址：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_D