成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專(zhuān)欄INFORMATION COLUMN

JS實(shí)現(xiàn)插入排序

tolerious / 2029人閱讀

摘要：但是，插入排序真的一無(wú)是處嗎答案是否定的，插入排序在實(shí)踐中的使用頻率是很高的，在一些場(chǎng)景下，甚至展現(xiàn)出完勝高級(jí)排序的效率。那么插入排序?qū)嶋H上就是每次將一個(gè)數(shù)插入到有序的數(shù)組中去初始一個(gè)數(shù)字自然有序。

直接插入排序的時(shí)間復(fù)雜度為 O(n^2) ，相較于復(fù)雜度為 O(nlogn) 的快速排序、歸并排序、堆排序、希爾排序，插入排序可謂相形見(jiàn)絀。但是，插入排序真的一無(wú)是處嗎? 答案是否定的，插入排序在實(shí)踐中的使用頻率是很高的，在一些場(chǎng)景下，甚至展現(xiàn)出完勝高級(jí)排序的效率。下面我們一起來(lái)看看。

由于插入排序的實(shí)現(xiàn)很簡(jiǎn)單，首先直接放出代碼：

function insertSort(arr) {
  let length = arr.length;
  for(let i = 1; i < length; i++) {
    let temp = arr[i];
    let j = i;
    for(; j > 0; j--) {
      if(temp >= arr[j-1]) {
        break;      // 當(dāng)前考察的數(shù)大于前一個(gè)數(shù)，證明有序，退出循環(huán)
      }
      arr[j] = arr[j-1]; // 將前一個(gè)數(shù)復(fù)制到后一個(gè)數(shù)上
    }
    arr[j] = temp;  // 找到考察的數(shù)應(yīng)處于的位置
  }
  return arr;
}

// example
let arr = [2,5,10,7,10,32,90,9,11,1,0,10]
console.log(insertSort(arr));

插入排序的思路跟整理?yè)淇伺剖且粯拥?，即每次拿到一張牌，按大小順序?qū)⑵洳迦氲胶线m的位置。那么插入排序?qū)嶋H上就是：每次將一個(gè)數(shù)插入到有序的數(shù)組中去(初始一個(gè)數(shù)字自然有序)。

下面以實(shí)例結(jié)合代碼來(lái)分析一個(gè)插入排序的過(guò)程：

由于第一個(gè)數(shù) 6 是自然有序的，所以我們從第二個(gè)數(shù) 5 開(kāi)始考察， 將 5 取出與它的前一個(gè)數(shù) 6 比較，5 < 6， 將 6 復(fù)制到 5 的位置，5 向前移動(dòng)繼續(xù)比較，此時(shí) 5 已經(jīng)處于數(shù)組第一位，第一次排序結(jié)束，將 5 放入當(dāng)前位置；

此時(shí) [5, 6] 已經(jīng)構(gòu)成有序數(shù)組，考察 4，將 4 取出與它的前一個(gè)數(shù) 6 比較，4 < 6，將 6 復(fù)制到 4 的位置；4 向前移與 5 比較，4 < 5，將 5 復(fù)制到前一個(gè) 6 的位置，此時(shí) 4 處于數(shù)組第一位，第二趟排序結(jié)束。

后面的排序過(guò)程與前面分析的過(guò)程一致，總結(jié)一下就是：不斷將大于當(dāng)前考察對(duì)象的數(shù)后移一位，直到找到考察對(duì)象應(yīng)該處于的位置。有一個(gè)需要注意的點(diǎn)是，考察對(duì)象不一定是要一直向前移動(dòng)到數(shù)組第一個(gè)位置才結(jié)束一趟排序，如果中間找到了合適的位置，這趟排序是可以提前終止的。
舉例：

這一點(diǎn)正是插入排序的精髓所在！如果對(duì)一個(gè)已經(jīng)有序的數(shù)組使用插入排序，插入排序只會(huì)遍歷數(shù)組一遍，時(shí)間復(fù)雜度退化為 O(n)；可以想象，如果對(duì)一個(gè)接近有序的數(shù)組使用插入排序，其效率是非?？捎^(guān)的，而很多時(shí)候我們處理的數(shù)據(jù)是接近有序的，只需調(diào)整一些無(wú)序項(xiàng)，所以插入排序是很有用的。

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://hztianpu.com/yun/95945.html

