网站建设的计划,深圳设计公司办公室,大型网页游戏排行榜,中国品牌网站官网/*直接插入#xff1a;把待排序序列分为有无序区和和无序区#xff0c;使用无序区的数据一次插入倒有序区中#xff0c;最终结果尾有序序列
1 把数据分为有序区和无序区#xff0c;默认第一个元素在有序区#xff0c;剩下在无序区
2 外层循环#xff0c;循环无…/*直接插入把待排序序列分为有无序区和和无序区使用无序区的数据一次插入倒有序区中最终结果尾有序序列
1 把数据分为有序区和无序区默认第一个元素在有序区剩下在无序区
2 外层循环循环无序区 的元素 for(i1;in;i)
3 内层循环倒序循环有序区 for(ji-1;j0arr[j]temp;j–)
4 【升序】有序区元素如果大于插入的元素后移arr[j1]arr[j]
5 在j1下标插入temp
时间复杂度On^2*/
#includestdio.h
int main(int argc, const char *argv[])
{int i,j;int arr[7]{4,2,3,1,5,6,7};int nsizeof(arr)/sizeof(arr[0]);for(i1;in;i){int temparr[i];for(ji-1;j0temparr[j];j--){arr[j1]arr[j];}arr[j1]temp;}for(int i0;in;i){printf(%d\t,arr[i]);}return 0;
}//希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序
//随着增量逐渐减少每组包含的越来越多当增量减至 1 时整个文件恰被分成一组
//最后都会走到直接插入的地步
//希尔排序时间复杂度低
//时间复杂度On^1.5
#includestdio.h
int main(int argc, const char *argv[])
{int arr[]{4,5,3,1,2,6,7,1};int nsizeof(arr)/sizeof(arr[0]);int kn/2;int j;while(k1){for(int ik;in;iik){int temparr[i];for(ji-k;j0temparr[j];jj-k){arr[jk]arr[j];}arr[jk]temp;}kk/2;}for(int i0;in;i){printf(%d\t,arr[i]);}return 0;
}// 快排n*logn
//、从待排序的序列中任意选择一个元素作为基准
// 2、将其他元素与基准进行比较分为大小两个部分
// 3、再对各个部分重新选定基准并以上述两步重复进行直到每个部分只剩一个元素为止
#includestdio.h
int oneSort(int arr[],int low,int high)
{int keyarr[low];while(lowhigh){while(lowhighkeyarr[high]){high--;}arr[low]arr[high];while(keyarr[low]lowhigh){low;}arr[high]arr[low];}arr[low]key;return low;
}
void Quick(int arr[],int low,int high)
{// if(lowhigh){// return;// }
// if(lowhigh){
// return;
// }if(lowhigh){int midoneSort(arr,low,high);Quick(arr,low,mid-1);Quick(arr,mid1,high);}
}int main(int argc, const char *argv[])
{int arr[]{1,2,4,9,6,3,2,1};int lensizeof(arr)/sizeof(arr[0]);Quick(arr,0,len-1);for(int i;ilen;i){printf(%d\t,arr[i]);}return 0;
}二路归并将待排序序列以中间值mid为界均分为左右两部分左右两部分继续均分直到序列中只有一个元## 素为止逐级将左右两部分有序合并到一个新数组中**
#includestdio.h
void combin(int arr[],int low,int high,mid)
{int lenhigh-low1;int temp[len];int ilow,jmid1,k0;while(imidjhigh){if(arr[i]arr[j]){temp[k]arr[i]}else{temp[k]arr[j];}}while(imid){temp[k]arr[i];}while(jhigh){temp[k]arr[j];}for(int i0;ilen;i){arr[low]temp[i];}
}
void guibing(int arr[],int low,int high)
{if(lowhigh){return;}int mid(lowhigh)/2;mergersort(arr,low,mid);mergersort(arr,mid1,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 lensizeof(arr)/sizeof(arr[0]);mergersort(arr,0,len-1);return 0;
}
查找给定关键字查找关键字是否存在
1 顺序查找O(n)
1.1 存在性查找查找数据是否存在
1.2 个数查找查找关键字存在几次
2折半查找有顺序的顺序存储
注意折半查找只能对有序序列进行查找
时间复杂度On/2**
//存在返回下标失败返回
int halfSearch(int arr[],int low,int high,int key)
{int mid;while(lowhigh){mid(lowhigh)/2;if(keyarr[mid]){return mid;}else if(keyarr[mid]){lowmid1;}else{highmid-1;}}return -1;
}
int main(int argc, const char *argv[])
{/*
mid(lowhigh)/287
12,32,45,65, 67,87,89,97
LOW mid high67 87 89 97low mid high lowmid1*/int arr[]{12,32,45,65,67,87,89,97};int lensizeof(arr)/sizeof(arr[0]);int key;printf(输入查找的值);scanf(%d,key);int flaghalfSearch(arr,0,len-1,key);if(flag-1)printf(%d不存在\n,key);elseprintf(在%d下表出现,flag);return 0;
}//存在返回下标失败返回
