前言：
嗐，很久没更新博客了，因为这几个月都在搞学习（大部分时间都在闯王者峡谷，哈哈），最近刚过了一遍数据结构与算法，所以想着趁热打铁，把一些重要的、基础的知识点整理起来，等以后复习的时候能够派上用场。于是为大家带来了撕烂数据爆锤算法系列（听起来很牛批，实际上菜的一批，哈哈)。当然作为毅力超群的我，会持续更新的啦。若有啥不足之处，欢迎大佬们喷一喷（手下留情啊）。最后，希望我的总结能对你们有所帮助，这将是我的荣幸！
同是天涯码字猿，
共勉，共勉~~~
正文：
一、基础概述：
如果N=1，则序列有序。如果N>1，则先将第1个数据元素看成有序的子序列，其他数据元素看成无序子序列。从第2个数据元素开始从无序子序列逐个取出一个数据元素，插入有序子序列中，从而使有序子序列逐渐变长，无序子序列逐渐变短，最后整个序列完全有序。特征：需要比较的次数越多，排序效率越低；移动数据元素个数越多，排序效率越低。总的来说，序列的有序水平越高，排序就越快。
二、实现方式：
a.直接插入排序；
b.二路插入排序；
c.希尔排序
三、3.时间（或空间）复杂度:
a.直接插入：最坏情况O(n^2)，比较一次；最好情况：O(n)，平均比较次数：n/2；属于稳定算法。
b.二路插入:与直接插入相比，虽然会减少数据移动总量，但是这种减少却与数据规模无关，而与数据自身的排序状态有关，所以时间复杂度与直接插入相同。
c.希尔排序:希尔排序时间复杂度估算十分复杂，它与dlta(取元素的间隔数)的值有关，目前还没有一致的结论。
四、代码实现：
一、直接插入排序：
1.定义头文件：
#include<stdio.h>
#define MAXSIZE 100
int main(); //主函数
void InitDate(int Date[],int &n); //初始化待排元素
void Sort(int Date[],int n); //插入排序
void Traverse(int Date[],int n); //遍历排序结果2.初始化待排元素：
void InitDate(int Date[],int &n) //初始化待排元素
{
int i;
printf("\n请输入待排元素个数:");
scanf("%d",&n);
putchar(10);
for(i=1;i<=n;i++)
{
printf("\n请输入待排元素:");
scanf("%4d",&Date[i]);
}
putchar(10);
return;
}3.直接插入排序（核心）：
void Sort(int Date[],int n) //直接插入排序
{
int i,j,temp;
for(i=2;i<=n;i++) //假定第一个元素已排，故从第二个待排元素开始
{
temp=Date[i]; //记录当前待排元素
for(j=i;j>1&&Date[j-1]>temp;j--) //待排元素与已排元素进行比较，若已排元素>待排元素，将已排元素向后移一位
Date[j]=Date[j-1];
Date[j]=temp; //插入待排元素
}
return;
}4.遍历排序结果：
void Traverse(int Date[],int n) //遍历排序结果
{
int i;
printf("\n排序结果为:");
for(i=1;i<=n;i++)
printf("%4d",Date[i]);
putchar(10);
return;
}5.主函数：
int main()
{
int n,Date[MAXSIZE];
InitDate(Date,n);
Sort(Date,n);
Traverse(Date,n);
return 0;
}二、二路插入排序
1.定义头文件：
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
int main(); //主函数
void InitDate(int Date[],int &n); //初始化待排元素
void SortOne(int Date[],int n); //二路插入排序(方法一)
void SortTwo(int Date[],int n); //二路插入排序(方法二)
void Traverse(int Date[],int n); //遍历排序结果2.初始化待排元素：
void InitDate(int Date[],int &n) //初始化待排元素
{
int i;
printf("\n请输入待排元素个数:");
scanf("%d",&n);
putchar(10);
for(i=0;i<n;i++)
{
printf("\n请输入待排元素:");
scanf("%4d",&Date[i]);
}
putchar(10);
return;
}3.二路插入排序(方法一)（核心）：
void SortOne(int Date[],int n) //二路插入排序(方法一)
{
int *Copy,i,k,first,last;
Copy=(int *)malloc(sizeof(int)*n); //分配存放有序子序列的数组
if(!Copy) return;
first=last=0; //first:最小单元指针，last:最大单元指针，此处初始化指针
Copy[0]=Date[0]; //取无序序列中第一个元素为有序子序列第一个元素
for(i=1;i<n;i++)
{
if(Date[i]<Copy[first]) //待插入元素比有序序列中的最小值小，将其插入到Copy[first]前，并将first指向该值
{
first=(first-1+n)%n;
Copy[first]=Date[i];
}
else if(Date[i]>Copy[last]) //待插入元素比有序序列中的最大值大，将其插入到Copy[last]后，并将last指向该值
{
last=(last+1+n)%n;
Copy[last]=Date[i];
}
else //待插入元素比有序序列中的最小值大，最大值小，寻找合适位置进行插入
{
k=(last+1+n)%n; while(Copy[(k-1+n)%n]>Date[i])
{
Copy[(k+n)%n]=Copy[(k-1+n)%n];
k=(k-1+n)%n;
}
Copy[(k+n)%n]=Date[i];
last=(last+1+n)%n;
}
}
for(i=0;i<n;i++)
Date[i]=Copy[(i+first)%n]; //将有序序列从Copy复制到Date中
free(Copy);
return;
}4.二路插入排序(方法二)（核心）：
void SortTwo(int Date[],int n) //二路插入排序(方法二)
{
int i,last,first,k,*a;
a=(int *)malloc(sizeof(int)*n); //分配存放有序子序列的数组
if(!a) return;
last=first=0; //first:首单元指针，last:尾单元指针，此处初始化指针
a[0]=Date[0]; //取无序序列中第一个元素为有序子序列第一个元素
for(k=1;k<n;k++) //依次将Date[K]插入到a中的有序子序列中
{
if(Date[k]>=a[0]) //将Date[k]插入到a[0]的右边
{
i=last; while(i>=0&&a[i]>Date[k])
{
a[i+1]=a[i];
i--;
}
a[i+1]=Date[k];
last++;
}
else //将Date[k]插入到a[0]的左边，即从数组末位向左插入
{
first--;
if(first==-1)
first=n-1;
i=first+1; while(i<n&&a[i]<=Date[k]) //为了使排序是稳定的，此处使用<=
{
a[i-1]=a[i];
i++;
}
a[i-1]=Date[k];
}
}
i=first;
k=0; while(k<n) //将有序序列从a复制到Date中
{
Date[k]=a[i];
k++;
i=(i+1)%n;
}
free(0);
}5.遍历排序结果：
void Traverse(int Date[],int n) //遍历排序结果
{
int i;
printf("\n排序结果为:");
for(i=0;i<n;i++)
printf("%4d",Date[i]);
putchar(10);
return;
}6.主函数：
int main() //主函数
{
int n,Date[MAXSIZE];
InitDate(Date,n);
SortOne(Date,n);
SortTwo(Date,n);
Traverse(Date,n);
return 0;
}三、希尔排序
1.定义头文件：
#include<stdio.h>
#include<math.h>
#define MAXSIZE 100
int main(); //主函数
void InitDate(int Date[],int &n); //初始化待排元素
void Sort(int Date[],int n); //希尔排序
void Traverse(int Date[],int n) //遍历排序结果2.初始化待排元素：
void InitDate(int Date[],int &n) //初始化待排元素
{
int i;
printf("\n请输入待排元素个数:");
scanf("%d",&n);
putchar(10);
for(i=1;i<=n;i++)
{
printf("\n请输入待排元素:");
scanf("%4d",&Date[i]);
}
putchar(10);
return;
}3.希尔排序（核心）：
void Sort(int Date[],int n) //希尔排序(三总增量用一种即可)
{
int i,j,temp,k,m;
for(k=n/2;k>0;k/=2) //增量:kn=n/2
{
for(i=1+k;i<=n;i++)
{
temp=Date[i];
for(j=i;j>k&&Date[j-k]>temp;j-=k)
Date[j]=Date[j-k];
Date[j]=temp;
}
}
for(m=n;m>=1;m--) //Hibbard增量序列in=2^n-1,时间复杂度:T=O（N^(3/2)）
{
i=pow(2,m)-1;
for(k=i+1;k<=n;k++)
{
temp=Date[k];
for(j=k;j>i&&Date[j-i]>temp;j-=i)
Date[j]=Date[j-i];
Date[j]=temp;
}
}
for(m=n;m>=1;m--) //Sedgewick增量序列in=4^n-3*2^n+1,时间复杂度:T(avg)=O(N^(7/6))
{
i=pow(4,m)-3*pow(2,m)+1;
for(k=i+1;k<=n;k++)
{
temp=Date[k];
for(j=k;j>i&&Date[j-i]>temp;j-=i)
Date[j]=Date[j-i];
Date[j]=temp;
}
}
return;
}4.遍历排序结果：
void Traverse(int Date[],int n) //遍历排序结果
{
int i;
printf("\n排序结果为:");
for(i=1;i<=n;i++)
printf("%4d",Date[i]);
putchar(10);
return;
}5.主函数：
int main() //主函数
{
int n,Date[MAXSIZE];
InitDate(Date,n);
Sort(Date,n);
Traverse(Date,n);
return 0;
}看完这<撕烂数据爆锤算法：内排序之插入算法>，是否还意犹未尽，那么就跟着我进入推荐环节吧（恬不知耻的我，死活都要自荐一翻，哈哈）。
小小推荐：
撕烂数据锤爆算法系列：
撕烂数据爆锤算法：循环链表
撕烂数据爆锤算法：单链表
撕烂数据爆锤算法：内排序之交换算法
前端案例系列：
前端小案例：登录页面
C语言案例系列：
C语言小案例：登录界面
C语言小案例：学生管理系统1.0版
感谢浏览，你们的支持就是我的动力，下次再见喽~~~
京公网安备 11010502036488号