首页 > 代码库 > 折半插入排序
折半插入排序
// 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;
}
折半插入排序