検索
ホームページウェブフロントエンドjsチュートリアルJS の一般的な基本アルゴリズムの紹介

JS の一般的な基本アルゴリズムの紹介

Oct 14, 2020 pm 05:33 PM
javascriptアルゴリズム

JS の一般的な基本アルゴリズムの紹介

アルゴリズムは、特定のデータ構造の入力を特定のデータ構造の出力に変換する単なる関数です。アルゴリズムの内部ロジックによって変換方法が決まります。

基本アルゴリズム

1. 並べ替え

1. バブルソート

//冒泡排序function bubbleSort(arr) {
  for(var i = 1, len = arr.length; i < len - 1; ++i) { 
     for(var j = 0; j <= len - i; ++j) {    
       if (arr[j] > arr[j + 1]) {     
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

2. 挿入ソート

//插入排序 过程就像你拿到一副扑克牌然后对它排序一样
function insertionSort(arr) {
  var n = arr.length;  
// 我们认为arr[0]已经被排序,所以i从1开始
  for (var i = 1; i < n; i++) {  
// 取出下一个新元素,在已排序的元素序列中从后向前扫描来与该新元素比较大小
    for (var j = i - 1; j >= 0; j--) {   
        if (arr[i] >= arr[j]) { // 若要从大到小排序,则将该行改为if (arr[i] <= arr[j])即可
        // 如果新元素arr[i] 大于等于 已排序的元素序列的arr[j],
        // 则将arr[i]插入到arr[j]的下一位置,保持序列从小到大的顺序
        arr.splice(j + 1, 0, arr.splice(i, 1)[0]);       
        // 由于序列是从小到大并从后向前扫描的,所以不必再比较下标小于j的值比arr[j]小的值,退出循环
        break;  
      } else if (j === 0) {        
      // arr[j]比已排序序列的元素都要小,将它插入到序列最前面
        arr.splice(j, 0, arr.splice(i, 1)[0]);
      }
    }
  } 
   return arr;
}

目的が昇順ソートである場合、シーケンスがすでに昇順でソートされていることが最善のケースです。順序の場合、比較する必要があるのは n-1 回だけであり、時間計算量は O(n) です。最悪のシナリオは、シーケンスが元々降順でソートされているため、n(n-1)/2 回の比較が必要となり、時間計算量が O(n^2) になることです。

したがって、平均すると、挿入ソートの時間計算量は O(n^2) になります。明らかに、電力レベルの時間の複雑さは、大量のデータがある状況には挿入ソートが適していないことを意味しますが、一般に、挿入ソートは少量のデータのソートに適しています。

3. クイックソート

//快速排序
function qSort(arr) {
  //声明并初始化左边的数组和右边的数组
  var left = [], right = [];
 //使用数组第一个元素作为基准值
  var base = arr[0];  
 //当数组长度只有1或者为空时,直接返回数组,不需要排序
  if(arr.length <= 1) return arr;  
 //进行遍历
  for(var i = 1, len = arr.length; i < len; i++) {
    if(arr[i] <= base) {    
    //如果小于基准值,push到左边的数组
      left.push(arr[i]);
    } else {    
    //如果大于基准值,push到右边的数组
      right.push(arr[i]);
    }
  }
  //递归并且合并数组元素
  return [...qSort(left), ...[base], ...qSort(right)];
    //return qSort(left).concat([base], qSort(right));}

補足:

このコードでは、次のことがわかります。左部分と右部分をピボットで分割し、その後、再帰的に左部分と右部分のピボットソートを続けることで、クイックソートのテキスト記述が実現されており、このアルゴリズムの実装には問題ありません。

ただし、この実装は非常に理解しやすいです。ただし、この実装にも改善の余地があり、関数内に一時データを格納する配列が左右 2 つ定義されていることがわかりました。再帰の数が増加するにつれて、より多くの一時データが定義および保存され、Ω(n) 個の追加の保存スペースが必要になります。

したがって、多くのアルゴリズムの紹介と同様に、インプレース パーティショニング バージョンはクイック ソートの実装に使用されます。

インプレース分割アルゴリズムの説明

  • シーケンスから「ピボット」と呼ばれる要素、つまり最初の要素の位置を選択します。配列のインデックスがインデックスとして使用されます。

  • # 配列を走査します。配列番号が基本値以下の場合、インデックス位置の番号を番号とインデックス 1

    # に置き換えます。
  • ##ベース値を現在のインデックス位置と交換します。
  • 上記の 3 つの手順を実行すると、ベース値が中央に配置され、その左側と右側に数字が配置されます。配列は、それぞれ基本値より小さいか大きくなります。このとき、その場で再帰的に分割することでソートされた配列を取得できます。

インプレース分割アルゴリズムの実装

// 交换数组元素位置
function swap(array, i, j) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
function partition(array, left, right) {
    var index = left;
    var pivot = array[right]; // 取最后一个数字当做基准值,这样方便遍历
    for (var i = left; i < right; i++) {
    if (array[i] <= pivot) {
        swap(array, index, i);
        index++;
     }
 }
     swap(array, right, index);
     return index;
     }
インプレース分割を複数回再帰的に行う必要があり、同時に追加のアドレスは必要ないためです。したがって、分割アルゴリズムを実装するときは、元の配列 array、走査する必要がある配列の左側の開始点、および走査する必要がある配列の右側の終点という 3 つのパラメータがあります。

最後に、次の再帰のためにソートされたインデックス値が返されます。このインデックスに対応する値は、インデックスの左側の配列要素より小さく、右側のすべての配列要素より大きくなければなりません。

基本的には、パーティショニング アルゴリズムをさらに最適化できます。

現場でパーティションのバージョンは高速です ソートの実装

function quickSort(array) {
    function swap(array, i, j) {
       var temp = array[i];
       array[i] = array[j];
       array[j] = temp;
     }
     function partition(array, left, right) {
        var index = left;
        var pivot = array[right]; // 取最后一个数字当做基准值,这样方便遍历
         for (var i = left; i < right; i++) {
             if (array[i] < pivot) {
                 swap(array, index, i);
                 index++;
           }
      }
      swap(array, right, index);        
      return index;
      }
      function sort(array, left, right) {    
          if (left > right) {        
              return;
        }        
        var storeIndex = partition(array, left, right);
        sort(array, left, storeIndex - 1);
        sort(array, storeIndex + 1, right);
    }

    sort(array, 0, array.length - 1);    
    return array;
}

2.文字列

1.回文文字列

//判断回文字符串
function palindrome(str) {
  var reg = /[\W\_]/g;  
  var str0 = str.toLowerCase().replace(reg, "");  
  var str1 = str0.split("").reverse().join("");  
  return str0 === str1;
}

2. 文字列を反転します

function reverseString(str) {
  return str.split("").reverse().join("");
}

3. 文字列内で最も多く出現する文字

function findMaxDuplicateChar(str) {
  var cnt = {}, //用来记录所有的字符的出现频次
      c = &#39;&#39;; //用来记录最大频次的字符
  for (var i = 0; i < str.length; i++) {
      var ci = str[i];    
      if (!cnt[ci]) {
      cnt[ci] = 1;
    } else {
      cnt[ci]++;
    }    
      if (c == &#39;&#39; || cnt[ci] > cnt[c]) {
      c = ci;
    }
  }  
      console.log(cnt)  return c;
}

3. アレイ

1. アレイの重複排除

//数组去重
function uniqueArray(arr) {
  var temp = [];  
  for (var i = 0; i < arr.length; i++) {
      if (temp.indexOf(arr[i]) == -1) {
      temp.push(arr[i]);
    }
  } 
      return temp;  
      //or
  return Array.from(new Set(arr));
}

4. 検索

1. 二分検索

//二分查找
function binary_search(arr, l, r, v) {
  if (l > r) {  
    return -1;
  }  
   var m = parseInt((l + r) / 2);  
   if (arr[m] == v) {  
     return m;
  } else if (arr[m] < v) {  
       return binary_search(arr, m+1, r, v);
  } else {   
        return binary_search(arr, l, m-1, v);
  }
}
前の挿入ソートに二分検索を適用して二分挿入ソートを形成すると、効率が向上するといわれています。しかし、テストしてみると、データ量が少なすぎたのか、あまり明らかなギャップは見つかりませんでした。 。自分で試すことができます ~ (たとえば、関数呼び出しの最初と最後に console.time('挿入ソートに時間がかかる') と console.timeEnd('挿入ソートに時間がかかる') を使用します)

5. ツリー検索/トラバーサル

1. 深さ優先検索

//深搜 非递归实现
function dfs(node) {
  var nodeList = [];  
  if (node) {  
    var stack = [];
    stack.push(node);   
     while(stack.length != 0) {   
        var item = stack.pop();
      nodeList.push(item);      
        var children = item.children;      
        for (var i = children.length-1; i >= 0; i--) {
             stack.push(children[i]);
      }
    }
  }  return nodeList;
} 
//深搜 递归实现
function dfs(node, nodeList) { 
 if (node) {
    nodeList.push(node);    
 var children = node.children;    
 for (var i = 0; i < children.length; i++) {
      dfs(children[i], nodeList);
    }
  }  
 return nodeList;
}

2. 幅- first search

//广搜 非递归实现
function bfs(node) {
    var nodeList = [];    
    if (node != null) {     
       var queue = [];
       queue.unshift(node);        
       while (queue.length != 0) {     
           var item = queue.shift();
            nodeList.push(item);            
           var children = item.children;           
            for (var i = 0; i < children.length; i++)
                queue.push(children[i]);
        }
    }    
        return nodeList;
}
//广搜 递归实现
var i=0;  
//自增标识符
function bfs(node, nodeList) {  
  if (node) {
      nodeList.push(node);      
  if (nodeList.length > 1) {
        bfs(node.nextElementSibling, nodeList); //搜索当前元素的下一个兄弟元素
      }
      node = nodeList[i++];
      bfs(node.firstElementChild, nodeList); //该层元素节点遍历完了,去找下一层的节点遍历
    }    return nodeList;
}

高次関数導出アルゴリズム

1. フィルター重複排除

フィルターも一般的に使用される操作。配列の特定の要素をフィルターで除外し、残りの要素を返します。このようにも理解できます フィルタのコールバック関数は、配列の各要素を処理します 処理結果が false を返した場合、フィルタ結果はその要素を削除します 真の場合は残ります

高い値を使用します-order function filter(). 重要なのは、「filter」関数を正しく実装することにあります。

実際、このフィルタリング関数には複数のパラメータ filter(function (element,index, self)) があり、次のようにフィルタを使用して重複を削除する方法を示しています。 #2、ソート並べ替えアルゴリズム

排序也是在程序中经常用到的算法。无论使用冒泡排序还是快速排序,排序的核心是比较两个元素的大小。如果是数字,我们可以直接比较,但如果是字符串或者两个对象呢?

直接比较数学上的大小是没有意义的,因此,比较的过程必须通过函数抽象出来。通常规定,对于两个元素x和y,如果认为x y,则返回1,这样,排序算法就不用关心具体的比较过程,而是根据比较结果直接排序。

值得注意的例子:

// 看上去正常的结果:
[&#39;Google&#39;, &#39;Apple&#39;, &#39;Microsoft&#39;].sort(); // [&#39;Apple&#39;, &#39;Google&#39;, &#39;Microsoft&#39;];
// apple排在了最后:
[&#39;Google&#39;, &#39;apple&#39;, &#39;Microsoft&#39;].sort(); // [&#39;Google&#39;, &#39;Microsoft", &#39;apple&#39;]
// 无法理解的结果:
[10, 20, 1, 2].sort(); // [1, 10, 2, 20]

解释原因

第二个排序把apple排在了最后,是因为字符串根据ASCII码进行排序,而小写字母a的ASCII码在大写字母之后。

第三个排序结果,简单的数字排序都能错。

这是因为Array的sort()方法默认把所有元素先转换为String再排序,结果’10’排在了’2’的前面,因为字符’1’比字符’2’的ASCII码小。

因此我们把结合这个原理:

var arr = [10, 20, 1, 2];
    arr.sort(function (x, y) {    
    if (x < y) {        
        return -1;
        }    
            if (x > y) {         
               return 1;
        }        return 0;
    });   
     console.log(arr); // [1, 2, 10, 20]

上面的代码解读一下:传入x,y,如果xy,返回-1,x后面排,如果x=y,无所谓谁排谁前面。

还有一个,sort()方法会直接对Array进行修改,它返回的结果仍是当前Array,一个例子:

var a1 = [&#39;B&#39;, &#39;A&#39;, &#39;C&#39;];var a2 = a1.sort();
    a1; // [&#39;A&#39;, &#39;B&#39;, &#39;C&#39;]
    a2; // [&#39;A&#39;, &#39;B&#39;, &#39;C&#39;]
    a1 === a2; // true, a1和a2是同一对象

相关免费学习推荐:js视频教程

以上がJS の一般的な基本アルゴリズムの紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明
この記事はOSCHINAで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。
JavaScriptの役割:WebをインタラクティブでダイナミックにするJavaScriptの役割:WebをインタラクティブでダイナミックにするApr 24, 2025 am 12:12 AM

JavaScriptは、Webページのインタラクティブ性とダイナミズムを向上させるため、現代のWebサイトの中心にあります。 1)ページを更新せずにコンテンツを変更できます。2)Domapiを介してWebページを操作する、3)アニメーションやドラッグアンドドロップなどの複雑なインタラクティブ効果、4)ユーザーエクスペリエンスを改善するためのパフォーマンスとベストプラクティスを最適化します。

CおよびJavaScript:接続が説明しましたCおよびJavaScript:接続が説明しましたApr 23, 2025 am 12:07 AM

CおよびJavaScriptは、WebAssemblyを介して相互運用性を実現します。 1)CコードはWebAssemblyモジュールにコンパイルされ、JavaScript環境に導入され、コンピューティングパワーが強化されます。 2)ゲーム開発では、Cは物理エンジンとグラフィックスレンダリングを処理し、JavaScriptはゲームロジックとユーザーインターフェイスを担当します。

Webサイトからアプリまで:JavaScriptの多様なアプリケーションWebサイトからアプリまで:JavaScriptの多様なアプリケーションApr 22, 2025 am 12:02 AM

JavaScriptは、Webサイト、モバイルアプリケーション、デスクトップアプリケーション、サーバー側のプログラミングで広く使用されています。 1)Webサイト開発では、JavaScriptはHTMLおよびCSSと一緒にDOMを運用して、JQueryやReactなどのフレームワークをサポートします。 2)ReactNativeおよびIonicを通じて、JavaScriptはクロスプラットフォームモバイルアプリケーションを開発するために使用されます。 3)電子フレームワークにより、JavaScriptはデスクトップアプリケーションを構築できます。 4)node.jsを使用すると、JavaScriptがサーバー側で実行され、高い並行リクエストをサポートします。

