目录
1.前言
2.直接插入排序
3.希尔插入排序
题目描述
输入输出样例
样例输入 #1
样例输出 #1
希尔排序的增量选择会对算法时间复杂度产生很大影响，上面的增量序列采用的是原始Shell增量序列，适用于数据量较少的情况。下面给出常用的增量公式Hibbard 序列
4.感言
1.前言
最近学习比较繁忙，一直没有抽出时间整理，难得有一个比较清闲的周末，专门写一篇笔记来整理一下排序方法，这里主要讲插入排序。算法思想是将待排序的序列分为已排序和未排序两部分，每次从未排序部分取出一个元素，在已排序部分中找到合适的位置插入，使已排序部分始终保持有序。
2.直接插入排序
大家一开始接触的排序除了冒泡排序与选择排序外，就是插入排序了。这算是时间复杂度为O(n^2)的排序中平均情况下比较快的排序了，在比较元素后可能正好是最大值，直接插入到原排序中，也就省去了移动过程。
#include<bits/stdc++.h> using namespace std; const int N=1e7; int arr[N]; int main(int argc, char** argv) { int n; cin>>n; if(n<=1) { cout<<"无需排序"<<endl; return 0; } for(int i=0;i<n;i++) cin>>arr[i]; for(int i=1;i<n;i++){ int k=arr[i]; //相当于拿出一个元素 ，这样就腾出了一个空位置，即arr[n] int j=i-1; //双指针，i指向当前空位置 ，j指向前序列元素 的位置 while(j>=0&&arr[j]>k){ //采用移动元素，而不是每次比较做交换 arr[j+1]=arr[j]; j--; } //最终j停留在arr[j]<=k的位置 ,arr[j+1]可以看做一个空位置 arr[j+1]=k; } for(int i=0;i<n;i++){ cout<<arr[i]<<" "; } cout<<endl; return 0; }3.希尔插入排序
这是上世纪50年代唐纳德·L·希尔（Donald L. Shell）的算法，这也是计算机历史上的第一个突破时间复杂度O（n^2）的算法，达到了约O（n^1.3）。（具体时间复杂度目前算不清）
简单来说，核心思想是通过设定某增量序列，将大序列分成小序列，插入排序每个小序列，再不断缩小增量，继续进行插入排序，逐渐提高序列的有序性，最终实现整个序列的排序。具体来说，通过设定增量为p,我们就可以将序列分为p组，这些组的序列分别满足{x1}%p==0,{x2}%p==1……{xp}%p==p-1。不难发现，当p=1时，就是直接插入排序。
题目描述
给你10个数，设计一个程序，实现希尔插入排序算法，并输出这个序列的希尔排序过程。
输入
1行10个数，两个数之间有空格隔开，所有数均不超过10^9
输出
每个排序过程输出一行，直到排序完成。
输入输出样例
样例输入 #1
9 8 7 6 5 4 3 2 1 0样例输出 #1
4 3 2 1 0 9 8 7 6 5 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9代码如下
#include <bits/stdc++.h> using namespace std; int main(){ int n=10; int arr[n]; for(int i=0;i<n;i++) cin>>arr[i]; int gap; for(gap=n/2;gap>0;gap/=2){ for(int i=gap;i<n;i++){ int k=arr[i]; int j=i; while(j>=gap&&arr[j-gap]>k){ arr[j]=arr[j-gap]; j-=gap; } arr[j]=k; } for(int i=0;i<n;i++) cout<<arr[i]<<" "; cout<<endl; } return 0; }补充
希尔排序的增量选择会对算法时间复杂度产生很大影响，上面的增量序列采用的是原始Shell增量序列，适用于数据量较少的情况。下面给出常用的增量公式Hibbard 序列
Hibbard 序列是希尔排序中一种经典的增量序列。它通过公式
1,3,7,15,31,63,127,255,511,1023……生成，其中 kk为正整数，增量值依次为：
使用时通常取小于数组长度 n的最大值作为初始增量，然后按递减顺序取完所有值，最后以 1 结束
4.感言
都说学算法是重复造轮子，但我觉得更重要是学会用轮子。站在前人的肩膀上，虽然我是当下的菜鸡，但在百年前未必不是算法大佬（狗头）。
