// main.cpp // BinaryInsertSort // Created by Jason on 16/9/22. // Copyright © 2016年 Jason. All rights reserved. #include <iostream> using namespace std; #define ARR_SIZE(array,len)(len = (sizeof(arr)/sizeof(arr[0]))); //折半查找代码如下: /** 折半查找原理: 百度百科:http://baike.baidu.com/link?url=uxMHSYOcdy9RUc6ooMe_K4rbeg6zTIcaoQ3Jkcuve_NP89P-atvjG16ZoCiAw40xJgH9TMNKHflHwl7BLn1Z2NB-Na-zbIVtczksUUC65xZjOuIEIUagDjhrkEoet2vInr-f3cjI92XwTmBzKa0mC23T7sFqBPTFgFlkYlt-eyKY6GjN7Upr6NitRmXDRF2B 折半插入排序原理 百度百科: http://baike.baidu.com/link?url=7hiQinaLychnjNHoBBUEA3Xyivln5hPiDrv8nVPYJSNlKIYbpk4gx-pEmzBKNlPyyzEZvWwNitny81xpj1b_Nq **/ void BinaryInsertSort(int array[],int n)//传递数组和数组元素个数 { int i,j,mid,low,high,temp; for(i = 1;i < n; ++i)//我看了一些其他人写得折半插入算法是从下标1开始的,i = 2;i <=n,并将array[i]存储到array[0] { temp = array[i];//把第i+1个元素赋值给temp(数组从下标0开始) low = 0;//初始化low,array[low]代表数组中第1个元素 high = i;//初始化high,array[high]代表已插入的最后一个元素 while(low <= high) //不断的折半1/2 1/4 .... { mid = (low + high) / 2;//计算中间位置 if (temp > array[mid]) { //插入值大于中间值 low = mid + 1; }else{ //插入值小于中间值 high = mid - 1; } } for(j=i-1;j >= low; --j) { //将需要移动的数组向后移 array[j+1] = array[j]; } //将值插入到指定位置 array[low] = temp; } } int main(int argc, const char * argv[]) { int arr[] = {6,12,8,1,15,11,3,7,4,13}; int len; ARR_SIZE(arr,len); BinaryInsertSort(arr,len); for(int i=0;i<len;i++) { cout << arr[i] << " "; } cout << endl; }