Python vs. JavaScript:ユースケースとアプリケーションと比較されますPython vs. JavaScript:ユースケースとアプリケーションと比較されますApr 21, 2025 am 12:01 AM

Pythonはデータサイエンスと自動化により適していますが、JavaScriptはフロントエンドとフルスタックの開発により適しています。 1. Pythonは、データ処理とモデリングのためにNumpyやPandasなどのライブラリを使用して、データサイエンスと機械学習でうまく機能します。 2。Pythonは、自動化とスクリプトにおいて簡潔で効率的です。 3. JavaScriptはフロントエンド開発に不可欠であり、動的なWebページと単一ページアプリケーションの構築に使用されます。 4. JavaScriptは、node.jsを通じてバックエンド開発において役割を果たし、フルスタック開発をサポートします。

JavaScript通訳者とコンパイラにおけるC/Cの役割JavaScript通訳者とコンパイラにおけるC/Cの役割Apr 20, 2025 am 12:01 AM

CとCは、主に通訳者とJITコンパイラを実装するために使用されるJavaScriptエンジンで重要な役割を果たします。 1)cは、JavaScriptソースコードを解析し、抽象的な構文ツリーを生成するために使用されます。 2)Cは、Bytecodeの生成と実行を担当します。 3)Cは、JITコンパイラを実装し、実行時にホットスポットコードを最適化およびコンパイルし、JavaScriptの実行効率を大幅に改善します。

