折半插入排序（Binary Insertion Sort）是一种插入排序算法，通过不断地将数据元素插入到合适的位置进行排序，在寻找插入点时采用了折半查找。
一、算法基本思想
（1）基本思想
折半插入排序的基本思想是：顺序地把待排序的序列中的各个元素按其关键字的大小，通过折半查找插入到已排序的序列的适当位置。
（2）运行过程
直接插入排序的运作如下：
1、将待排序序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2、从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置，在查找元素的适当位置时，采用了折半查找方法。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
二、算法实现（核心代码）
C++实现：
void binary_insertion_sort(int arr[], int len) { int i, j, temp, m, low, high; for (i = 1; i < len; i++) { temp = arr[i]; low = 0; high = i-1; while (low <= high) { m = (low +high) / 2; if(arr[m] > temp) high = m-1; else low = m+1; } } for (j = i-1; j>=high+1; j--) arr[j+1] = arr[j]; arr[j+1] = temp; }
Java实现：
public void binary_insertion_sort(int arr[]) { int i, j, temp, m, low, high, len = arr.length; for (i = 1; i < len; i++) { temp = arr[i]; low = 0; high = i-1; while (low <= high) { m = (low +high) / 2; if(arr[m] > temp) high = m-1; else low = m+1; } } for (j = i-1; j>=high+1; j--) arr[j+1] = arr[j]; arr[j+1] = temp; }
三、性能（算法时间、空间复杂度、稳定性）分析
折半查找只是减少了比较次数，但是元素的移动次数不变。折半插入排序平均时间复杂度为O(n^2)；空间复杂度为O(1)；是稳定的排序算法。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/230410.html原文链接：https://javaforall.net
