javascript插入排序

in 算法 with 0 comment

插入排序: 思路是把一个未排序的元素放到一个有序的序列当中，就像我们打地主，当前比如牌是 1,2,5,现在拿到一个4,那么4的位置其实是2和5之间，找到这个位置把4放进去即可

插入排序是一种稳定的排序方法，平均时间复杂度是 O(n²) , 基本插入排序是一种稳定排序

//自己实现的一版插入排序，按定义规规矩来两个循环,这里定义一个finalIndex ，不过可能不严谨,初始值必须指定为0
//如果是希尔排序的话，finalIndex就不太好指定了，所以这版不推荐用，finalIndex要指定为内层的循环变量j才对
 function insertSort1(arr) {
   //每一轮确定一个元素所在的index
   for(let i = 1; i < arr.length; i++) {
     let temp = arr[i]
     let finalIndex = 0
     for(let j = i - 1; j >= 0; j--){
       //arr[i]与0 ~ i - 1之间的元素一一比较
        if(temp < arr[j]){
          //单向赋值
          arr[j+1] = arr[j]
         }else{
          finalIndex = j + 1
          //因为是有序序列，如果当前元素比有序序列最大元素还大不用再比了，直接退出内层循环
          break
         }
         //console.log('j' + j)
     }
     //循环结束的j保存下来就是找到的位置
     arr[finalIndex] = temp
   }
 }

//精简一下，其实可以用内层的循环变量j来替代tempIndex
 function insertSort2(arr) {
   //每一轮确定一个元素所在的index
   for(let i = 1; i < arr.length; i++) {
     let temp = arr[i]
     let j = 0
      for(j = i - 1; j >= 0 && temp < arr[j]; j--){
        //单向赋值
        arr[j+1] = arr[j]
      }
     arr[j + 1] = temp
   }
   console.log(arr)
 }
//内层使用while循环，这里finalIndex也相当于上边内层循环变量j
 function insertSort(arr) {
  for(let i = 1; i < arr.length; i++) {
    let temp = arr[i]
    let finalIndex = i - 1
    while(finalIndex >=0 && temp < arr[finalIndex]) {
      arr[finalIndex + 1] = arr[finalIndex]
      finalIndex --
    }
    arr[finalIndex + 1] = temp
  }
  console.log(arr)
 }

//也可以用两两交换元素的方法,效率跟移动元素比差很多，不推荐

function insertSwap(){
  let outarr = [3, 5, 1, 6, 0, 8, 9, 4, 7, 12]
  for(let i = 1; i < outarr.length; i++){
    let insertVal = outarr[i]
    for(let j = i - 1; j >= 0; j -= 1) {
      if(insertVal < outarr[j]){
        let temp = outarr[j + 1]
        outarr[j + 1] = outarr[j]
        outarr[j] = temp
      }
    }
  }
  console.log(outarr)
}

插入排序的升级版希尔排序

插入排序的平均时间复杂度是 O(n²)，比如一个完全逆序的数组[5,4,3,2,1] ,现在把1插入到已有序列中，这时要把数组元素5,4,3,2 都要移动，代价很高，希尔排序则解决了这个问题。

希尔排序是典型的概念简单，但用算法实现起来不是那么简单的问题，一开始我总是想把每次分开的数组进行单独的插入排序，然后再合并起来，为此写了以下代码，能成功把数组按步长分组，但最终还是没有实现排序

希尔排序是不稳定排序,比如 [3, 5, 1, 6, 0, 3, 9, 4, 7, 2] -->分: [3, 1, 0, 9, 7] + [5, 6, 3, 4, 2],这两组分别排序后合并数组时后半部分的3会跑到前半部分3的前边

 //写的伪代码，只是实现了分组
 function shellSortxx(){
   const arr = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
   for(let gap = parseInt(arr.length / 2); gap >= 1; gap = parseInt(gap / 2)) {
      //这层循环表示把原数组分成gap组
      for(let i = 0; i < gap; i++) {
        let temparr = []
        for(let j = i; j < arr.length && (j + gap < arr.length); j += gap){
          temparr.push(arr[j])
        }
        console.log(temparr)
      }
   }
 }

