数据结构--排序之插入排序

/*
     * 插入排序O(N2)的运行时间
     * 思想是：若数组长度为N 那么把数组序号从1到N-1的值依次往前进行比较 这里需要一个for循环
     * 注意每个数在比较的时候它前面的数据都是已经排好序号的（因为从序号为1时就开始排序了）
     * 注意我们这里用类似堆中下浮和上浮的交换方法  把需要交换的数据拿出来 和前面的数据依次进行比较 如果拿出来的数据小了  这个当前位置直接被覆盖就可 这里又有一个嵌套的for循环
     */
    public static<T extends Comparable<? super T>> void insertSort(T[] t)
    {
        //因为最后插入值时候 需要在内部for循环的外面  所以j要在外部定义
        int j;
        for(int p=1;p<t.length;p++)
        {
            T temp=t[p];
            for(j=p;j>0 && temp.compareTo(t[j-1])<0;j--)
                t[j]=t[j-1];
            t[j]=temp;//检测到j--之后j==0 或者t[j]>=t[j-1] 直接给t[j]位置赋值 完成插入
        }
    }

public static void main(String[] args)
    {
        Integer[] t={45,3,23,1,1,13,33};
        //insertSort(t);
        shellSort(t);
        for(Integer tt:t)
            System.out.print(tt+"   ");
    }

数据结构--排序之插入排序

原文：http://blog.csdn.net/u012411414/article/details/44590317