插入排序的思路

老师你看我的sort 与sort2 是不是也是插入排序的思想,如果是,我就有点模糊,就是插入排序的思想到底是重点是在采用插入这个动作,还是说是保证[0,i)是已经排好序的

class InsertSort{<br>static sort(arr){<br>

// 假设第一个[0,0]已经排序完成<br>for(let i=1; i<arr.length; i++){<br>let curIndex = i;<br>for(let j=i-1; j>=0; j--){<br>if(arr[j]>arr[curIndex]) {<br>this.swap(arr, j, curIndex);<br>curIndex = j;<br>console.log(`第${j}次:`+arr);<br>}<br>}<br>// console.log(`第${i}次:`+arr);<br>}<br>return arr;<br>}<br>static sort2(arr){<br>// 假设第一个[0,0]已经排序完成<br>for(let i=1; i<arr.length; i++){<br>let curIndex = arr[i];<br>for(let j=i-1; j>=0; j--){<br>if(arr[j]>curIndex) {<br>arr[j+1] = arr[j];<br>arr[j] = curIndex;<br>}<br>}<br>console.log(`第${i}次:`+arr);<br>}<br>return arr;<br>}<br><br>static sort3(arr){<br>// 假设第一个[0,0]已经排序完成<br>for(let i=1; i<arr.length; i++){<br>for(let j=i; j-1>=0; j--){<br>if(arr[j]<arr[j-1]) {<br>this.swap(arr, j, j-1);<br>}else{<br>break;<br>}<br>}<br>console.log(`第${i}次:`+arr);<br>}<br>return arr;<br>}<br>static swap(arr, i, j){<br>let temp = arr[i];<br>arr[i] = arr[j];<br>arr[j]=temp;<br>}<br>}<br>

else2021 2021-04-05

源自：排序基础 2-2 实现插入排序法

收起

1回答

liuyubobobo 2021-04-05 17:34:13

插入排序的关键是“插入”这个动作。

选择排序和冒泡排序在每轮循环中也是保证 [0,i) 排好序的，但是他们和插入排序是不同的。

继续加油！：）

收起回答

提问者 else2021 #1

哦哦,明白了,那老师,我的前两种写法是不是也是正确的

2021-04-05 17:42:17
liuyubobobo 回复提问者 else2021 #2

我看了一遍你的逻辑，是正确的。其实你的前两个实现，本质也是插入排序的思路。只不过对与如何实现“插入”这个过程，具体的实现方式和我的实现方式不同而已：）

2021-04-05 18:18:52