成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

用JavaScript實現(xiàn)插入排序

LittleLiByte / 1934人閱讀

摘要：實現(xiàn)插入排序插入排序是一種非常簡單的算法，最適合大部分已經(jīng)被排好序的數(shù)據(jù)。由此才有了這個名字插入排序。插入排序的最壞情況是輸入的數(shù)組是按逆序排序的。總結(jié)當輸入的數(shù)組已經(jīng)大部分被排好序時，插入排序的效果最佳。

翻譯：瘋狂的技術(shù)宅
https://medium.com/@jimrottin...

本文首發(fā)微信公眾號：前端先鋒
歡迎關(guān)注，每天都給你推送新鮮的前端技術(shù)文章

插入排序的工作原理是選擇當前索引 i 處的元素，并從右向左搜索放置項目的正確位置。

實現(xiàn)插入排序

插入排序是一種非常簡單的算法，最適合大部分已經(jīng)被排好序的數(shù)據(jù)。在開始之前，通過可視化演示算法如何運作一個好主意。你可以參考前面的動畫來了解插入排序的工作原理。

算法的基本思想是一次選擇一個元素，然后搜索并插入到正確的位置。由此才有了這個名字：插入排序。這種操作將會導致數(shù)組被分為兩個部分 —— 已排序部分和未排序的元素。有些人喜歡把它描繪成兩個不同的數(shù)組 —— 一個包含所有未排序的元素，而另一個的元素是完全排序的。但是將其描述為一個數(shù)組更符合代碼的工作方式。

先來看看代碼，然后再進行討論。

const insertionSort = (nums) => {
  for (let i = 1; i < nums.length; i++) {
    let j = i - 1
    let tmp = nums[i]
    while (j >= 0 && nums[j] > tmp) {
      nums[j + 1] = nums[j]
      j--
    }
    nums[j+1] = tmp
  }
  return nums
}

在插入排序的代碼中有兩個索引：i 和 j。 i 用來跟蹤外循環(huán)并表示正在排序的當前元素。它從 1 開始而不是0，因為當我們在新排序的數(shù)組中只有一個元素時，是沒有什么可做的。所以要從第二個元素開始，并將它與第一個元素進行比較。第二個索引 j 從 i-1 開始，從右往左迭代，一直到找到放置元素的正確位置。在此過程中，我們將每個元素向后移動一個位置，以便為要排序的新元素騰出空間。

這就是它的全部過程！如果你只是對實現(xiàn)感興趣，那你就不用再看后面的內(nèi)容了。但如果你想知道怎樣才能正確的實現(xiàn)這個算法，那么請繼續(xù)往下看！

檢查循環(huán)不量變條件

為了確定算法是否能夠正常工作而不是恰好得出了給定輸入的正確輸出，我們可以建立一組在算法開始時必須為真的條件，在算法結(jié)束時，算法的每一步都處于條件之中。這組條件稱為循環(huán)不變量，并且必須在每次循環(huán)迭代后保持為真。

循環(huán)不變量并不是總是相同的東西。它完全取決于算法的實現(xiàn)，是我們作為算法設計者必須確定的。在例子中，我們每次迭代數(shù)組中的一個元素，然后從右向左搜索正確的位置以插入它。這將會導致數(shù)組的左半部分（到當前索引為止）始終是最初在該數(shù)組切片中找到的元素的排序排列。換一種說法是

插入排序的循環(huán)不變量表示到當前索引的所有元素“A [0..index]”構(gòu)成在我們開始排序前最初在“A [0..index]”中找到的元素的排列順序。

要檢查這些條件，我們需要一個可以在循環(huán)中調(diào)用的函數(shù)，該函數(shù)作為參數(shù)接收：

新排序的數(shù)組

原始輸入

當前的索引。

一旦有了這些，就能將數(shù)組從 0 開始到當前索引進行切片，并運行我們的檢查。第一個檢查是新數(shù)組中的所有元素是否都包含在舊數(shù)組中，其次是它們都是有序的。

//用于檢查插入排序循環(huán)不變的函數(shù)
const checkLoopInvariant = (newArr, originalArr, index) => {
  //need to slice at least 1 element out
  if (index < 1) index = 1

  newArr = newArr.slice(0,index)
  originalArr = originalArr.slice(0, index)

  for (let i=0; i < newArr.length; i++) {

    //check that the original array contains the value
    if (!originalArr.includes(newArr[i])) {
      console.error(`Failed! Original array does not include ${newArr[i]}`)
    }

    //check that the new array is in sorted order
    if (i < newArr.length - 1 && newArr[i] > newArr[i+1]) {
      console.error(`Failed! ${newArr[i]} is not less than ${newArr[i+1]}`)
    }
  }
}

如果在循環(huán)之前、期間和之后調(diào)用此函數(shù)，并且它沒有任何錯誤地通過，就可以確認我們的算法是正常工作的。修改我們的代碼以包含此項檢查，如下所示：

const insertionSort = (nums) => {
  checkLoopInvariant(nums, input, 0)
  for (let i = 1; i < nums.length; i++) {
    ...
    checkLoopInvariant(nums, input, i)
    while (j >= 0 && nums[j] > tmp) {
      ...
    }
    nums[j+1] = tmp
  }
  checkLoopInvariant(nums, input, nums.length)
  return nums
}

注意下圖中在索引為2之后的數(shù)組狀態(tài)，它已對3個元素進行了排序。

如你所見，我們已經(jīng)處理了3個元素，前3個元素按順序排列。你還可以看到已排序數(shù)組的前3個數(shù)字與原始輸入中的前3個數(shù)字相同，只是順序不同。因此保持了循環(huán)不變量。

