数据结构与算法-直接插入排序

以你之姓@ 2022-04-08 10:21 244阅读 0赞

### 概要 ###

*   *   *  基本概念
         *  java代码实现
         *  图示执行过程
         *  时间复杂度分析

### 基本概念 ###

> 直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排序好的有序表中，从而得到一个新的、记录数增1的有序表。

### java代码实现 ###

/* 声明待排序数组 */
    int[] a = {
        9,1,5,8,3,7,4,6,2};
    int i,j;
    int flag; 
    for (i = 1; i < a.length; i++) {
        
         flag = a[i];	/* 设置哨兵（当前记录） */
         if (a[i] < a[i-1]) {
         /* 当前关键字小于前一个关键字，需要将当前记录往前插入 */
    	for (j = i-1; j >= 0 && a[j] > flag; j--) {
         /* 循环遍历当前关键字之前的所有关键字，并与哨兵比较，若大于哨兵，则记录后移 */
    	     a[j+1] = a[j];	/* 记录后移 */
    	}
            //伪代码 a[j] = flag; 因为j循环最后执行j--，故这边j需+1
    	a[j+1] = flag;	/* 将哨兵插入正确位置 */
          }
    }

### 图示执行过程 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70][]

### 时间复杂度分析 ###

*  最好的情况，也就是待排序的表本身就是有序的，比较次数为n-1次，因为没有移动的记录，故时间复杂度为O(n)；
 *  最坏的情况，即待排序表是逆序的，此时比较次数为2+3+···+n=(n+2)(n-1)/2次，而记录移动次数也达到最大值2+3+···+n=(n+2)(n-1)/2次，如果排序记录是随机的，那么根据概相同的原则，平均比较和移动次数约为n2/4次，故时间复杂度为O(n2)；
 *  因此，直接插入排序时间复杂度为O(n2)，但分析可知性能要比[冒泡排序][Link 1]和[简单选择排序][Link 2]好一些。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70]: /images/20220406/130747b313ea4d9d92a4293d4b483657.png
[Link 1]: https://blog.csdn.net/FTD_SL/article/details/84882498
[Link 2]: https://blog.csdn.net/FTD_SL/article/details/84936838