<fieldset id="i6ea2"></fieldset>

<del id="i6ea2"></del>

<strike id="i6ea2"></strike>

<fieldset id="i6ea2"></fieldset>

javascript數據結構與算法 --- 高級排序算法

qianfeng 發布于2019-08-26 11:34 / 1853人閱讀

摘要：高級排序算法總結希爾排序間隔序列可以動態定義，不過對于大部分的實際應用場景，算法要用到的間隔序列可以提前定義好有一些公開定義的間隔序列，使用它們會得到不同的結果。

高級排序算法總結

希爾排序

    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可以動態定義，不過對于大部分的實際應用場景，算法要用到的間隔序列可以提前定義好,有一些公開定義的間隔序列，使用它們會得到不同的結果。例如Marcin Ciura 在2001 的論文“Best Increments for theAverage Case of Shell Sort”中的間隔序列[701, 301, 132, 57, 23, 10, 4, 1],下一節將介紹具有動態間隔序列的希爾排序.

動態間隔序列希爾排序

    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 定義了一個   shellsort() 函數，在這個函數中可以通過一個公式來對希爾排序用到的間隔序列進行動態計算。Sedgewick 的算法是通過上面的代碼片段來決定初始間隔值的,并添加到外層 for 循環.

歸并排序

    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));
    }

GPU云服務器云服務器算法與數據結構數據結構與算法排序算法圖解排序算法總結

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

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

javascript數據結構與算法 --- 基本排序算法

摘要：基本排序算法總結前言隨著的興起將推向的一個前所未有的高度作為為建立高性能的服務端而創建的運行平臺隨著時間的推移和生態鏈的完善已經不再局部于服務端包括前端后端桌面這篇文章介紹的傳統的散打排序方法并用實現其功能如有需要可以對其封裝在隨后會介紹高基本排序算法總結前言隨著node的興起, 將javascript推向的一個前所未有的高度, node作為為建立高性能的服務端而創建的js運行平...

wangdai 2019-08-26 11:33 評論0 收藏0
javascript實現排序算法

摘要：高級排序算法有希爾排序歸并排序快速排序。冒泡排序首先聲明，這是最慢的排序算法之一，但是也是最容易實現的排序算法。穩定性冒泡排序為一種穩定排序。快速排序快速排序是出力大數據集最快的排序算法之一。簡介對計算機中存儲的數據執行的兩種最常見的操作是排序和檢索，也是面試經常會被問到的一個知識點，本文將整理數據排序的基本算法和高級算法。其中基本排序算法有：冒泡排序、選擇排序、插入排序。高級排序...

xiangzhihong 2019-08-22 10:39 評論0 收藏0
Nicolas講算法：Computer Science in JavaScript

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

codergarden 2019-08-19 17:30 評論0 收藏0
JavaScript數據結構和算法

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

EastWoodYang 2019-08-21 16:23 評論0 收藏0
前端排序算法總結；前端面試題2.0；JavaScript異步編程

摘要：與異步編程按照維基百科上的解釋獨立于主控制流之外發生的事件就叫做異步。因為的存在，至少在被標準化的那一刻起，就支持異步編程了。然而異步編程真正發展壯大，的流行功不可沒。在握手過程中，端點交換認證和密鑰以建立或恢復安全會話。 1、前端排序算法總結排序算法可能是你學編程第一個學習的算法，還記得冒泡嗎？當然，排序和查找兩類算法是面試的熱門選項。如果你是一個會寫快排的程序猿，面試官在比較...

aaron 2019-08-01 17:38 評論0 收藏0