插入排序
直接插入排序
直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
插入排序算法其实很好理解，我们在玩扑克牌的时候，通常喜欢左手拿着排好序的牌，右手拿一张牌然后在左手找位置插入，基本上就是这个思想。我们整理牌的方法，其实就是直接插入排序。
在这里插入图片描述
对于插入排序，我们可以有两种构造
- 设定哨兵位，即在数组第一位留空，循环中每一次要排序的那个数（从第二个数开始）先赋值给哨兵位，然后相应数字往后移动。说到底这个哨兵位起到暂时储存值的作用。
- 用变量temp来储存要排序的那个值，以下代码是这个方法的实现。
void insertSort(int* a,int len)
{
int i,j,temp;
for(i=1;i<len;i++) //数组中从第二个数开始（假设第一个数已经是排好的）
{ //遍历后面每一个数，进行插入排序操作
temp=a[i]; //把要排序的那个数先拿出来
for(j=i-1;a[j]>temp;j--) //逐一比较
{
a[j+1]=a[j]; //数组中在temp之前的每一个数向后移动
}
a[j+1]=temp; //找到了要插入的位置，插入
} //由于for循环中最后j--了，所以是a[j+1]，而不是a[j]
}
希尔排序
分享一篇有助于学习希尔排序的文章：图解希尔排序
希尔排序(Shell Sort)是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
那怎么理解这个定义呢？什么是增量？
其实希尔排序的关键，并不是随便分组然后各自排序的，而就是按这个增量，也就是下标相隔的距离来进行分组，各个子序列有序，跳跃排序，到最终到整体有序。
选取增量的方式，是个世界难题，迄今为止没有人找到一种最好的增量序列。
在《大话数据结构》中是用increment = increment/3+1的方式（兼顾奇偶），在上面分享的那篇文章，则是用gap = gap/2折半的方式来缩小增量。
void shellSort(int* a,int n)
{ //j,i两个循环变量，gap每次分组中元素的物理位置间隔(以元素大小为单位)，x一个暂时存放插入值的变量
int j,gap=n/2,i,x;
for(gap;gap>0;gap/=2)//每次改变每组中元素的物理位置间隔
for(i=gap;i<n;i++){
//（当不是最后一次时）当i自加时，实质就是跳到了下一个分组上（总是对分组的第二个元素进行排序）
x=a[i];
for(j=i-gap;j>=0&&x<a[j];j-=gap)//若x小于a[j]元素的值，
{ //则将a[j]赋值给a[j]的下一个逻辑单元并移动j到j的上一个逻辑值 （找到x的插入点的前一个逻辑点）
a[j+gap]=a[j];
}
a[j+gap]=x;//将x插入
}
}
下面我们再来看一次直接插入排序和希尔排序的动画对比：
直接插入排序
希尔排序
希尔排序不愧是第一批突破O(n^2)时间的算法，用一个简单的思想就能够完成高效的算法排序。
归并排序
归并排序（Merging Sort）是利用归并的思想实现的排序方法，该算法采用经典的==分治==（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
分治思想
归并排序
归并排序的递归实现，我们需要两个函数来完成，一个函数用于完成分而治之的工作，另一个函数调用上一个函数完成递归工作。
代码实现及其说明：
void Merge(int SR[],int TR[],int i ,int m ,int n)
{
int j,k,l;
for(j=m+1,k=i;i<=m && j<=n;k++) //两个序列，i第一个序列起点，j=m+1第二个序列起点
{ //将SR中记录有小到大归并入TR
if (SR[i]<SR[j])
TR[k]=SR[i++]; //第一个序列的第一个比第二个序列的第一个小，所以赋值然后i+,取第一个序列的下一个
else
TR[k]=SR[j++];
}
if(i<=m)
{
for (l=0;l<=m-i;l++)
TR[k+l]=SR[i+l]; //将剩余的SR[i...m]复制到TR
}
if(j<=n)
{
for (l=0;l<=n-j;l++)
TR[k+l]=SR[j+l]; //将剩余的SR[j...m]复制到TR
}
}
void MSort(int SR[],int TR1[],int s,int t )
{
int m;
int TR2[MAXSIZE+1];
if (s==t)
{
TR1[s]=SR[s];
}
else
{
m=(s+t)/2;//将SR平分为两个SR
MSort(SR,TR2,s,m);//递归将SR（前半段）归并为有序的TR2
MSort(SR,TR2,m+1,t);//递归将SR（后半段）归并为有序的TR2
Merge(TR2,TR1,s,m,t); //传三个参数目的 起点，分离点 ，终点
//将TR2（前半段）和TR2（后半段）归并到TR1
}
}
/**
*代码来自《大话数据结构》，我们要使用写好的归并排序，就是调用 MSort()函数
* 参数说明：SR[]和TR1[]最开始传参的时候都是传入数组a
* s和t分别是1和最大下标，数组下标从1开始
* MSort()的作用：将SR[s...t]归并排序为TR1[s...t]
* Merge()的作用：将有序的SR[i...m]和SR[m+1...n]归并为有序的TR[i...n]
*/
