插入排序：
1.直接插入排序
2.折半插入排序
3.希尔排序
**排序的三种特性：
**1.时间复杂度
算法的时间复杂度是一个函数，它定性描述该算法的运行时间
2.空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度
3.稳定性
初始数列中有R[i]和R[j]两个元素，两个元素相等（R[i]==R[j]）,且i<j，
当经过某种排序以后，R[i]元素位置变为i’，R[j]元素位置变为j’，
如果在排序之后，i’<j’，R[i’]位置依然在R[j’]之前，那么称之为稳定排序
稳定性无关一个排序的好坏，只是考虑特定的场合
直接插入：
将下标为i的元素直接插入到下标范围[0,i-1]的数组中，插入后的数组[0,i]
依然要求保持有序
时间复杂度为(On^2)
空间复杂度为(O1)
void insertSort(int arr[],int n){
int i,j;
int key = 0;
for(i=1;i<n;i++){//i=0,只有一个元素，本身就是有序的，不需要插入，i=1从第二个元素开始，逐一往前插入，使之保持有序
key = arr[i];//提前保存要插入的元素 因为前面的元素往后移，会覆盖后面的元素
for(j=i-1;j>=0&&arr[j]>key;--j){
arr[j+1] = arr[j];
}
if(i!=j+1){//i==j+1
arr[j+1] = key;//arr[i]=key;
}
}
}
输入示例数组：
{1,8,9,3,4,7,0,2,5,6}
i=1,key=arr[1]=8,
j=0,arr[0+1]=key=8; 1,8…
i=2,key=arr[2]=9,
j=1,arr[1+1]=9; 1,8,9…
i=3,key=3
j=2,arr[3]=arr[2]=9,arr[2]=arr[1]=8,arr[1]=3; 1,3,8,9…
i=4,key=4,
j=3,arr[4]=arr[3]=9,arr[3]=arr[2]=8,arr[2]=4; 1,3,4,8,9…
…
折半插入排序：
将数组一分为2，与数组的最中间的元素进行比较，如果元素比中间的元素小，则保留数组的前半段，继续选取中间的元素进行比较
时间复杂度为(On^2)
空间复杂度为(O1)
void bininsertSort(int arr[],int n){
int left,right,mid,i,j,key;
for(i=1;i<n;i++){//arr[1]----arr[n-1]所有的元素依次往前插入
key=arr[i];//保存要插入的元素arr[i]
for(left=0,right=i-1;left<=right;){//找到arr[i]插入的位置 折半查找
mid = (left+right)/2;
if(key < arr[mid]){
right = mid - 1;
}else{
left = mid + 1;
}
}
//right+1位置要存储arr[i] key
for(j=i-1;j>right;--j){
arr[j+1] = arr[j];
}
arr[right+1] = key;
}
}
输入示例数组：
{1,8,9,3,4,7,0,2,5,6}
i=1,left=0,right=0,mid=0,
key=arr[1]=8,key>arr[mid],left=1,
j=0,arr[1]=8; 1,8
i=2,left=0,right=1,mid=0,
key=9,key>arr[mid],left=1,
j=1,arr[2]=9; 1,8,9
i=3,left=0,right=2,mid=1,
key=3,key<arr[mid],right=1,
j=2,j>right,arr[3]=arr[2]=9,arr[2]=arr[1]=8,arr[1]=3; 1,3,8,9
…
2路插入排序：
折半插入的一种
申请一个和原始数组相同内存的数组brr，开始时往左插，当遇到比brr[0]小的值时插入到右边brr[i-1]
时间复杂度(On^2)
空间复杂度(O1)
void twoRoadInsert(int arr[],int n){
int *brr = (int *)malloc(sizeof(arr[0])*n);//申请一个相同内存的数组
int left = -1,right = n;
int i,j;
for(i=0;i<n;i++){
if(left==-1||arr[i]>brr[0]){//left==-1时给brr[0]一个初始值，当元素大于最左端的元素brr[0]时插入到brr[0]后
for(j=left;j>=0&&arr[i]<brr[j];--j){
brr[j+1] = brr[j];
}
brr[j+1] = arr[i];
++left;
}else{//<brr[0] 如果要插入左边 左边所有元素都要移动
for(j=right;j<n&&arr[i]>brr[j];++j){
brr[j-1] = brr[j];
}
brr[j-1] = arr[i];
--right;
}
}
for(i=right;i<n;i++){
arr[i-right] = brr[i];
}
for(i=0;i<=left;i++){
arr[n-right+i] = brr[i];
}
}
示例数组：
1,8,9,3,4,7,0,2,5,6
i=0,left=-1,right=10,
j=-1,brr[0]=arr[0]=1,left=0; 1
i=1,left=0,right=10,
j=0,brr[1]=arr[1]=8,left=1; 1,8
i=2,left=1,right=10,
j=1,brr[2]=arr[2]=9,left=2; 1,8,9
i=3,left=2,right=10,
j=2,arr[3]<brr[2],brr[3]=brr[2]=9,brr[2]=brr[1]=8,brr[1]=3,left=3; 1,3,8,9
i=4,left=3,right=10,
j=3,arr[4]<brr[3],brr[4]=brr[3]=9,brr[3]=brr[2]=8,brr[2]=4,left=4; 1,3,4,8,9
…
i=6,left=5,right=10,
arr[6]<brr[0],j=right=10,brr[9]=arr[6]=0;right=9; 1,3,4,7,8,9, , , ,0
…
示例特殊，只使用了一次right
希尔排序：
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
时间复杂度(On^(1.3-2))
空间复杂度(O1)
void shellSort(int arr[],int n){
//分组 分为step个小组 组内元素步长step
int step,i,j;
for(step=n/2;step>0;step=step/2)//分组
//组内排序 [0,step)组内的第一个元素
for(i=step;i<n;i++){//除了组内第一个元素 其他元素都需要进行组内排序
int key = arr[i];
for(j=i-step;j>=0&&key<arr[j];j=j-step){
arr[j+step] = arr[j];
}
arr[j+step] = key;
}
}
