插入排序算法

插入排序是简单排序的一种，也是基于“减治法”思想的一种算法，减治法有3种变形：

• 减去一个常量；
• 减去一个常量因子；
• 减去的规模是可变的。

插入排序算法的时间复杂度和冒泡、选择排序算法一样也是o(n²)，常见的基于插入排序算法思想的排序算法有：

• 直接插入排序算法；
• 折半插入排序算法；
• 希尔排序算法。（查看）

插入的方法一共有三种：

• 我们可以从左向右扫描序列，找到合适的位置插入；
• 我们可以从右向左扫描序列，找到合适的位置插入；
• 对于有序序列我们可以使用折半查找到合适的位置插入。

对于未知是否有序的数组，我们一般采用第二种方法从后往前扫描，它可以在比较的过程中往后移动腾空位置，比第一种要少做一次循环，效率比同种情况下的从前往后扫描更高，这一点可以去验证一下。

一、直接插入排序算法：

1、描述：假定在有序数组A[0...n-2]后面插入一个元素An-1，也就是把A[n-1]位置的移动到它合适的位置去，可以从后往前扫描，直到遇到第一个小于等于它的元素，然后把它插入到该元素的后面。

2、C语言代码实现

#include <stdio.h>

void directlyinsertSort(int a[],int n);

int main()
{
    int a[] = {6,3,8,7,3,0,9,-3,15,4};
    int k = 0;
    directlyinsertSort(a,10);
    for(;k<10;k++)
    {
        printf("%4d",a[k]);
    }
    return 0;
}

void directlyinsertSort(int a[],int n)
{
    int temp = 0;
    int i,j;
    for(i=1;i<n;i++)
    {
        if(a[i]<a[i-1])
        {
            temp = a[i];
            j = i;
            do{
                a[j] = a[j-1];
                j--;
            }while(j>0&&a[j-1]>temp);
            a[j] = temp;
        }
    }
}

3、Java代码实现

public static void insertSort0405(int[] a){
		int temp;
		int j;
		for(int i=1;i<a.length;i++){
			if(a[i]<a[i-1]){
				temp = a[i];
				j = i;
				do{
					a[j] = a[j-1];
					j--;
				}while(j>0&&a[j-1]>temp);
				a[j] = temp;
			}
		}
	}

4、一点优化

上述代码中使用了temp变量临时存放需要插入的元素，这样在while比较语句中(j>0&&a[j-1]>temp)就需要判断两次，对于庞大的数据量，这样做消耗非常大，于是我们可以使用a[0]的位置来充当这个临时存放，改进的代码如下：

#include <stdio.h>

void optimizeDirectlyInsertSort(int a[],int n);

int main()
{
    int a[] = {0,6,3,8,7,3,0,9,-3,15,4};
    int k = 0;
    optimizeDirectlyInsertSort(a,10);
    for(k=1;k<=10;k++)
    {
        printf("%4d",a[k]);
    }
    return 0;
}

void optimizeDirectlyInsertSort(int a[],int n)
{
    int i,j;
    for(i=2;i<=n;i++)
    {
        if(a[i]<a[i-1])
        {
            a[0] = a[i];
            j = i-1;
            do{
                a[j+1] = a[j];
                j--;
            }while(a[0]<a[j]);
            a[j+1] = a[0];
        }
    }
}

二、折半插入排序算法

1、描述：折半插入排序算法的使用是有前提的，就是必须是有序数组。它是指在一个有序序列中插入一个元素形成一个心得有序序列。在有序序列中进行查找，折半思想也是最有效的方法。折半查找设置三个下标low、high和mid，设置low的值为1，high为n-1，mid的值为(low+high)/2，然后将要插入的元素与mid下标元素进行比较。若小于mid下标元素，那么high=mid-1，low值不变，若大于mid下标元素，则low=mid+1,high值不变；若等于mid那么查找成功插入之。

2、C语言代码实现

#include <stdio.h>

void halfInsertSort(int a[],int n);

int main()
{
    int a[] = {0,1,2,3,4,6,7,8,9,10,5};
    int k = 0;
    halfInsertSort(a,10);
    for(k=1;k<=10;k++)
    {
        printf("%4d",a[k]);
    }
    return 0;
}

void halfInsertSort(int a[],int n)
{
    int low,mid,high;
    int i,j,m;
    for(i=2;i<=n;i++)
    {
        a[0] = a[i];
        low = 1;
        high = i -1;
        while(low<=high)
        {
            m = (low+high)/2;
            if(a[0]<a[m])
            {
                high = m -1;
            }else low = m + 1;
        }
        for(j=i-1;j>=high;j--)
        {
            a[j+1] = a[j];
        }
        a[high+1] = a[0];
    }
}