本文共 1052 字，大约阅读时间需要 3 分钟。

数据结构排序算法之插入排序<二>

2.折半插入排序

基本思想：

折半插入算法是对直接插入排序算法的改进，排序原理同。

例子：int[] arr={5,2,6,0,9};经行折半插入排序

Java实现：

package priv.qcy.sort.insert;public class BinaryInsertSort {	public static void binaryInsertSort(int[] a) {		int n = a.length;		int i, j;		for (i = 1; i < n; i++) {			int temp = a[i];			int low = 0;			int high = i - 1;			while (low <= high) {				int mid = (low + high) / 2;				if (a[mid] > temp) {					high = mid - 1;				} else {					low = mid + 1;				}			}			for (j = i - 1; j >= low; j--) {				a[j + 1] = a[j];			}			a[low] = temp;		}	}	public static void main(String[] args) {		int[] a = { 20, 40, 30, 10, 60, 50 };		System.out.print("排序前：");		for (int i = 0; i < a.length; i++) {			System.out.print(a[i] + "  ");		}		System.out.println();		binaryInsertSort(a);		System.out.print("排序后：");		for (int i = 0; i < a.length; i++) {			System.out.print(a[i] + "  ");		}	}}

时间复杂度：可以看出，折半插入排序减少了比较元素的次数，约为O(nlogn)，比较的次数取决于表的元素个数n。因此，折半插入排序的时间复杂度仍然为O(n²)，但它的效果还是比直接插入排序要好。

空间复杂度：排序只需要一个位置来暂存元素，因此空间复杂度为O（1）。

特点：

• 只适用于顺序结构
• 适合初始记录无序，n较大的情况
• 稳定，相对于直接插入排序元素减少了比较次数

转载地址：http://binwi.baihongyu.com/