/*直接插入：把待排序序列分为有无序区和和无序区，使用无序区的数据一次插入倒有序区中，最终结果尾有序序列
1> 把数据分为有序区和无序区，默认第一个元素在有序区，剩下在无序区
2> 外层循环，循环无序区 的元素 for(i=1;i<n;i++)
3> 内层循环，倒序循环有序区 for(j=i-1;j>=0&&arr[j]>temp;j–)
4> 【升序】有序区元素如果大于插入的元素，后移arr[j+1]=arr[j]
5> 在j+1下标插入temp
时间复杂度：O（n^2）*/
#include<stdio.h>
int main(int argc, const char *argv[])
{int i,j;int arr[7]={4,2,3,1,5,6,7};int n=sizeof(arr)/sizeof(arr[0]);for(i=1;i<n;i++){int temp=arr[i];for(j=i-1;j>=0&&temp<arr[j];j--){arr[j+1]=arr[j];}arr[j+1]=temp;}for(int i=0;i<n;i++){printf("%d\t",arr[i]);}return 0;
}
//希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
//随着增量逐渐减少，每组包含的越来越多，当增量减至 1 时，整个文件恰被分成一组
//最后都会走到直接插入的地步
//希尔排序时间复杂度低
//时间复杂度：O（n^1.5）
#include<stdio.h>
int main(int argc, const char *argv[])
{int arr[]={4,5,3,1,2,6,7,1};int n=sizeof(arr)/sizeof(arr[0]);int k=n/2;int j;while(k>=1){for(int i=k;i<n;i=i+k){int temp=arr[i];for(j=i-k;j>=0&&temp<arr[j];j=j-k){arr[j+k]=arr[j];}arr[j+k]=temp;}k=k/2;}for(int i=0;i<n;i++){printf("%d\t",arr[i]);}return 0;
}
// 快排n*logn
//、从待排序的序列中，任意选择一个元素作为基准
// 2、将其他元素与基准进行比较，分为大小两个部分
// 3、再对各个部分重新选定基准，并以上述两步重复进行，直到每个部分只剩一个元素为止
#include<stdio.h>
int oneSort(int arr[],int low,int high)
{int key=arr[low];while(low<high){while(low<high&&key<=arr[high]){high--;}arr[low]=arr[high];while(key>=arr[low]&&low<high){low++;}arr[high]=arr[low];}arr[low]=key;return low;
}
void Quick(int arr[],int low,int high)
{
if(low<high){int mid=oneSort(arr,low,high);Quick(arr,low,mid-1);Quick(arr,mid+1,high);}
}int main(int argc, const char *argv[])
{int arr[]={1,2,4,9,6,3,2,1};int len=sizeof(arr)/sizeof(arr[0]);Quick(arr,0,len-1);for(int i;i<len;i++){printf("%d\t",arr[i]);}return 0;
}
二路归并：将待排序序列以中间值mid为界均分为左右两部分，左右两部分继续均分，直到序列中只有一个元## 素为止，逐级将左右两部分有序合并到一个新数组中**
#include<stdio.h>
void combin(int arr[],int low,int high,mid)
{int len=high-low+1;int temp[len];int i=low,j=mid+1,k=0;while(i<mid&&j<=high){if(arr[i]<=arr[j]){temp[k++]=arr[i++]}else{temp[k++]=arr[j++];}}while(i<=mid){temp[k++]=arr[i++];}while(j<=high){temp[k++]=arr[j++];}for(int i=0;i<len;i++){arr[low++]=temp[i++];}
}
void guibing(int arr[],int low,int high)
{if(low>=high){return;}int mid=(low+high)/2;mergersort(arr,low,mid);mergersort(arr,mid+1,high);combin(arr,low,high,mid);
}
int main(int argc, const char *argv[])
{int arr[]={1,2,3,5,9,6,2,1,3};int len=sizeof(arr)/sizeof(arr[0]);mergersort(arr,0,len-1);return 0;
}
查找：给定关键字，查找关键字是否存在
1> 顺序查找O(n)
1.1 存在性查找：查找数据是否存在
1.2 个数查找：查找关键字存在几次
2>折半查找：有顺序的顺序存储
注意：折半查找只能对有序序列进行查找
时间复杂度：O（n/2）**
int halfSearch(int arr[],int low,int high,int key)
{int mid;while(low<=high){mid=(low+high)/2;if(key==arr[mid]){return mid;}else if(key>arr[mid]){low=mid+1;}else{high=mid-1;}}return -1;
}
int main(int argc, const char *argv[])
{int arr[]={12,32,45,65,67,87,89,97};int len=sizeof(arr)/sizeof(arr[0]);int key;printf("输入查找的值：");scanf("%d",&key);int flag=halfSearch(arr,0,len-1,key);if(flag==-1)printf("%d不存在\n",key);elseprintf("在%d下表出现",flag);return 0;
}