分析運行時間

我們將要使用插入排序查看的最后一件事是運行時。執(zhí)行真正的運行時分析需要大量的數(shù)學運算，你可以很快找到自己的雜草。如果你對此類分析感興趣，請參閱Cormen的算法導論，第3版。但是，就本文而言，我們只會進行最壞情況的分析。

插入排序的最壞情況是輸入的數(shù)組是按逆序排序的。這意味著對于我們需要迭代每個元素，并在已經(jīng)排序的元素中找到正確的插入點。外部循環(huán)表示從 2 到 n 的總次數(shù)（其中 n 是輸入的大?。⑶颐看蔚仨殘?zhí)行 i-1 次操作，因為它從 i-1 迭代到零。

這個結(jié)論的證明超出了本文的范圍。老實說，我只是將它與最佳情況進行比較，其中元素已經(jīng)排序，因此每次迭代所需要的時間都是固定的......

就 big-O 表示法而言，最壞情況是 ?(n2)，最好的情況是?(n)。我們總是采用最壞情況的結(jié)果，因此整個算法的復雜度是?(n2)。

總結(jié)

當輸入的數(shù)組已經(jīng)大部分被排好序時，插入排序的效果最佳。一個好的程序應該是將一個新元素插入已經(jīng)排好序的數(shù)據(jù)存儲中。即便是你可能永遠不必編寫自己的排序算法，并且其他類型（例如歸并排序和快速排序）更快，但是我認為用這種方式去分析算法的確很有趣。

本文首發(fā)微信公眾號：前端先鋒 歡迎掃描二維碼關(guān)注公眾號，每天都給你推送新鮮的前端技術(shù)文章

歡迎繼續(xù)閱讀本專欄其它高贊文章：

12個令人驚嘆的CSS實驗項目

必須要會的 50 個React 面試題

世界頂級公司的前端面試都問些什么

11 個最好的 JavaScript 動態(tài)效果庫

CSS Flexbox 可視化手冊

從設計者的角度看 React

過節(jié)很無聊？還是用 JavaScript 寫一個腦力小游戲吧！

CSS粘性定位是怎樣工作的

一步步教你用HTML5 SVG實現(xiàn)動畫效果

程序員30歲前月薪達不到30K，該何去何從

14個最好的 JavaScript 數(shù)據(jù)可視化庫

8 個給前端的頂級 VS Code 擴展插件

Node.js 多線程完全指南

把HTML轉(zhuǎn)成PDF的4個方案及實現(xiàn)

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/109417.html

相關(guān)文章

  • 用 JavaScript 實現(xiàn)鏈表操作 - 06 Insert Sort

    摘要：需求實現(xiàn)一個函數(shù)對鏈表進行升序排列插入排序。關(guān)于插入排序插入排序的介紹可以看，大體邏輯為建立一個新的空鏈表。遍歷完成，返回新鏈表。代碼如下總結(jié)因為有上個的函數(shù)的幫助，這個插入排序?qū)崿F(xiàn)起來非常簡單。 TL;DR 2016 年末最后一篇，對鏈表進行插入排序。系列目錄見 前言和目錄 。 需求 實現(xiàn)一個 insertSort() 函數(shù)對鏈表進行升序排列（插入排序）。實現(xiàn)過程中可以使用 上一個 ...

    doodlewind 評論0 收藏0

  • JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 冒泡排序、插入排序、選擇排序

    摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩(wěn)定的排序算法。選擇排序思路選擇排序算法的實現(xiàn)思路有點類似插入排序，也分已排序區(qū)間和未排序區(qū)間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法為王。 想學好前端，先練好內(nèi)功，...

    canger 評論0 收藏0

  • 深入淺出 JavaScript 的 Array.prototype.sort 排序算法

    摘要：快速排序是不穩(wěn)定的排序算法。瀏覽器的實現(xiàn)不同有什么影響排序算法不穩(wěn)定有什么影響舉個例子某市的機動車牌照拍賣系統(tǒng)，最終中標的規(guī)則為按價格進行倒排序相同價格則按照競標順位即價格提交時間進行正排序。 本文要解決的問題 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一種直觀的方式展示 Array.prototype.sort 的時間復雜度，看看它有多快？ 3、...

    itvincent 評論0 收藏0

  • JavaScript各種排序算法的實現(xiàn)及其速度性能分析

    摘要：今天我們來討論的問題有兩個如何用實現(xiàn)選擇排序冒泡排序插入排序快速排序歸并排序堆排序?qū)ι傻娜f個隨機數(shù)進行排序，各個排序算法的性能分析?？焖倥判蚩焖倥判蛩惴ɑ旧鲜敲嬖嚤乜寂判蛩惴?，也是傳聞最好用的算法。 今天我們來討論的問題有兩個： 如何用JavaScript實現(xiàn)選擇排序、冒泡排序、插入排序、快速排序、歸并排序、堆排序； 對生成的10萬個隨機數(shù)進行排序，各個排序算法的性能分析。 創(chuàng)...

    yuanxin 評論0 收藏0

  • JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 十大經(jīng)典排序算法匯總

    摘要：筆者寫的數(shù)據(jù)結(jié)構(gòu)與算法之美系列用的語言是，旨在入門數(shù)據(jù)結(jié)構(gòu)與算法和方便以后復習。這應該是目前較為簡單的十大經(jīng)典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經(jīng)典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數(shù)據(jù)。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法為王。想學好前端，先練好內(nèi)功，內(nèi)功不行，就...

    zsy888 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<