JavaScript上的插入排序算法

Question

我最近开始学习基于O'Reilly的数据结构和算法的书.

我停止了第12章 - 排序算法.

我无法理解Insertion Sort的工作原理.

这是我正在使用的代码:pasteBin - Insertion Sort

以下是令我困惑的部分:

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());
}

任何人都可以帮助和评论这段代码吗？

Answer 1

它是一种排序算法,从数组的开头开始,一直到结束.对于每个索引处的项目,它会返回先前索引处的项目并检查它是否应放在它们之前.如果是这样,它会将索引与较大的值交换,直到它进入应该具有的索引.

这是带有一些评论的代码,希望它对你有所帮助.

function insertionSort() {
    /* Set up local vars */
    var temp, inner;
    /* Start at index 1, execute outer loop once per index from 1 to the last index */
    for (var outer = 1; outer <= this.dataStore.length - 1; ++outer) {
        /* Store the value at the current index */
        temp = this.dataStore[outer];
        /* Set up temporary index to decrement until we find where this value should be */
        inner = outer;
        /* As long as 'inner' is not the first index, and 
        there is an item in our array whose index is less than 
        inner, but whose value is greater than our temp value... */ 
        while (inner > 0 && (this.dataStore[inner-1] >= temp)) {
            /* Swap the value at inner with the larger value */
            this.dataStore[inner] = this.dataStore[inner-1];
            /* Decrement inner to keep moving down the array */
            --inner;
        }
        /* Finish sorting this value */
        this.dataStore[inner] = temp;
    }
    console.log(this.toString());
}

这是一个包含大量控制台打印输出的jsfiddle,因此您可以逐步浏览它,看看每一步都会发生什么.

Answer 2

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

比较发生在你的情况下dataStore，其中包含我们假设的可比较元素，例如数字。

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

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

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

1. 将我们正在数组中访问的当前元素存储在名为的变量中temp。
2. inner通过和变量跟踪我们在数组中的位置outer，其中：
   • outer是我们的柜台。
   • inner是一个标志，用于确定我们是否正在访问数组中的第一个元素。为什么这很重要？因为在第一次尝试时对第一个元素进行比较是没有意义的。

3. 它将当前元素temp与数组中位于其之前的每个元素进行比较dataStore。这是通过内部while循环完成的，如下所示：

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

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

交换它们将实现以下目的：

• 假设之前的所有元素this.dataStore[inner]都大于 10，并且当前访问的元素this.dataStore[inner]等于 5。这从逻辑上意味着 5 需要位于数组的开头。在这种情况下，我们将继续将 5 一直向下传递，这this.datastore[0]要归功于 while 循环。从而使 5 成为数组中的第一个元素。

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

TLDR：我也喜欢 Justin Powell 的答案，因为它与代码一致，但我认为根据您的理解水平，演练会更有用。我希望它有帮助！