插入排序算法

admin

1、算法描述

1，从第一个元素开始，该元素可以认为已经被排序；
2，取出下一个元素，在已经排序的元素序列中从后向前扫描。
3，如果该元素(已排序)大于新元素，将该元素移到下一位置。
4，重复步骤3 ，直到找到已排序的元素小于或者等于新元素的位置。
5，将新元素插入到该位置中。
6，重复步骤2。

2、java代码
public class InsertSort
{
    public void insertSort(int[] a)
    {
        for(int j=1;j<a.length;j++)
        {
            int temp=a[j],i=j;
            while(i>=1&&a[i-1]>temp)
            {
                a[i]=a[i-1];
                i--;
            }
            a[i]=temp;
        }
    }

    public static void main(String[] args)
    {
        int[] a=new int[]{3,5,6,4,1,2};
        InsertSort sort=new InsertSort();
        sort.insertSort(a);
    }
}
3、时间复杂度分析
函数内部包含一个for循环，循环次数跟数组的长度n一样，循环内部的 int temp=a[j],i=j;和 a[i]=temp;为基础语句，执行时间为常量a，执行次数为n。主要就看for循环内部的while部分，while内部的语句a[i]=a[i-1];和i--;为基础语句，执行时间为常量a，就看执行次数了。while的执行次数由j和数组中元素的排列顺序控制，分三种情况：

1）、最好情况

数组中元素按从小到大排列，则while内部语句不会执行，次数时间复杂度为O(n).

2）、最坏情况

数组中元素按从大到小排列，则while执行次数为：1+2+3+...+(n-1)=\(\frac{(n-1)n}{2}\)=O(n^2)

3）、随机顺序

这个该如何

wang1026613528

会的真多，望尘莫及