検索
ホームページウェブフロントエンド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の進化:現在の傾向と将来の見通しJavaScriptの進化:現在の傾向と将来の見通しApr 10, 2025 am 09:33 AM

JavaScriptの最新トレンドには、TypeScriptの台頭、最新のフレームワークとライブラリの人気、WebAssemblyの適用が含まれます。将来の見通しは、より強力なタイプシステム、サーバー側のJavaScriptの開発、人工知能と機械学習の拡大、およびIoTおよびEDGEコンピューティングの可能性をカバーしています。

javascriptの分解:それが何をするのか、なぜそれが重要なのかjavascriptの分解:それが何をするのか、なぜそれが重要なのかApr 09, 2025 am 12:07 AM

JavaScriptは現代のWeb開発の基礎であり、その主な機能には、イベント駆動型のプログラミング、動的コンテンツ生成、非同期プログラミングが含まれます。 1)イベント駆動型プログラミングにより、Webページはユーザー操作に応じて動的に変更できます。 2)動的コンテンツ生成により、条件に応じてページコンテンツを調整できます。 3)非同期プログラミングにより、ユーザーインターフェイスがブロックされないようにします。 JavaScriptは、Webインタラクション、シングルページアプリケーション、サーバー側の開発で広く使用されており、ユーザーエクスペリエンスとクロスプラットフォーム開発の柔軟性を大幅に改善しています。

pythonまたはjavascriptの方がいいですか?pythonまたはjavascriptの方がいいですか?Apr 06, 2025 am 12:14 AM

Pythonはデータサイエンスや機械学習により適していますが、JavaScriptはフロントエンドとフルスタックの開発により適しています。 1. Pythonは、簡潔な構文とリッチライブラリエコシステムで知られており、データ分析とWeb開発に適しています。 2。JavaScriptは、フロントエンド開発の中核です。 node.jsはサーバー側のプログラミングをサポートしており、フルスタック開発に適しています。

JavaScriptをインストールするにはどうすればよいですか?JavaScriptをインストールするにはどうすればよいですか?Apr 05, 2025 am 12:16 AM

JavaScriptは、最新のブラウザにすでに組み込まれているため、インストールを必要としません。開始するには、テキストエディターとブラウザのみが必要です。 1)ブラウザ環境では、タグを介してHTMLファイルを埋め込んで実行します。 2)node.js環境では、node.jsをダウンロードしてインストールした後、コマンドラインを介してJavaScriptファイルを実行します。

クォーツでタスクが開始される前に通知を送信する方法は?クォーツでタスクが開始される前に通知を送信する方法は?Apr 04, 2025 pm 09:24 PM

Quartzタイマーを使用してタスクをスケジュールする場合、Quartzでタスク通知を事前に送信する方法、タスクの実行時間はCron式によって設定されます。今...

JavaScriptでは、コンストラクターのプロトタイプチェーンで関数のパラメーターを取得する方法は?JavaScriptでは、コンストラクターのプロトタイプチェーンで関数のパラメーターを取得する方法は?Apr 04, 2025 pm 09:21 PM

JavaScriptプログラミング、プロトタイプチェーンの関数パラメーターの理解と操作のJavaScriptのプロトタイプチェーンの関数のパラメーターを取得する方法は、一般的で重要なタスクです...

WeChat MiniプログラムWebViewでVUE.JSダイナミックスタイルの変位が失敗した理由は何ですか?WeChat MiniプログラムWebViewでVUE.JSダイナミックスタイルの変位が失敗した理由は何ですか?Apr 04, 2025 pm 09:18 PM

WeChatアプレットWeb-ViewでVue.jsを使用する動的スタイルの変位障害がvue.jsを使用している理由の分析...

TamperMonkeyで複数のリンクの同時GETリクエストを実装し、順番に戻る結果を決定する方法は?TamperMonkeyで複数のリンクの同時GETリクエストを実装し、順番に戻る結果を決定する方法は?Apr 04, 2025 pm 09:15 PM

複数のリンクの同時ゲットリクエストを作成し、結果を返すために順番に判断する方法は? TamperMonkeyスクリプトでは、複数のチェーンを使用する必要があることがよくあります...

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衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

SecLists

SecLists

SecLists は、セキュリティ テスターの究極の相棒です。これは、セキュリティ評価中に頻繁に使用されるさまざまな種類のリストを 1 か所にまとめたものです。 SecLists は、セキュリティ テスターが必要とする可能性のあるすべてのリストを便利に提供することで、セキュリティ テストをより効率的かつ生産的にするのに役立ちます。リストの種類には、ユーザー名、パスワード、URL、ファジング ペイロード、機密データ パターン、Web シェルなどが含まれます。テスターはこのリポジトリを新しいテスト マシンにプルするだけで、必要なあらゆる種類のリストにアクセスできるようになります。

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

AtomエディタMac版ダウンロード

AtomエディタMac版ダウンロード

最も人気のあるオープンソースエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい