JavaScript上的插入排序算法 [英] Insertion Sort Algorithm on JavaScript

问题描述

我最近开始根据 O'Reilly的JavaScript数据结构和算法来学习算法。 / a>。

I recently started learning algorithms based on the book Data Structures and Algorithms with JavaScript from O'Reilly.

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

I stopped on Chapter 12 - Sorting Algorithms.

我不明白插入排序的方式

I can not understand how Insertion Sort works.

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

Here is the code I am working with: pasteBin - Insertion Sort

下面是令我困惑的部分：

Below is the part that is confusing to me:

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

有人可以帮助和评论此代码吗？

Could anyone help and comment on this code?

推荐答案

插入排序的主要概念是按比较对元素进行排序。

The main concept behind insertion sort is to sort elements by comparison.

比较发生在 dataStore 数组的情况，其中包含我们认为是可比较的元素（例如数字）。

The comparison occurs in your case for a dataStore array, containing what we assume to be comparable elements such as numbers.

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

In order to compare element by element, this insertion sort algorithm starts at the beginning of the dataStore array and will continue to run until the end of the array has been reached. This is accomplished by a for loop:

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

作为算法按顺序遍历每个元素，它将：

As the algorithm goes through each element in order, it will:

1. 将我们要访问的当前元素存储在名为<$ c $的变量中c> temp 。


2. 通过 inner 和外部变量，其中：
   
   
   
   
   • 外部是
   
   
   • inner 是一个标志，用于确定是否要访问数组中的第一个元素。为什么这很重要？因为没有必要在第一个元素上进行比较，因此在第一次尝试时就没有意义。
   
   

1. Store the current element we are visiting in the array in a variable called temp.
2. Keep track of the location we are in the array via the inner and outer variables, where:
   • outer is our counter.
   • inner is a flag to determine whether or not we are visiting the first element in the array. Why is this important? Because there is no point in doing a comparison on the first element, on the first try.

它将比较当前元素。 temp 元素，并在 dataStore 数组中的每个元素之前。这是通过内部 while 循环完成的，如下所示：

It will compare the current element temp with each element that came before it in the dataStore array. This is accomplished by an inner while loop as seen here:

while（内部> ; 0&&（this.dataStore [inner-1]> = temp））

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

This tells you that, as long as all previous visited elements in the dataStore array are greater than or equal to temp, our temporary variable used to store the current element; we want to swap these values.

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

Swapping them will accomplish the following:

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

• Assume all elements before this.dataStore[inner] are greater than 10, and the currently visited element this.dataStore[inner] equals 5. This logically means that 5 needs to be at the beginning of the array. In such case we would continue to pass 5 all the way down to this.datastore[0] thanks to the while loop. Thus making 5 the first element in the array.

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

At the end of this swapping, the value in temp is placed accordingly to the current position we are in the array, just to remind you which position this is, it's stored the variable outer.

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

TLDR: I also like Justin Powell's answer as it sticks with the code, but I thought a walk through would be more useful depending on your level of understanding. I hope it helps!

这篇关于JavaScript上的插入排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！