1372 - 算法10-2：折半插入排序
折半插入排序同样是一种非常简单的排序方法，它的基本操作是在一个已经排好序的有序表中进行查找和插入。不难发现这个查找的过程可以十分自然的修改成折半查找的方式进行实现。
折半插入排序的算法可以描述如下：
<span style="font-family:宋体;">在本题中，读入一串整数，将其使用以上描述的折半插入排序的方法从小到大排序，并输出。</span>
<span></span>
Input
输入的第一行包含1个正整数n，表示共有n个整数需要参与排序。其中n不超过1000。
第二行包含n个用空格隔开的正整数，表示n个需要排序的整数。
Output
只有1行，包含n个整数，表示从小到大排序完毕的所有整数。
请在每个整数后输出一个空格，并请注意行尾输出换行。
Examples
Input
10 2 8 4 6 1 10 7 3 5 9
Output
1 2 3 4 5 6 7 8 9 10
Hint
在本题中，需要按照题目描述中的算法完成折半插入排序的算法。与直接插入排序算法不同，折半插入排序算法在查找插入位置时采用了折半查找的方案，减少了关键字之间的比较次数，但是记录的移动次数并没有发生改变，因此折半插入排序的时间复杂度依旧为O(n2)，同样不是一种非常高效的排序方法。
Solution C
#include <stdio.h> #include <string.h> #include <stdlib.h> int s[10000],n,i; int cmp(const void *a,const void *b) { return(*(int *)a-*(int *)b);//ÉýÐò£»b-a½µÐò } int main() { scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&s[i]); qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%d ",s[i]); printf("\n"); return 0; }
Solution C++
#include <cstdio> #include <cstdlib> #include <stack> #include <algorithm> using namespace std; const int MAXN = 1000; int val[MAXN]; int n; void InsertSort() { int current, l, r, mid; for (int i = 1;i < n;i++) { current = val[i]; l = 0; r = i; while (l < r) { mid = (l + r) / 2; if (val[mid] < current) l = mid + 1; else r = mid; } for (int j = i;j > l;j--) val[j] = val[j - 1]; val[l] = current; } } int main() { scanf("%d", &n); for (int i = 0;i < n;i++) { scanf("%d", &val[i]); } InsertSort(); for (int i = 0;i < n;i++) { printf("%d ", val[i]); } puts(""); return 0; }
Hint
在本题中，需要按照题目描述中的算法完成折半插入排序的算法。与直接插入排序算法不同，折半插入排序算法在查找插入位置时采用了折半查找的方案，减少了关键字之间的比较次数，但是记录的移动次数并没有发生改变，因此折半插入排序的时间复杂度依旧为O(n2)，同样不是一种非常高效的排序方法。