插入排序--直接插入排序

2018-10-28 本文已影响0人 iarchitect

1 基本思想

将一个记录插入到已排好序的序列中，从而得到一个新的有序序列（将序列的第一个数据看成是一个有序的子序列，然后从第二个记录逐个向该有序的子序列进行有序的插入，直至整个序列有序）

重点：使用哨兵，用于临时存储和判断数组边界。

2 排序流程图

image.png

3算法实现 java

import java.util.Arrays;

public class Sort {

    public static void main(String[] args) {

        int arr[] = {2,1,5,3,6,4,9,8,7};

        int temp;

        for (int i=1;i<arr.length;i++){

            //待排元素小于有序序列的最后一个元素时，向前插入
            if (arr[i]<arr[i-1]){
                temp = arr[i];
                for (int j=i;j>=0;j--){
                    if (j>0 && arr[j-1]>temp) {
                        arr[j]=arr[j-1];
                    }else {
                        arr[j]=temp;
                        break;
                    }
                }
            }
        }

        System.out.println(Arrays.toString(arr));

    }


}

4 运行结果

image.png

5 算法分析

1，当初始序列为正序时，只需要外循环n-1次，每次进行一次比较，无需移动元素。此时比较次数（ $C _{min}$ ）和移动次数（ $M_{min}$ ）达到最小值。
$C _{min}$ =n-1
$M_{min}$ =0
此时时间复杂度为 $O(n)$ 。
2，当初始序列为反序时，需要外循环n-1次，每次排序中待插入的元素都要和[0,i-1]中的i个元素进行比较且要将这i个元素后移i次，加上tmp=arr[i]与arr[j]=temp的两次移动，每趟移动次数为i+2,此时比较次数和移动次数达到最大值。
$C_{max}$ = 1+2+...+(n-1) = n(n-1)/2= $O(n^2)$
$M_{max}$ = （1+2）+ （2+2）+.....+（n-1+2）=（n-1）(n+4)/2= $O(n^2)$
此时时间复杂度 $O(n)$
3，在直接插入排序中只使用了i,j,tmp这三个辅助元素，与问题规模无关，空间复杂度为 $O(1)$ 。
4，相同元素的相对位置不变，如果两个元素相同，插入元素放在相同元素后面。是一种稳定排序