学步园

排序算法之插入排序

1插入排序的思想

假设在一个有序序列中e[0]~e[i-1]这i个元素已经排好序，则当要将第i+1个元素e'插入该序列时，只需将第i+1个元素与从e[0]开始到e[i-1]元素进行比较，当发现第j个元素e[j]在序列中应在e'前，且e[j+1]应在e'后时，将该有序列中从e[j+1]到e[i-1]的元素向后移动一个单元。最后将e'插入原来e[j+1]所在的位置。重复前面的动作直到将所有的元素插入该有序列中为止。

2插入排序的实现思想

在一个无序序列中，一个只有一个元素e[0]的序列是有序的。此时按照上面的算法思想将e[1]插入该有序序列中。如此往复，直到将原无序序列中所有的元素都插入该有序序列中为止。< /p>

3插入排序的具体实现

/**//*

C代码的插入排序

有序序列为整数的由小到大序列

*/
void insertSort(int e[],int n)...{
    int i,j;
    int temp;
    for(i=1;i<n;i++)...{
        temp=e[i];
        for(j=i-1;j>=0;j--)...{
            if(e[j]<temp)...{
                break;
            }
            e[j+1]=e[j];
        }
        e[j+1]=temp;
    }
}

#!/usr/bin/perl
#perl代码的插入排序
#有序序列为整数的由小到大序列

sub insertSort{
    my(@e)=@_;
    my($i,$j)=(0,0);
    my($temp)=0;
    for($i=1;$i<@e;$i++){
        $temp=$e[$i];
        for($j=$i-1;$j>=0;$j--){
            if($e[$j]<$temp){
                last
            }
            @e[$j+1]=@e[$j];
        }
        @e[$j+1]=$temp;
    }
    return(@e);
}

#!/usr/local/bin/python
#Python代码的插入排序
#有序序列为整数的由小到大序列

def insertSort(e):
    i=j=0
    n=len(e)
    for i in range(1,n):
        temp=e[i]
        for j in range(0,i+1):
            j=(i-1)-j
            if(e[j]<temp):
                break
            e[j+1]=e[j]
        e[j+1]=temp
    return(e)

4算法分析

插入排序最坏的情况是初始序列与要求的序列逆序。此时，每次插入都需要将插入项后的元素向后移动。
插入排序的复杂度为n(n-1)/2=O(n^2) 且 是稳定排序
插入排序的性能和原始序列的情况密切相关。当原始序列非常接近排序后的序列时，插入排序的效率是很高的。当原始序列与排序后的序列互为逆序时，插入排序的效率最差。

文外音:

很早以前就想写这样的文章了，所以今天有些时间就写了。感觉我的Blog很久都没更新了，突然发现自己貌似有些变懒惰了。我觉得很多人把算法理解的过于狭隘了，其实算法本身并没有意义。我之后还会用有类似的文章出来，如果各位有兴趣的话可以关注一下。如果各位有什么问题，可以到http://nirvana.cublog.cn上提出。

NERVE软件开发组(NDT)
NERVEDevelopment Team
北斗星君(黄庠魁)