直接插入排序与折半插入排序

直接插入排序

原理：每次将排序中的元素，插入到前面已经排好序的有序序列中去，直到排序完成。

步骤：

• 第一步，a[0]为有序区，待排序区为a[1..n-1]。令i=1。

• 第二步，将a[1]与a[0]中元素比较，将小的元素放在第一个位置。

• 第三步，以此类推，直到待排序中全部元素插入完成为止。

例子：int[] arr={5,2,6,0,9};经行直接插入排序

图解：

过程：

• 初始状态：设5为有序，其中i为1，即：5 2 0 6 9

• 第一趟排序：第i个元素2比5小，则插入到5前面，然后i自增，即 ： 2 5 0 6 9

• 第二趟排序：第i个元素0比2，5小，则插入到2前面，然后i自增，即：0 2 5 6 9

• 第三趟排序：第i个元素6比5大，则插入到5后面，然后i自增，即：0 2 5 6 9

• 第四趟排序：第i个元素9比6大，则插入到6后面，然后i自增，即：0 2 5 6 9

• 最终的答案为：0 2 5 6 9

时间复杂度：

1.在最好情况下，严格递增的数组，比较次数C和移动次数M为：

C = n - 1
M = 0
时间复杂度为O(n)。

2.在最坏情况下，严格递减的数组，比较次数C和移动次数M为：

C = n(n-1)/2
M = n(n-1)/2
时间复杂度为O(n²)。

综上，时间复杂度为：O_(n²) 。

优缺点：　　

• 优点 : 稳定，相对于冒泡排序与选择排序更快；
• 缺点 : 比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量大的时候；

代码：

public class InsertSort {
    public static void main(String[] args){
        int arr[] = { 5 , 2 , 6 , 0 , 9};   
        System.out.println("排序前的数据：");
        for (int i = 0; i < arr.length; i++) {            
            System.out.print(arr[i] + " ");
        }
        //直接插入排序
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            //待排序中的元素比已排序的元素小，则交换位置
            while (j > 0 && arr[j] < arr[j - 1]) {
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                j--;
            }
        }     
        System.out.println();
        System.out.println("排序后的数据：");
        for (int i = 0; i < arr.length; i++) {            
            System.out.print(arr[i] + " ");
        }                
    }        
}

结果：

---

折半插入排序

原理：折半插入算法是对直接插入排序算法的改进，排序原理同直接插入算法。

区别：在插入到已排序的数据时采用来折半查找（二分查找），取已经排好序的数组的中间元素，与插入的数据进行比较，如果比插入的数据大，那么插入的数据肯定属于前半部分，否则属于后半部分，依次不断缩小范围，确定要插入的位置。

例子：int[] arr={5,2,6,0,9};经行折半插入排序

图解：

代码：

public class BinaryInsertSort {
    public static void main(String[] args){
        int arr[] = { 5 , 2 , 6 , 0 , 9 };   
        //打印排序前的数据
        System.out.println("排序前的数据：");
        for (int i = 0; i < arr.length; i++) {            
            System.out.print(arr[i] + " ");
        }
        //直接插入排序
        binaryInsertSort(arr);
        //打印排序后的数据
        System.out.println();
        System.out.println("排序后的数据：");
        for (int i = 0; i < arr.length; i++) {            
            System.out.print(arr[i] + " ");
        }                
    }    
    private static void binaryInsertSort(int arr[]){

        int low,high,m,temp,i,j;
        for(i = 1;i<arr.length;i++){
            //折半查找应该插入的位置
            low = 0;
            high = i-1;
            while(low <= high){
                m = (low+high)/2;
                if(arr[m] > arr[i])
                    high = m - 1;
                else
                    low = m + 1;
            }
            //统一移动元素，然后将这个元素插入到正确的位置
            temp = arr[i];
            for(j=i;j>high+1;j--){
                arr[j] = arr[j-1];
            }
            arr[high+1] = temp;
        }        
    }
}

过程：

• 初始状态：设5为有序，其中i为1，即：5 2 0 6 9

• 第一趟排序：low为0，high为0，则中间值下标为0（（low+high）/2，下文都是如此计算），即5大于2，则插入到5前面，然后i自增。即：2 5 6 0 9

• 第二趟排序：low为0，high为1，则中间值下标为0，即2小于6，然后low等于中间值得下标加1，继续找中间值为5小于6，则插入到5后面，然后i自增。即：2 5 6 0 9

• 第三趟排序：low为0，high为2，则中间值下标为1，即5大于0，然后high等于中间值得下标减1，继续找中间值为2大于0，则插入到2前面，然后i自增。即：0 2 5 6 9

• 第四趟排序：low为0，high为3，则中间值下标为1，即2小于9，然后low等于中间值得下标加上1，继续找中间值为5小于9，然后low等于中间值得下标加上1，继续找中间值为6小于9，则插入到6后面，然后i自增，即：0 2 5 6 9

• 最终的答案为：0 2 5 6 9

结果：

结论： 先折半查找元素的应该插入的位置，然后统一移动应该移动的元素，再将这个元素插入到正确的位置。

优缺点：　　

• 优点 : 稳定，相对于直接插入排序元素减少了比较次数；
• 缺点 : 相对于直接插入排序元素的移动次数不变；

时间复杂度：可以看出，折半插入排序减少了比较元素的次数，约为O(nlogn)，比较的次数取决于表的元素个数n。因此，折半插入排序的时间复杂度仍然为O(n²)，但它的效果还是比直接插入排序要好。

空间复杂度：排序只需要一个位置来暂存元素，因此空间复杂度为O（1）。