插入排序算法

iugsix8n 于 2021-09-13 发布在 Java

关注(0)|答案(3)|浏览(331)

在这个算法中

let arr =[8,10,222,36,5,0,0];

let insertionSort = (arr) => {
    let len = arr.length;
    for(let i = 0; i < len; i++){
        let curr = arr[i];
        let j = i - 1;
        while(arr[j] > curr){ 
            arr[j+1] = arr[j];
            j--
        };
        j++
        arr[j] = curr;
    };
    console.log(arr);
};

insertionSort(arr);

为什么 j-- 及 j++ 我是说他们到底做什么，我们为什么使用它们(我了解所有其他的事情（这个）
他们在阵列中到底做了什么？改变数字的位置？还是怎样

JavaScript sorting Algorithm

来源：https://stackoverflow.com/questions/68306090/insertion-sort-algorithm-javascript

3条答案

按热度按时间

k97glaaz1#

算法就像拿一副牌。你拿着卡片一次一张地对它们进行排序，然后你向se检查之前的卡片是否大于你拥有的卡片。你要检查之前的那个，直到找到正确的位置。
因此，j是在你拥有一张卡之前检查每张卡的部分。您正在将所有卡向上移动一个位置，以填补拉出卡的空白。
一旦你找到了位置，j++就会用手中的卡来填补当前的空白。

Grab the current index
         V
1,2,4,5,[3]

Look at 5. Is it greater than 3? Yes, move 5 up
       V
1,2,4,[5],5
j--

Look at 4. Is it greater than 3? Yes, Move 4 up
1,2,[4],4,5
j--

Look at 2. Is it greater than 3? NO, leave the 2 alone

Now we are at the "2" so add one to get to the index where 3 needs to live.
j++
1,2,[3],4,5

赞(0）回复(0）举报 2021-09-13

olmpazwi2#

j++表示递增，j--表示递减：

for(let i = 0; i < len; i++)

→在这里，您可以通读数组-从第一项（i=0）到最后一项（i=len）

let curr = arr[i];
    let j = i - 1;
    while(arr[j] > curr){ 
        arr[j+1] = arr[j];
        j--
    };
    j++
    arr[j] = curr;

→假设您有一个子阵列arr[0..i]。在这里，以相反的顺序遍历子数组。每当一个项目高于arr[i]时，它就取其前一个项目的值。它使所有值从一个列组移到数组的右侧。当while循环停止时，数组中位置j上的项取current的值，通过此操作，您可以确保已将arr[i]值移动到arr[0..i]子数组中，确保在该子数组中对项进行排序。
请记住，for循环上部的一个不变量是arr[0..i]已排序。当递增i并使用子数组arr[0..i]在for循环中进行新的迭代时，curr值可以是任何值，但值arr[0..i-1]是排序的，因此嵌套while循环确保curr值插入到它应该插入的位置。
例如，让我们以您的数组为例 [8,10,222,36,5,0,0] . i=4时：

curr = 36
arr[0..i] = [8,10,222,36]

# iteration of the while loop :

    j=3: arr[j]=222>curr -> arr[0..i]=[8,10,222,222]
    j=2: arr[j]=10<curr -> end of the while loop
    (arr[j+1] = curr) -> arr[0..i] = [8,10,36,222]
arr[0..4] is sorted

赞(0）回复(0）举报 2021-09-13

zsbz8rwp3#

澄清：这些运算符起源于“c”语言。
i++是一个后增量运算符，它返回i的当前值，然后将其递增。
++i是一个预递增运算符，它递增i的值，然后返回递增的值。
从那时起，几乎每一种编程语言都复制了这些非常方便的结构。

赞(0）回复(0）举报 2021-09-13