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

資訊專欄INFORMATION COLUMN

javascript數(shù)據(jù)結(jié)構(gòu)與算法 --- 高級(jí)排序算法

qianfeng / 1857人閱讀

摘要：高級(jí)排序算法總結(jié)希爾排序間隔序列可以動(dòng)態(tài)定義，不過對(duì)于大部分的實(shí)際應(yīng)用場景，算法要用到的間隔序列可以提前定義好有一些公開定義的間隔序列，使用它們會(huì)得到不同的結(jié)果。

高級(jí)排序算法總結(jié)

希爾排序

    function shellsort(array, gaps) {
      for (var g = 0; g < gaps.length; g++) {
        for (var i = gaps[g]; i < array.length; i++) {
          var temp = array[i];
          for (var j = i; (j >= gaps[g]) && (temp < array[j-gaps[g]]);j -= gaps[g]) {
            array[j] = array[j - gaps[g]];
          }
          array[j] = temp;
        }
        console.log(array);
      }
    }
間隔序列 gaps可以動(dòng)態(tài)定義，不過對(duì)于大部分的實(shí)際應(yīng)用場景，算法要用到的間隔序列可以提前定義好,有一些公開定義的間隔序列，使用它們會(huì)得到不同的結(jié)果。例如Marcin Ciura 在2001 的論文“Best Increments for theAverage Case of Shell Sort”中的間隔序列[701, 301, 132, 57, 23, 10, 4, 1],下一節(jié)將介紹具有動(dòng)態(tài)間隔序列的希爾排序.

動(dòng)態(tài)間隔序列希爾排序

    function dynOrdShellsort(array) {
      var N = array.length;
      var h = 1;
      while (h < N/3) {h = 3 * h + 1;
      }
      while (h >= 1) {
        for (var i = h; i < N; i++) {
          for (var j = i; j >= h && array[j] < array[j-h]; j -= h) {
            // swap(array, j, j-h);
            [array[j], array[j-h]] = [array[j-h], array[j]];
          }
        }h = (h-1)/3;
      }
    }
在《算法（第 4 版）》（人郵版）的合著者 Robert Sedgewick 定義了一個(gè)   shellsort() 函數(shù)，在這個(gè)函數(shù)中可以通過一個(gè)公式來對(duì)希爾排序用到的間隔序列進(jìn)行動(dòng)態(tài)計(jì)算。Sedgewick 的算法是通過上面的代碼片段來決定初始間隔值的,并添加到外層 for 循環(huán).

歸并排序

    let mergeSort = (function () {
      function mergeSort(arr) {
        if (arr.length < 2) {
          return;
        }
        var step = 1;
        var left, right;
        while (step < arr.length) {
          left = 0;
          right = step;
          while (right + step <= arr.length) {
            mergeArrays(arr, left, left+step, right, right+step);
            left = right + step;
            right = left + step;
          }
          if (right < arr.length) {
            mergeArrays(arr, left, left+step, right, arr.length);
          }
          step *= 2;
        }
      }
      function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
        var rightArr = new Array(stopRight - startRight + 1);
        var leftArr = new Array(stopLeft - startLeft + 1);
        k = startRight;
        for (var i = 0; i < (rightArr.length-1); ++i) {
          rightArr[i] = arr[k];
          ++k;
        }
        k = startLeft;
        for (var i = 0; i < (leftArr.length-1); ++i) {
          leftArr[i] = arr[k];
          ++k;
        }
        rightArr[rightArr.length-1] = Infinity; // 哨兵值
        leftArr[leftArr.length-1] = Infinity; // 哨兵值
        var m = 0;
        var n = 0;
        for (var k = startLeft; k < stopRight; ++k) {
          if (leftArr[m] <= rightArr[n]) {
            arr[k] = leftArr[m];
            m++;
          }
          else {
            arr[k] = rightArr[n];
            n++;
          }
        }
        // console.log("left array - ", leftArr);
        // console.log("right array - ", rightArr);
      }
      return mergeSort;
    })()

快速排序

    function qSort(arr){
      if (arr.length == 0) {
        return [];
      }
      var left = [];
      var right = [];
      var pivot = arr[0];
      for (var i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
          left.push(arr[i]);
        } else {
          right.push(arr[i]);
        }
      }
      return qSort(left).concat(pivot, qSort(right));
    }

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

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

