JS插入排序簡(jiǎn)單理解與實(shí)現(xiàn)方法分析

發(fā)布時(shí)間：2020-09-02 16:17:23 來(lái)源：腳本之家閱讀：157 作者：循環(huán)源圈欄目：web開發(fā)

本文實(shí)例講述了JS插入排序簡(jiǎn)單理解與實(shí)現(xiàn)方法。分享給大家供大家參考，具體如下：

在這里，我詳細(xì)的講一下我個(gè)人對(duì)于插入排序的理解。

每個(gè)人對(duì)于事物的理解都是不一樣的，因?yàn)槊總€(gè)人對(duì)世界萬(wàn)物的看法和思考方式都不一樣。因此，對(duì)于排序算法，我想每個(gè)人都有自己的理解方式，所以，雖然博客園里有很多關(guān)于排序的文章，但那只是其他人對(duì)這幾個(gè)排序的理解方式，而筆者也有自己的理解方式，所以，筆者也就沒(méi)有在意博客園寫了那么多關(guān)于排序的文章而還在這里寫下個(gè)人的見解了。

對(duì)于插入排序，筆者是這么理解的：

插入排序就是把一組數(shù)字分成兩部分，一部分是排好順序的，另一部分是沒(méi)有排好順序的，然后，就是從沒(méi)有排好順序的那組數(shù)字中獲取數(shù)字，把它插入到已經(jīng)排好的順序的那部分?jǐn)?shù)字中，當(dāng)然，在插入到已經(jīng)排好順序的那部分?jǐn)?shù)字時(shí)，你還必須讓這個(gè)插入進(jìn)來(lái)的數(shù)字與已經(jīng)排好順序的數(shù)字進(jìn)行比較，為的是保證已經(jīng)排好的順序的那部分?jǐn)?shù)字不被打亂，插入排序的關(guān)鍵也就是這里，如果能夠理解這里，我想對(duì)于接下來(lái)我寫的代碼應(yīng)該不難理解了。

我舉個(gè)例子：

這是個(gè)雜亂的一組數(shù)字：8,1,2,5,9,3,4,6,7,0

看到上面的那組數(shù)字嗎？你覺(jué)得能把這組數(shù)字分出一部分有序的出來(lái)嗎？因?yàn)?，我們插入排序首先要做的就是在一組數(shù)字中找出有序的部分，所以，首先，你得從一組數(shù)字中找到有序的才行對(duì)吧？其實(shí)，上面那組數(shù)字是可以找到有序的部分的。怎么說(shuō)呢？很簡(jiǎn)單，你把第一個(gè)數(shù)字8當(dāng)成一部分，其余的當(dāng)成另外一部分，不就分出一部分有序的數(shù)字和一部分無(wú)序的數(shù)字了嗎？你想想，第一部分就是一個(gè)數(shù)字8，一個(gè)數(shù)字構(gòu)成的一部分，它都不用比較了，這還不是有序的那還得了，呵呵。

之所以在這里提一下一個(gè)數(shù)字當(dāng)成一部分的情況，那是因?yàn)?，我們所提供的插入排序的?shù)字是雜亂的，無(wú)序的，我們誰(shuí)也不能保證最開始的那部分一定是有序的，因此，我們就只能選擇一個(gè)數(shù)字作為有序的那部分才能保證所有的排序都是在有序那部分進(jìn)行的，不然，插入排序就沒(méi)辦法找到有序的那部分了。

插入排序開始：

第一個(gè)有序部分（就是第一個(gè)數(shù)字了）：8

第一個(gè)無(wú)序部分（就是剩下的部分了）：1,2,5,9,3,4,6,7,0

根據(jù)前面所講的插入排序原理：從無(wú)序部分中獲取數(shù)字，把它插入到有序的那一部分中。

1、這里怎么在無(wú)序部分中獲取數(shù)字？

2、怎么把獲取的數(shù)字有序的插入到有序部分中？換句話說(shuō)，就是怎么讓這個(gè)獲取的數(shù)字插入到有序的那部分之后，有序的那部分還是有序的，并不會(huì)被這個(gè)插入的數(shù)字破壞掉隊(duì)形而變得無(wú)序？

首先回答第一個(gè)問(wèn)題：

這個(gè)問(wèn)題其實(shí)很簡(jiǎn)單啦，我們把那組無(wú)序的數(shù)組分成兩部分之后，只要從無(wú)序的那部分?jǐn)?shù)字的第一個(gè)數(shù)字開始往后面獲取數(shù)字就行了，是吧？

