第一种实现方式：(本人一开始对cin的使用不是很熟悉，看了一些人得博客详解后才有了第一种方式的实现，自己都被惊讶到了so easy:题目在下面)
//
// main.cpp
// BinaryInsertSort
//
// Created by Jason on 16/9/28.
// Copyright © 2016年 Jason. All rights reserved.
//
#include <iostream>
using namespace std;
//折半插入排序-算法
void BinaryInsertSort(int R[],int n )
{
int i,j,mid,low,high,temp;
for(i=2; i<=n; ++i)
{
R[0] = R[i];
low = 1;
high = i-1;
while(low <= high)
{
mid = (low + high) / 2;
if(temp > R[mid])
{
low = mid + 1;
}else{
high = mid - 1;
}
}
for(j=i-1; j>=high+1; --j)
{
R[j+1] = R[j];
}
R[high+1] = R[0];
}
}
int main(int argc, const char * argv[]) {
int n;
int i = 0;
cin>>n;
if(n<=1000&&n>=1)
{
int R[n];
int b;
while(i<n&&cin>>b)
{
R[i] = b;
i++;
}
BinaryInsertSort(R,n);
for(int j=0; j<n; ++j)
{
cout << R[j] <<" ";
}
cout << endl;
}
return 0;
}
第二种实现方式
// main.cpp
// ACM_1775
// Created by Jason on 16/9/27.
// Copyright © 2016年 Jason. All rights reserved.
/**
ACM题目：
地址：http://arena.acmclub.com/problem.php?id=1775
输入
输入的第一行包含1个正整数n，表示共有n个整数需要参与排序。其中n不超过1000。
第二行包含n个用空格隔开的正整数，表示n个需要排序的整数。
输出
只有1行，包含n个整数，表示从小到大排序完毕的所有整数。
请在每个整数后输出一个空格，并请注意行尾输出换行。
样例输入
10
2 8 4 6 1 10 7 3 5 9
样例输出
1 2 3 4 5 6 7 8 9 10
提示
在本题中，需要按照题目描述中的算法完成折半插入排序的算法。与直接插入排序算法不同，折半插入排序算法在查找插入位置时采用了折半查找的方案，减少了关键字之间的比较次数，但是记录的移动次数并没有发生改变，因此折半插入排序的时间复杂度依旧为O(n2)，同样不是一种非常高效的排序方法。
**/
#include <iostream>
#include <sstream>//包含串流输入输入类
#include <string>
using namespace std;
//折半插入算法
void BinaryInsertSort(int R[],int n )
{
int i,j,mid,low,high,temp;
for(i=1; i<n; ++i)
{
temp = R[i];
low = 0;
high = i;
while(low <= high)
{
mid = (low + high) / 2;
if(temp > R[mid])
{
low = mid + 1;
}else{
high = mid - 1;
}
}
for(j=i-1; j>=low; --j)
{
R[j+1] = R[j];
}
R[low] = temp;
}
}
int main(int argc, const char * argv[]) {
int k = 0;
int n;
cin>>n;
int R[n];
/**
问题：下面的getline(cin,m)没法键盘输入，直接跳过
解决：由于在写getline()函数之前，使用过了回车
（不论你输入的是字符，数字或是回车，空格符，getline()函数都接收）
而cin>>这种输入方式却是忽略回车的，如果你在getline()之前cin的一个数，回车被cin忽略了，却被getline函数接收了，感觉就是这条语句被跳过了
所以解决的办法是在getline函数之前再使用getline一次，将输入流里的回车符接收掉，后面就能正常输入了
**/
if (n<=1000&&n>=1) {
string m;
/**
getline 函数不是c库函数而是C++库函数，
getline函数是一个比较常见的函数。根据它的名字我们就可以知道这个函数是来完成读入一行数据的
C++中定义了一个在std名字空间的全局函数，因为这个getline函数的参数使用了string字符串，所以声明在了<string>头文件中了。
**/
getline(cin, m);
getline(cin, m);
/**
C++引入了ostringstream、istringstream、stringstream这三个类，要使用他们创建对象就必须包含<sstream>这个头文件。
istringstream类用于执行C++风格的串流的输入操作。
ostringstream类用于执行C风格的串流的输出操作。
strstream类同时可以支持C风格的串流的输入输出操作。
istringstream的构造函数原形如下：
istringstream::istringstream(string str);
它的作用是从string对象str中读取字符。
getline()的原型是istream& getline ( istream &is , string &str , char delim );
其中 istream &is 表示一个输入流，譬如cin；string&str表示把从输入流读入的字符串存放在这个字符串中（可以自己随便命名，str什么的都可以）；
char delim表示遇到这个字符停止读入，在不设置的情况下系统默认该字符为'
'，也就是回车换行符（遇到回车停止读入）
**/
istringstream is(m);
int number;
while(is>>number)
{
R[k] = number;
k++;
}
BinaryInsertSort(R,n);
for(int j=0; j<n; ++j)
{
cout << R[j] <<" ";
}
cout << endl;
}
}