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

浏览数：21 / 时间：2015年06月08日

/*
     * 插入排序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+"   ");
    }

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

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