JavaScript插入排序

chun

2022-4-13

前端笔记数据结构

思路

从第一个元素开始，该元素可以认为已经被排序；
取出第i个元素记为target，在已经排序的元素序列中从后向前扫描；
如果target小于已排序的元素，则交换位置；target更新；
else大于break跳出循环；
重复步骤3~5

「时间复杂度: O(n*n)」

核心程序：取出第i个元素，在序列中找到一个合适的位置并将她插入到该位置上。

方法1：

function insertSort(array) {

for (let i = 1; i < array.length; i++) {

let temp=array[i];

for (let j = i - 1; j >= 0; j--) {

if(temp<array[j]) {//数组往后移

array[j+1] =array[j];

if(j==0){//插入第0位的特殊情况

array[j] = temp;

}

else {//插入相应的位置

array[j+1] =temp;

break;

}

return array;

}

let a=[2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]

console.log(insertSort(a))

方法2（简便）：

   function insertSort(array) {
      for (let i = 1; i < array.length; i++) {
        let target = i;
        for (let j = i - 1; j >= 0; j--) {//在已排序中找大于target的元素后移
          if (array[target] < array[j]) {
            [array[target], array[j]] = [array[j], array[target]]
//交换位置[2,3,1]=>[2,1,3]
            target = j;//指向1
          } else {//在剩余的已排序元素中找到小于target的则跳出循环
            break;
          }
        }
      }
      return array;
    }

阅读剩余

作者：chun

链接：https://chun53.top/794.html

文章版权归作者所有，未经允许请勿转载。

THE END