首页 > 代码库 > 折半插入排序
折半插入排序
之间介绍插入排序时漏掉一种插入方式,那就是折半插入。
这种方式是采用二分查找法去查找插入点,可以减少元素比较次数,但是并不能减少移动次数,复杂度跟直接插入一样,都为O(n^2).
直接上代码:
//二分插入排序 void binary_insert_sort(int arr[],int len) { if(arr == NULL || len <= 1) { return; } int i,j; for(i = 1; i < len; i++) { int low = 0,high = i-1; int target = arr[i]; while(low <= high) { int middle = low + ((high - low)>>1); if(arr[middle] > target) { high = middle-1; }else { low = middle+1; } } //low的位置正好是插入点 //i与low之间的元素后移一位(不包括i) for(j = i; j>low; j--) { arr[j] = arr[j-1]; } //将target插入到正确位置 arr[low] = target; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。