直接插入排序

代码

package com.sort;

public class InsertSort {

    public static void main(String[] args) {
        System.out.println("------------------------------");
        int[] arg = {1, -9, 5, 8, 7, 6, 2, 4, 22, 24};
        System.out.println("插入排序前：");
        PrintArg(arg);
        System.out.println("------------------------------");
        InsertSort(arg);
        System.out.println("插入排序后：");
        PrintArg(arg);
        System.out.println("------------------------------");
    }

      //插入排序
//    public static void InsertSort(int[] arg) {
//        int length = arg.length;
//        for (int i = 1; i < length; i++) {
//            for (int j = i; j > 0 && smaller(arg[j], arg[j - 1]); j--) {
//                swap(arg, j, j - 1);
//            }
//        }
//    }
    //插入排序
    public static void InsertSort(int[] arg) {
        int length = arg.length;
        for (int i = 1; i < length; i++) {

            for (int j = i; j > 0; j--) {
                if (smaller(arg[j], arg[j - 1])) {
                    swap(arg, j, j - 1);
                } else {
                    break;
                }
            }
            System.out.println("第" + i+"次排序:");
            PrintArg(arg);
        }
        System.out.println("------------------------------");
    }

    //比较大小
    public static boolean smaller(int x, int y) {
        if (x < y) {
            return true;
        } else {
            return false;
        }
    }

    //交换顺序
    public static void swap(int arg[], int i, int j) {
        int temp = arg[i];
        arg[i] = arg[j];
        arg[j] = temp;
    }

    //打印数组
    public static void PrintArg(int[] arg) {
        for (int i = 0; i < arg.length; i++) {
            if (i == arg.length - 1) {
                System.out.println(arg[i]);
            } else {
                System.out.print(arg[i] + " ");
            }
        }
    }

}

运行结果

原理

插入排序的基本思想是：每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。

算法分析

时间复杂度

从时间来看，排序的基本操作为：比较两个关键字的大小和移动记录。
对于其中的某一趟插入排序，内层的for循环次数取决于待插记录的关键字与前i个关键字之间的关系。其中，在最好情况(正序：待排序序列中记录按关键字非递减有序排列)下，比较1次，不移动；在最坏情况(逆序：待排序序列中记录按关键字非递增有序排列)下，比较i次(依次同前面i-1个记录进行比较，并和哨兵比较1次)，移动i+1次(前面的i-1个记录依次向后移动，另外开始时将待插入的记录移动到监视哨中，最后找到插入位置，又从监视哨中移过去)。
对于整个排序过程需执行n-1趟，最好情况下，总的比较次数达最小值n-1，记录不需移动；最坏情况下，宗的关键字比较次数KCN和记录移动次数RMN均达到最大值，分别为：

若待排序序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下，直接插入排序关键字的比较次数和记录移动次数均约为n²/4。
由此，直接插入排序的时间复杂度为O(n²)。

空间复杂度

直接插入排序只需要一个记录的辅助空间，所以空间复杂度为O(1)。

算法特点

1. 稳定排序。
2. 算法简便，且容易实现。
3. 也适用于链式存储结构，只是在单链表上无需移动记录，只需修改相应的指针。
4. 更适合于初始记录基本有序(正序)的情况，当初始记录无序，n较大时，此算法时间复杂度较高，不宜采用。

2018.10.17