【白话排序算法】简单插入排序法

╰半橙微兮° 2022-12-22 12:28 100阅读 0赞

直接插入排序也就是简单插入排序，顾名思义，其思路简单：假设我有以下序列

[9,2,6,4,3,1,7,5,6]

针对于上述序列，准备一个子序列（为方便理解，此处单独准备一个子序列）

var subseq = [];

从待排序的序列中，由左至右依次取出元素，每次只取一个。将取出的元素**插入**到子序列的合适位置，从而保证子序列始终有序。

比如，第一次取出`9`：

subseq = [9]

第二次取出`2`，`2`这个元素需要找到在子序列中合适的位置，进而保证子序列始终有序。

subseq = [2, 9]

之后以此类推。

我们可以看到：**插入排序的核心工作是找到元素在子序列中正确的位置**。查找可使用二分查找或者粗暴的遍历。

下面我使用JavaScript语言来实现

其实以上的代码还可以进行优化，观察交换的代码片段

...
    temp = seq[j]
    seq[j] = seq[j-1]
    seq[j-1] = temp
    ...

不难发现在交换的过程中，seq\[j-1\]不断的被赋值，然后在下一次比较中发现位置仍旧需要前移（位置仍旧不正确）。也就是会出现赋值语句的浪费。其实可以最终一次性的将seq\[j\]插入到合适的位置。见优化的代码

以上。

还没有评论，来说两句吧...