接下來(lái)回答第二個(gè)問(wèn)題：

這個(gè)問(wèn)題有點(diǎn)復(fù)雜，我就不敘述了，直接舉例子吧，這樣子更容易理解。

第二次插入排序：

首先我們從上面已經(jīng)分好的無(wú)序部分：1,2,5,9,3,4,6,7,0（前面已經(jīng)把8分成有序的部分了）獲取第一個(gè)數(shù)字1，假設(shè)我們是從小排到大的排序這組數(shù)字，獲取1這個(gè)數(shù)字之后，我們就要把1插入到8中啦，對(duì)吧？

我們把1和8做比較，比較規(guī)則：大于，8>1？真，既然是真，那么它們就要調(diào)換位置了，對(duì)吧？

所以經(jīng)過(guò)一次排序之后，原來(lái)的那組有序數(shù)字和無(wú)序數(shù)字就變成了下面的了：

第二個(gè)有序部分：1,8

第二個(gè)無(wú)序部分：2,5,9,3,4,6,7,0

經(jīng)過(guò)兩輪的有序和無(wú)序分組之后，就得到上面的兩個(gè)有序數(shù)字和無(wú)序數(shù)字了，接下來(lái)，我們繼續(xù)插入排序

依然從后面的無(wú)序部分獲取數(shù)字2，獲取之后，從有序部分的后面數(shù)字開始逐一的和2做比較，8>2嗎？真，那么它們兩者就調(diào)換位置。接下來(lái)讓1和2作比較，1>2嗎？假，那么就跳過(guò)不管，所以，就得到下面的有序和無(wú)序部分了。

第三個(gè)有序部分：1,2,8

第三個(gè)無(wú)序部分：5,9,3,4,6,7,0

比較到這里，插入排序已經(jīng)初步形成有序數(shù)字了，接下來(lái)的比較我就不敘述了，你們自己想想吧。接下來(lái)是代碼，代碼的思維和這里的描述是一樣的，你可以自己調(diào)試看一下代碼的執(zhí)行過(guò)程就再明白不過(guò)了。

注意、每一輪比較過(guò)后，有序部分總會(huì)多一個(gè)元素，而無(wú)序部分則少一個(gè)元素，插入排序嘛，就是從無(wú)序部分截取數(shù)字插入到有序部分中啦，這和下面的代碼循環(huán)是一致的。

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="zh-cn">
<head>
  <meta http-equiv="Content-Type" content="text/html;charset=UTF-8" />
  <title>js的插入排序</title>
  <meta name="keywords" content="關(guān)鍵字列表" />
  <meta name="description" content="網(wǎng)頁(yè)描述" />
  <link rel="stylesheet" type="text/css" href="" />
  <style type="text/css"></style>
  <script type="text/javascript">
  //插入排序，參數(shù)是數(shù)組
  function insertSort(arr){
    //判斷參數(shù)的合法性
    if(toString.call(arr) !== '[object Array]'){
      return false;
    }
    //獲取數(shù)組的長(zhǎng)度
    var len = arr.length;
    if(len <= 1){
      return arr;//小于等于1不用排序
    }
    //i=1開始，留著0作為有序部分，也就是說(shuō)，外層循環(huán)獲取數(shù)組后面的元素，也就是上面所講的無(wú)序部分
    for(var i=1;i<len;i++){
    //j=i-1，就是獲取有序部分最后的一個(gè)元素作為對(duì)照，也就是有序部分
      for(var j=i-1;j>=0;j--){//注意，j--,就是從有序部分的后面元素開始和無(wú)序部分的元素作比較
        if(arr[j] > arr[j+1]){//第一個(gè)j+1也就是外層循環(huán)i，
          //互換元素，對(duì)前面數(shù)組進(jìn)行排序
          var temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp;
        }
      }
    }
    return arr;
  }
  //測(cè)試
  var ar = [9,3,8,5,2,7,0,6,1,4];
  alert(insertSort(ar));
  </script>
</head>
<body>
</body>
</html>

感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運(yùn)行工具：http://tools.jb51.net/code/HtmlJsRun測(cè)試上述代碼運(yùn)行效果。

PS：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：

在線動(dòng)畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過(guò)程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》

希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。

向AI問(wèn)一下細(xì)節(jié)

JS插入排序簡(jiǎn)單理解與實(shí)現(xiàn)方法分析

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