实际上插入排序没有限制说一定要是数组中下标连续的数排序[1,2,3,4,5] 这样，其实1和3, 2和4同样可以进行插入排序，因此这里的分组是逻辑上的分组，并不是真正分组，其实是自己的思维定势

//1 元素后移
function test(){
  let outarr = [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
  // [3, 1 , 0 , 9 , 7]
  // [5, 6 , 8 , 4 , 2]
  let gap = 2
  for(let i = gap; i < outarr.length; i++){
    let temp = outarr[i]
    let j = 0
    for( j = i - gap; j >= 0; j -= gap){
       if(temp < outarr[j]) {
         outarr[j + gap] = outarr[j]
       }else{
         break
       }
    }
    outarr[j + gap] = temp
  }
  console.log(outarr)
// [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
}

//元素互换,效率跟元素后移差距比较大
function testgap1(){
  let outarr = [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
  // [3, 1 , 0 , 9 , 7]
  // [5, 6 , 8 , 4 , 2]
  let gap = 2
  for(let i = gap; i < outarr.length; i++){
    let insertVal = outarr[i]
    for(let j = i - gap; j >= 0; j -= gap) {
      if(insertVal < outarr[j]){
        let temp = outarr[j + gap]
        outarr[j + gap] = outarr[j]
        outarr[j] = temp
      }
    }
  }
  console.log(outarr)
}

希尔排序一：对原数组分组，每小组使用插入排序（元素后移） 推荐

 //采用元素移动法 内层for
 function shellSort2(){
   const arr = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
   for(let gap = parseInt(arr.length / 2); gap >= 1; gap = parseInt(gap / 2)) {
      for(let i = gap; i < arr.length; i++) {
        let temp = arr[i]
        let j = 0
        for(j = i - gap; j >= 0 && temp < arr[j]; j -= gap){
          arr[j + gap] = arr[j]
        }
        arr[j + gap] = temp
      }
      //if(gap === 2) break
   }
  console.log(arr)
 }

//采用元素移动法 内层while

 function shellSort5(){
   const arr = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
   for(let gap = parseInt(arr.length / 2); gap >= 1; gap = parseInt(gap / 2)) {
      for(let i = gap; i < arr.length; i++) {
        let temp = arr[i]
        let finalIndex = i - gap
        while(finalIndex >= 0 && temp < arr[finalIndex]) {
          arr[finalIndex + gap] = arr[finalIndex]
          finalIndex -= gap
        }
        arr[finalIndex + gap] = temp
      }
   }
  console.log(arr)
 }

希尔排序二：对原数组分组，每小组使用插入排序（元素交换）交换元素比元素后移效率低很多，不推荐

 function shellSort1(){
   const arr = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
   // 3 5 1 6 0 8 9 4 7 2
   for(let gap = parseInt(arr.length / 2); gap >= 1; gap = parseInt(gap / 2)) {
      for(let i = gap; i < arr.length; i++) {
        for(let j = i - gap; j >= 0; j -= gap){
          //console.log(arr[j], arr[i])
          //console.log(i, j, j+gap)
          if(arr[j] > arr[j + gap]) {
            let temp = arr[j]
            arr[j] = arr[j + gap]
            arr[j + gap] = temp
          }
        }
      }
      //if(gap === 2) break
   }
  console.log(arr)
 }

测试16万随机数据：交换元素 shell 35s 非shell 15s ; 元素后移 shell < 1s 非shell 6s

本文由 dealdot ＜dealdot＃163.com＞ 创作, Full Stack Developer @ DeepBlue
本文最后编辑时间为: Jun 11, 2021 at 10:42 am
转载请注明来源

评论已关闭.