JavaScript in Action:実際の例とプロジェクトJavaScript in Action:実際の例とプロジェクトApr 19, 2025 am 12:13 AM

現実世界でのJavaScriptのアプリケーションには、フロントエンドとバックエンドの開発が含まれます。 1)DOM操作とイベント処理を含むTODOリストアプリケーションを構築して、フロントエンドアプリケーションを表示します。 2)node.jsを介してRestfulapiを構築し、バックエンドアプリケーションをデモンストレーションします。

JavaScriptとWeb:コア機能とユースケースJavaScriptとWeb:コア機能とユースケースApr 18, 2025 am 12:19 AM

Web開発におけるJavaScriptの主な用途には、クライアントの相互作用、フォーム検証、非同期通信が含まれます。 1)DOM操作による動的なコンテンツの更新とユーザーインタラクション。 2)ユーザーエクスペリエンスを改善するためにデータを提出する前に、クライアントの検証が実行されます。 3)サーバーとのリフレッシュレス通信は、AJAXテクノロジーを通じて達成されます。

JavaScriptエンジンの理解:実装の詳細JavaScriptエンジンの理解:実装の詳細Apr 17, 2025 am 12:05 AM

JavaScriptエンジンが内部的にどのように機能するかを理解することは、開発者にとってより効率的なコードの作成とパフォーマンスのボトルネックと最適化戦略の理解に役立つためです。 1)エンジンのワークフローには、3つの段階が含まれます。解析、コンパイル、実行。 2)実行プロセス中、エンジンはインラインキャッシュや非表示クラスなどの動的最適化を実行します。 3)ベストプラクティスには、グローバル変数の避け、ループの最適化、constとletsの使用、閉鎖の過度の使用の回避が含まれます。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

MantisBT

MantisBT

Mantis は、製品の欠陥追跡を支援するために設計された、導入が簡単な Web ベースの欠陥追跡ツールです。 PHP、MySQL、Web サーバーが必要です。デモおよびホスティング サービスをチェックしてください。

EditPlus 中国語クラック版

EditPlus 中国語クラック版

サイズが小さく、構文の強調表示、コード プロンプト機能はサポートされていません

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強力な PHP 統合開発環境

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser は、オンライン試験を安全に受験するための安全なブラウザ環境です。このソフトウェアは、あらゆるコンピュータを安全なワークステーションに変えます。あらゆるユーティリティへのアクセスを制御し、学生が無許可のリソースを使用するのを防ぎます。

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)