相關(guān)文章

  • 排序算法分析總結(jié)（附js實(shí)現(xiàn)）

    摘要：本文對(duì)一些排序算法進(jìn)行了簡(jiǎn)單分析，并給出了的代碼實(shí)現(xiàn)。平均時(shí)間復(fù)雜度不好分析，它是冒泡排序是穩(wěn)定的排序算法。冒泡排序是原地排序算法原地排序指的是空間復(fù)雜度是的排序算法。歸并排序，會(huì)將數(shù)組從中間分成左右兩部分。 本文對(duì)一些排序算法進(jìn)行了簡(jiǎn)單分析，并給出了 javascript 的代碼實(shí)現(xiàn)。因?yàn)楸疚陌舜罅康呐判蛩惴?，所以分析不?huì)非常詳細(xì)，適合有對(duì)排序算法有一定了解的同學(xué)。本文內(nèi)容其實(shí)不...

    liaoyg8023 評(píng)論0 收藏0

  • 排序算法速度測(cè)試（插入排序、二分法插入、選擇排序、快速排序、堆排序）js實(shí)現(xiàn)

    摘要：公共函數(shù)庫(kù)用于取出隨機(jī)排列的數(shù)字原數(shù)組給原數(shù)組賦值排序算法插入排序時(shí)間復(fù)雜度二分法插入排序選擇排序快速排序一堆排序測(cè)試用例插入排序時(shí)間測(cè)試二分法插入排序時(shí)間測(cè)試選擇排序時(shí)間測(cè)試快速排序時(shí)間測(cè)試一堆 公共函數(shù)庫(kù)（用于取出隨機(jī)排列的數(shù)字） module.exports={ randomIntegerArray:function(count){ var origina...

    mochixuan 評(píng)論0 收藏0

  • JS中可能用得到的全部的排序算法

    本篇有7k+字, 系統(tǒng)梳理了js中常見(jiàn)的12種排序算法。除了基本排序算法，文章還包含了希爾排序、堆排序、桶排序等較為復(fù)雜的排序?qū)崿F(xiàn)，如果喜歡請(qǐng)點(diǎn)贊支持~謝謝. 原文: http://louiszhai.github.io/20... 導(dǎo)讀 排序算法可以稱(chēng)得上是我的盲點(diǎn), 曾幾何時(shí)當(dāng)我知道Chrome的Array.prototype.sort使用了快速排序時(shí), 我的內(nèi)心是奔潰的(啥是快排, 我只知道...

    verano 評(píng)論0 收藏0

  • JS實(shí)現(xiàn)希爾排序

    摘要：希爾排序本質(zhì)上是一種插入排序，但是對(duì)數(shù)列進(jìn)行了等間隔分組處理，在每一組中做插入排序，這一優(yōu)化使得時(shí)間復(fù)雜度降到了以下。 希爾排序本質(zhì)上是一種插入排序，但是對(duì)數(shù)列進(jìn)行了等間隔分組處理，在每一組中做插入排序，這一優(yōu)化使得時(shí)間復(fù)雜度降到了O(n^2)以下。 基本思想 希爾排序是按一定的間隔對(duì)數(shù)列進(jìn)行分組，然后在每一個(gè)分組中做插入排序；隨后逐次縮小間隔，在每一個(gè)分組中做插入排序...直到間隔等...

    chadLi 評(píng)論0 收藏0

  • 用js寫(xiě)插入排序和選擇排序

    摘要：總結(jié)一下，插入排序優(yōu)于選擇排序。插入排序可以提前終止內(nèi)層循環(huán)，如果數(shù)組近乎有序，那么效率會(huì)很高。我的寫(xiě)的不是最好的，僅僅是解釋概念，有興趣的同學(xué)可以自己寫(xiě)一個(gè)更好的插入排序和選擇排序。 我覺(jué)得作為前端學(xué)學(xué)算法也是有益處的吧，所以今天就先來(lái)講講最基礎(chǔ)的排序算法。提升我們程序員的內(nèi)功~ 插入排序 插入排序是n^2的基礎(chǔ)排序方法，大致思想是假設(shè)一個(gè)數(shù)組的前n個(gè)元素已經(jīng)有序，然后考慮把第n+1...

    SHERlocked93 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<