JavaScript上的插入排序算法

一尘不染

JavaScript上的插入排序算法

algorithm

我最近开始从O’Reilly的书《基于JavaScript的数据结构和算法》中学习算法。

我停在第12章-排序算法。

我不明白插入排序是如何工作的。

这是我正在使用的代码：pasteBin-插入排序

以下是令我困惑的部分：

function insertionSort() {
    var temp, inner;
    for (var outer = 1; outer <= this.dataStore.length - 1; ++outer) {
        temp = this.dataStore[outer];
        inner = outer;
        while (inner > 0 && (this.dataStore[inner-1] >= temp)) {
            this.dataStore[inner] = this.dataStore[inner-1];
            --inner;
        }
        this.dataStore[inner] = temp;
    }
    console.log(this.toString());
}

有人可以帮助对此代码进行评论吗？

阅读 203

2020-07-28

共1个答案

一尘不染

插入排序背后的主要概念是通过比较对元素进行排序。

在您的情况下，比较是针对dataStore数组进行的，其中包含我们认为是可比较的元素（例如数字）。

为了逐个元素地比较，此插入排序算法从dataStore数组的开头开始，并将继续运行，直到到达数组的末尾。这是通过for循环完成的：

for (var outer = 1; outer <= this.dataStore.length - 1; ++outer)

当算法按顺序遍历每个元素时，它将：

将我们要访问的当前元素存储在名为的变量中temp。
通过inner和outer变量来跟踪我们在数组中的位置，其中：
- outer 是我们的柜台。
- inner是确定我们是否要访问数组中第一个元素的标志。为什么这很重要？因为在第一个元素上进行比较没有任何意义，因此请先尝试一下。
它将比较当前元素temp与dataStore数组中之前的每个元素。这是通过一个内部while循环完成的，如下所示：

while (inner > 0 && (this.dataStore[inner-1] >= temp))

这告诉您，只要dataStore数组中所有先前访问的元素都大于或等于temp，我们用于存储当前元素的临时变量；我们想交换这些值。

交换它们将完成以下操作：

假设之前的所有元素this.dataStore[inner]都大于10，并且当前访问的元素this.dataStore[inner]等于5。从逻辑上讲，这意味着5必须位于数组的开头。在这种情况下，this.datastore[0]由于while循环，我们将一直向下传递5 。因此，将5设为数组中的第一个元素。

交换结束时，in的值对应于temp我们在数组中的当前位置放置，只是提醒您这是哪个位置，它存储了变量outer。

TLDR：我也喜欢Justin Powell的回答，因为它坚持使用代码，但是我认为根据您的理解水平，逐步学习会更有用。希望对您有所帮助！

2020-07-28