国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

用JavaScript實現插入排序

LittleLiByte / 1928人閱讀

摘要：實現插入排序插入排序是一種非常簡單的算法，最適合大部分已經被排好序的數據。由此才有了這個名字插入排序。插入排序的最壞情況是輸入的數組是按逆序排序的?？偨Y當輸入的數組已經大部分被排好序時，插入排序的效果最佳。

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

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

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

實現插入排序

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

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

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

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

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

檢查循環不量變條件

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

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

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

要檢查這些條件，我們需要一個可以在循環中調用的函數，該函數作為參數接收：

新排序的數組

原始輸入

當前的索引。

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

//用于檢查插入排序循環不變的函數
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]}`)
    }
  }
}

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

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之后的數組狀態，它已對3個元素進行了排序。

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

分析運行時間

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

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

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

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

總結

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

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

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

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

必須要會的 50 個React 面試題

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

11 個最好的 JavaScript 動態效果庫

CSS Flexbox 可視化手冊

從設計者的角度看 React

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

CSS粘性定位是怎樣工作的

一步步教你用HTML5 SVG實現動畫效果

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

14個最好的 JavaScript 數據可視化庫

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

Node.js 多線程完全指南

把HTML轉成PDF的4個方案及實現

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/109417.html

相關文章

  • 用 JavaScript 實現鏈表操作 - 06 Insert Sort

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

    doodlewind 評論0 收藏0

  • JavaScript 數據結構與算法之美 - 冒泡排序、插入排序、選擇排序

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

    canger 評論0 收藏0

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

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

    itvincent 評論0 收藏0

  • JavaScript各種排序算法的實現及其速度性能分析

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

    yuanxin 評論0 收藏0

  • JavaScript 數據結構與算法之美 - 十大經典排序算法匯總

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

    zsy888 評論0 收藏0

發表評論

0條評論

LittleLiByte

男|高級講師

TA的文章

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