【题目来源】
https://oj.czos.cn/p/1010
【题目描述】
对数组的元素按从小到大进行排序。
【输入格式】
第一行有一个整数 n（5≤n≤10）；
第二行有 n 个整数，每个整数的值在 [0, 10^9]的范围内。
【输出格式】
输出排序后的数组。
【输入样例】
8
1 2 3 6 8 7 4 5
【输出样例】
1 2 3 4 5 6 7 8
【数据范围】
5≤n≤10
【算法分析】
● 折半插入排序，也叫二分插入排序。它是对直接插入排序的优化，在查找插入位置时使用二分查找，从而减少比较次数。
【算法代码：折半插入排序】
#include <bits/stdc++.h> using namespace std; const int N=15; int a[N]; int n; int main() { cin>>n; for(int i=1; i<=n; i++) cin>>a[i]; for(int i=1; i<=n; i++) { int t=a[i]; int le=0,ri=i-1,mid; while(le<=ri) { mid=(le+ri)/2; if(a[mid]>t) ri=mid-1; else le=mid+1; } for(int j=i-1; j>=ri+1; j--) a[j+1]=a[j]; a[ri+1]=t; } for(int i=1; i<=n; i++) cout<<a[i]<<" "; return 0; } /* in: 5 6 9 2 7 1 out: 1 2 6 7 9 */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/161347829
https://blog.csdn.net/hnjzsyjyj/article/details/161332702
https://blog.csdn.net/hnjzsyjyj/article/details/161346075
https://blog.csdn.net/hnjzsyjyj/article/details/161588834
