排序算法二:插入排序及其优化

一. 算法描述

    插入排序：插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中......第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。

二.来自算法导论的算法伪代码：

insert_sort(A):
    for j <—— 1 to length[A]-1
        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

三.简单算法实现

#include <stdio.h>
 
void insert_sort(int *arr,int n)
{
    assert(n>0 || arr != NULL);
    int i,j,key;
    for(j=1;j<n;++j){
        key=arr[j];
        i=j-1;
        //把比key大的数依次往后移动一位
        while(i>=0 && arr[i]>key){
            arr[i+1]=arr[i];
            i--;
        }
        arr[i+1]=key;
    }
}

//简单的测试一下
int main()
{
    int arr[8]={32,3,4,5,6,7,9,106};
    insert_sort(arr,8);
    for (int i=0;i<8;i++)
    {
        printf("%d ",arr[i]);
    }
    return 0;
}

四. 算法优化

插入排序中，总是先寻找插入位置，然后在实行挪动和插入过程；寻找插入位置采用顺序查找的方式（从前向后或者从后向前），既然需要插入的数组已经是有序的，那么可以采用二分查找方法来寻找插入位置，提高算法效率，但算法的时间复杂度仍为O(n2)。

#include <stdio.h>

//Binary Search
int BinarySearch(int* num,int length,int data)
{
	int left=0;
	int right=length-1;
	int index;
	while(left<=right)
	{
		index=(left+right)/2;
		if(num[index]>data)
		{
			right=index-1;
		}
		else
		{
			left=index+1;
		}
	}
	//注意如果二分查找的下标index所对应的数小于或等于待插入的数，则插入位置应位于其后。
	if(num[index]<=data)
	{
		index++;
	}
	return index;
}

//Binary Insert Sort
void BinaryInsertSort(int* num,int length)
{
	for(int i=1;i<length;++i)
	{
		int index=BinarySearch(num,i,num[i]);
		if(i!=index)
		{
			int j=i;
			int temp=num[i];
			while(j>index)
			{
				num[j]=num[j-1];
				--j;
			}
			num[j]=temp;
		}
	}
}
int main()
{
	int num[]={3,2,5,1,4,9,6};
	BinaryInsertSort(num,7);
	for(int i=0;i<7;i++)
	{
		printf("%d ",num[i]);
	}
	printf("\n");
	return 0;
}