插入排序

2020-06-21

直接插入排序 #

思想 #

将记录集合分为有序和无序两部分，每次从无序序列中取一个记录加入有序序列中，使该有序序列仍然有序。重复该步骤，直到无序序列中的记录全部插入有序序列。

代码实现 #

    public static void insertionSort(int[] a){
        for(int i=1;i<a.length;i++){
            int key=a[i];//记录当前i位置的值
            int j=i-1;
            //将大于key的值全部后移
            while(j>=0&&a[j]>key){
                a[j+1]=a[j];
                j--;
            }
            a[j+1]=key;
        }
    }

复杂度 #

时间复杂度：O(n²)

空间复杂度：O(1)

稳定的排序算法

折半插入排序 #

思想 #

在将无序序列中的元素插入有序序列时，采用折半查找确定其位置，从而减少查找的次数

代码实现 #

        for(int i=1;i<a.length;i++){
            int key=a[i];
            int low=0,high=i-1;
            //加入一个折半查找，减少查找次数
            while(low<=high){
                int mid=(low+high)/2;
                if(a[mid]>key)
                    high=mid-1;
                else if(a[mid]<key)
                    low=mid+1;
            }
            int j;
            for(j=i-1;j>=high+1;j--)
                a[j+1]=a[j];
            a[j+1]=key;
        }

复杂度 #

与直接插入排序相同