經典排序（四）——二分插入排序

于插入排序，如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的次數，我們稱為二分插入排序。

算法概述

采用折半查找，來找到待排序元素的插入位置，然後移動元素，将待排序的元素插入序列中。移動必須從最後一個記錄開始，向後移動一位，再移動倒數第2位，直到要插入的位置的記錄移後一位。

C語言實作

#include<stdio.h>

void BinInsertSort(int A[],int n)
{
	int i,j;

	for(i = 1;i < n;i++)
	{
		int get = A[i];//取得的待排新元素
		int left = 0;
		int right = i-1;//已排序的有序區間
		
		while(left <= right)//有序區間内進行折半查找，找到插入位置
		{
			int mid = (right+left)/2;
			if(A[mid] > get)
				right = mid - 1;
			else
				left = mid + 1;
		}
		for(j = i - 1;j >= left;j--)//移出位置
		{
			A[j+1] = A[j];
		}
		A[left] = get;//将待排元素插入
	}
}

int main()
{
	int i;
	int A[] = {5,3,56,23,12,67,25};
	int n = sizeof(A)/sizeof(A[0]);

	BinInsertSort(A,n);

	for(i = 0;i < n;i++)
	{
		printf("%-6d",A[i]);
	}
	printf("\n");
	return;
}
           

運作結果

當數組元素較多時，二分插入排序的比較次數比直接插入排序的最差情況好得多，但比直接插入排序的最好情況要差，是以當元素初始序列已經接近升序時，直接插入排序比二分插入排序比較次數少。二分插入排序元素移動次數與直接插入排序相同，依賴于元素的初始序列。

也就是說，相比于直接插入排序，二分插入排序隻是減少了元素比較的次數，并未減少元素移動的次數，本質上講，并未提高算法的性能。