数据结构--直接插入排序

我不是女神ヾ 2021-11-29 10:18 246阅读 0赞

# 直接插入排序 #

## 概念 ##

插入排序的基本思想是：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。

插入类排序的整个过程就如同打扑克的理牌过程类似，拿到一张牌然后在已排好序的序列中找到一个合适的位置将这张牌插入。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]

把当前数（**curNum**）之前的所有数字看做有序数组，从后往前逐个比较，找到合适位置后插入。

注：上述写法由于变量`j`可能取值-1，所以在其他语言中可以采用将数组的第一个位置设置为当前值的方式（哨兵）来**避免数组越界问题**。

## 算法要点 ##

*  从后往前查找应插入的位置
 *  查找与移动在同一循环中完成

## 算法分析 ##

从空间角度看，仅需要一个`curName`变量来存储当前需要插入的数值。

从时间角度看，时间主要耗费在数值的比较和数组的移动上。

对于一趟插入排序，算法中的`while`循环的次数主要**取决于待插记录与前`i-1`个记录的关键字的关系**上。  
最好情况为(顺序)： r \[ i \] . k e y > r \[ i − 1 \] . k e y r\[i\].key> r\[i-1\].key r\[i\].key>r\[i−1\].key，while 循环只执行 1 次，且不移动记录；最坏情况为(逆序):  r \[ i \] . k e y < r \[ 1 \] . k e y r\[i\].key< r\[1\].key r\[i\].key<r\[1\].key， 则`while`循环中关键字比较次数和移动记录的次数为`i-1`。

对整个排序过程而言，最好情况是待排序记录本身已按关键字有序排列，此时总的比较次数为 n − 1 n-1 n−1次，移动记录的次数也达到最小值(n-1)(每一次只对待插记录移动一次)；最坏情况是待排序记录按关键字逆序排列，此时总的比较次数达到 最大值为 ( n + 2 ) ( n − 1 ) / 2 (n+2)(n-1)/2 (n\+2)(n−1)/2，记录移动的次数也达到最大值 ( n + 4 ) ( n − 1 ) / 2 (n+4)(n-1)/2 (n\+4)(n−1)/2。

执行的时间耗费主要取决于数据的分布情况。若待排序记录是随机的，即待排序记录可能出现的各种排列的概率相同， 则可以取上述最小值和最大值的平均值，约为 n2/4。因此，直接插入排序的时间复杂度为  T ( n ) = O ( n 2 ) T(n)=O(n^2) T(n)=O(n2)，空间复杂度为 S ( n ) = O ( 1 ) S(n)=O(1) S(n)=O(1)。

排序算法的稳定性必须从算法本身加以证明。直接插入排序方法是稳定的排序方法。在直接插入排序算法中，由于待插入元素的比较是从后向前进行的， 循环`while`( x . k e y < r \[ j \] . k e y x.key< r\[j\].key x.key<r\[j\].key)的判断条件就保证了后面出现的关键字不可能插入到与前面相同的关键字之前。

## 总结 ##

直接插入排序算法简便，比较适用于待排序记录数目较少且基本有序的情况。

当待排记录数目较大时，直接插入排序的性能就不好， 为此我们可以对直接插入 排序做进一步的改进。

在直接插入排序法的基础上，从==减少“比较关键字”和“移动记录”==两种操作的次数着手来进行改进。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]: /images/20211129/a9bbccc843fa46989cf534a1301bd2b2.png