美文网首页
直接插入排序

直接插入排序

作者: 刀拉 | 来源:发表于2020-03-16 17:36 被阅读0次

    对于一个有n个元素的待排序列,将这个序列分成有序表和无序表,刚开始时,有序表只有一个元素,无序表有n-1个元素,排序过程就是将无序表的第一个元素插入到有序表的合适位置,依次循环n-1次。

    public static void insertsort(int[] arr) {
        int i, j, k;
        for(i=1;i<arr.length;i++) {
            for(j=i-1;j>=0;j--) {
                if(arr[j]<arr[i])
                    break;
            }   
            if(j!=i-1) {
                int temp = arr[i];
                for(k = i-1;k>j;k--) {
                    arr[k+1] = arr[k];
                }
                arr[j+1]=temp;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {62,23,51,46,85,42,15};
        insertsort(arr);
        System.out.println(Arrays.toString(arr));
    }
    

    最好情况:待排序列已按关键字有序,只需1次比较,0次移动。
    总比较次数:n-1次
    总移动次数:0次
    最坏情况:待排序列按关键字逆序,即每趟都需要叫关键字插入到有序序列的第一位
    总比较次数:(n+2)(n+1)/2
    总移动次数:(n+4)(n-1)/2

    平均情况:O(n2)

    相关文章

      网友评论

          本文标题:直接插入排序

          本文链接:https://www.haomeiwen.com/subject/sgtgaqtx.html