相關(guān)文章

  • javascript數(shù)據(jù)結(jié)構(gòu)與算法 --- 基本排序算法

    摘要：基本排序算法總結(jié)前言隨著的興起將推向的一個(gè)前所未有的高度作為為建立高性能的服務(wù)端而創(chuàng)建的運(yùn)行平臺(tái)隨著時(shí)間的推移和生態(tài)鏈的完善已經(jīng)不再局部于服務(wù)端包括前端后端桌面這篇文章介紹的傳統(tǒng)的散打排序方法并用實(shí)現(xiàn)其功能如有需要可以對(duì)其封裝在隨后會(huì)介紹高 基本排序算法總結(jié) 前言 隨著node的興起, 將javascript推向的一個(gè)前所未有的高度, node作為為建立高性能的服務(wù)端而創(chuàng)建的js運(yùn)行平...

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

  • javascript實(shí)現(xiàn)排序算法

    摘要：高級(jí)排序算法有希爾排序歸并排序快速排序。冒泡排序首先聲明，這是最慢的排序算法之一，但是也是最容易實(shí)現(xiàn)的排序算法。穩(wěn)定性冒泡排序?yàn)橐环N穩(wěn)定排序?？焖倥判蚩焖倥判蚴浅隽Υ髷?shù)據(jù)集最快的排序算法之一。 簡介 對(duì)計(jì)算機(jī)中存儲(chǔ)的數(shù)據(jù)執(zhí)行的兩種最常見的操作是排序和檢索，也是面試經(jīng)常會(huì)被問到的一個(gè)知識(shí)點(diǎn)，本文將整理數(shù)據(jù)排序的基本算法和高級(jí)算法。其中基本排序算法有：冒泡排序、選擇排序、插入排序。高級(jí)排序...

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

  • Nicolas講算法：Computer Science in JavaScript

    摘要：使用來描述算法和數(shù)據(jù)結(jié)構(gòu)的教程很少，目前市面上用描述算法和數(shù)據(jù)結(jié)構(gòu)的書屈指可數(shù)，并且就我看過的那本而言我只看過數(shù)據(jù)結(jié)構(gòu)與算法語言描述質(zhì)量實(shí)在堪憂。 使用JavaScript來描述算法和數(shù)據(jù)結(jié)構(gòu)的教程很少， 目前市面上用JS描述算法和數(shù)據(jù)結(jié)構(gòu)的書屈指可數(shù)，并且就我看過的那本而言（我只看過《數(shù)據(jù)結(jié)構(gòu)與算法 JavaScript 語言描述》）質(zhì)量實(shí)在堪憂。碰巧有次看到Nicolas博客中的C...

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

  • JavaScript數(shù)據(jù)結(jié)構(gòu)和算法

    摘要：棧被稱為一種后入先出的數(shù)據(jù)結(jié)構(gòu)。散列使用的數(shù)據(jù)結(jié)構(gòu)叫做散列表。這些操作需要求助于其他數(shù)據(jù)結(jié)構(gòu)，比如下面介紹的二叉查找樹。 前言 在過去的幾年中，得益于Node.js的興起，JavaScript越來越廣泛地用于服務(wù)器端編程。鑒于JavaScript語言已經(jīng)走出了瀏覽器，程序員發(fā)現(xiàn)他們需要更多傳統(tǒng)語言（比如C++和Java）提供的工具。這些工具包括傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)（如鏈表，棧，隊(duì)列，圖等），...

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

  • 前端排序算法總結(jié)；前端面試題2.0；JavaScript異步編程

    摘要：與異步編程按照維基百科上的解釋獨(dú)立于主控制流之外發(fā)生的事件就叫做異步。因?yàn)榈拇嬖?，至少在被?biāo)準(zhǔn)化的那一刻起，就支持異步編程了。然而異步編程真正發(fā)展壯大，的流行功不可沒。在握手過程中，端點(diǎn)交換認(rèn)證和密鑰以建立或恢復(fù)安全會(huì)話。 1、前端 排序算法總結(jié) 排序算法可能是你學(xué)編程第一個(gè)學(xué)習(xí)的算法，還記得冒泡嗎？ 當(dāng)然，排序和查找兩類算法是面試的熱門選項(xiàng)。如果你是一個(gè)會(huì)寫快排的程序猿，面試官在比較...

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

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

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<