直接插入排序

插入排序是对少量元素进行排序的有效算法，各个数字是原地排序，插入排序是稳定的。
算法思想：将一个元素通过和当前已经排序好的数组的最大元素进行比较，并在待插入数组较小的情况下通过设置哨兵，整体移动，插入正确位置，从此得到一个新的排序好的数组的过程。

算法导论中的伪代码：

△INSERT-SORT(A)
for j ← 2 to length[A]
do key ← A[j]
△Insert A[j] into the sorted sequence A[1..j-1].
i ← j-1
while i>0 and A[i]>key
do A[i+1] ← A[i]
i ← i-1
A[i+1] ← key

C++实现

/**********直接插入排序*************/
void InsertSort(ElemType a[],int n)
{
	int i,j;
	ElemType key;
	for(i = 1; i < n; i++)
	{
		if(a[i] < a[i-1])
		{
			key = a[i];
			for(j = i-1; key < a[j]; j--)
				a[j+1] = a[j];
			a[j+1] = key;
		}
	}
}

Python实现

#---------------#
#--insert sort--#
#---------------#
def insertion_sort(arr):
		arrlen = len(arr)
		for i in range(1,arrlen):
				insert(arr,i)

def insert(arr,i):
		key = arr[i]
		j = i
		while j>0 and key < arr[j-1]:
				arr[j] = arr[j-1]
				j-=1
		arr[j] = key

直接插入排序时间复杂度分析：
最好的情况下，本身有序，即每次需要插入的元素都是最大的，这样只需要比较n-1次，没有移动记录，所以时间复杂度为O(n)。最坏的情况下，即待排序的是逆序的，此时需要比较的次数为：2+3+4+…+n=(n+2)(n-1)/2，而移动的次数为：(n+4)(n-1)/2。总得时间复杂度为O(n^2)。
平均比较和移动次数n^2/4次。
因此，我们得出直接插入排序算法的时间复杂度为O(n^2)。

直接插入排序空间复杂度分析：
原地排序，所以空间复杂度O(1)。

折半插入排序

直接插入排序的改进算法，减少了比较次数，移动次数未改变，同为稳定排序，时间复杂度仍为O(n^2)。
算法思想：在寻找插入点时采用二分查找。

C++实现

/**********折半插入排序*************/
void BinaryInsertSort(ElemType a[],int n)
{
	for(int i = 1;i < n;i++)
	{
		int low = 0;
		int high = i-1;
		int middle;
		ElemType key = a[i];
		while(low <= high)
		{
			middle = (low+high)/2;
			if(key < a[middle])
				high = middle-1;
			else
				low = middle+1;
		}
		for(int j = i;j > middle;j--)
			a[j] = a[j-1];
		a[low] = key;
	}
}

python实现

#----------------------#
#--binary insert sort--#
#----------------------#
def bin_insertion_sort(arr):
		arrlen = len(arr)
		for i in range(1,arrlen):
				bin_insert(arr,0,i-1,i)				

def bin_insert(arr,low,high,i):
		middle = (low+high)/2
		if low <= high:
				if arr[middle] < arr[i]:
						bin_insert(arr,middle+1,high,i)
				else:
						bin_insert(arr,low,high-1,i)
		else:
				key = arr[i]

				for j in reversed(range(low,i)):
						arr[j+1] = arr[j]
				arr[low] = key

 

#Testing
def main():
		arr = [4,10,9,8,7,6,5,4,3,2]
		#print "Insert Sort Result:"
		#insertion_sort(arr)
		print "Binary Insert Sort Result:"
		bin_insertion_sort(arr)
		print arr
if __name__ == '__main__':
    main();