検索
ホームページウェブフロントエンドjsチュートリアルJavaScript でのいくつかのソート アルゴリズムの簡単な実装_基礎知識

ソートアルゴリズムの実装

私の JS スキルは低いので、JAVA と C に似た方法を使用して JavaScript のソート アルゴリズムを作成します。

ここではアルゴリズムの原則については説明しません。コードの実装についてのみ説明します。バグがある可能性があります。ガイダンスとしてブログにコメントしてください。
挿入ソート

Insertion-Sort のアルゴリズムの説明は、シンプルで直感的な並べ替えアルゴリズムです。ソートされていないデータの場合は、ソートされたシーケンスを後ろから前にスキャンし、対応する位置を見つけて挿入します。挿入ソートの実装では、通常、インプレース ソート (つまり、O(1) 個の余分なスペースのみを使用するソート) が使用されます。そのため、後ろから前へのスキャン プロセス中に、繰り返し、徐々にシフトする必要があります。要素を後方にソートし、最新の要素の挿入スペースを提供します。

実装コードは次のとおりです:

function insertSort(arr) {
  if (!arr) return;
  var len = arr.length;
  if (len == 0 || len == 1) return;

  for (var i = 1, len = arr.length; i < len; i ++) {
    var stand = arr[i];
    for (var j = i - 1; j >= 0; j --) {
      if (arr[j] > stand) {
        arr[j + 1] = arr[j];
      } else {
        arr[j + 1] = stand;
        break;
      }
    }
  }

  return arr;
}

時間計算量は O(n^2)

もちろん、検索と置換の位置アルゴリズムを二分探索に変更するなど、このアルゴリズムを最適化する余地はあります。
バブルソート

古典的なソートアルゴリズム、バブルソートとなると心が痛む。私は学部時代にバブルソートアルゴリズムの改良に関する必須論文を書きましたが、その結果、論文を書き終えた後、バブルソートアルゴリズムを完全に実装することができませんでした。

  if (!arr) return;
  var len = arr.length;
  if (len == 0 || len == 1) return;

  for (var i = 0; i < len; i ++) {
    for (var j = 0; j < len - i - 1; j ++) {
      if (arr[j] > arr[j + 1]) {
        var tmp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = tmp;
      }
    }
  }

  return arr;
}


時間計算量は次のとおりです: O(n^2)
クイックソート

非常に古典的な並べ替えアルゴリズム。並べ替えプロセスは主に 3 つのステップに分かれています。

  1. シーケンスから「ピボット」と呼ばれる要素を選択します。
  2. ベースライン値より小さいすべての要素がベースラインの前に配置され、ベースライン値より大きいすべての要素がベースラインの後ろに配置されるようにシーケンスを並べ替えます (同じ番号をどちらの側にも配置できます)。このパーティションが終了すると、塩基はシーケンスの途中になります。これはパーティション操作と呼ばれます。
  3. 基本値より小さい要素の部分配列と基本値より大きい要素の部分配列を再帰的に並べ替えます。

実装コードは次のとおりです:

function quickSort(arr, bt, ed) {
  if (bt < ed) {
    var pivot = findPartition(arr, bt, ed);
    quickSort(arr, bt, pivot - 1);
    quickSort(arr, pivot + 1, ed);
  }
}

function findPartition(arr, bt, ed) {
  var stand = arr[bt];

  while (bt < ed) {
    while (bt < ed && arr[ed] >= stand) {
      ed --;
    }
    if (bt < ed) {
      arr[bt ++] = arr[ed];
    }
    while (bt < ed && arr[bt] <= stand) {
      bt ++;
    }
    if (bt < ed) {
      arr[ed --] = arr[bt]; 
    }
  }

  arr[bt] = stand;
  return bt;
}


時間計算量は O(nlogn) です。
並べ替えを結合

これは非常に古典的な並べ替えアルゴリズムでもあり、js を学ぶ機会を利用して古典的な並べ替えアルゴリズムを復習しました。マージ ソートのアイデアについては、私のブログ「マージ ソート」を参照してください。ここではjsの実装のみを書きます。

function mergeSort(arr, bt, ed) {
  if (bt < ed) {
    var mid = bt + parseInt((ed - bt) / 2);
    mergeSort(arr, bt, mid);
    mergeSort(arr, mid + 1, ed);
    mergeArray(arr, bt, mid, ed);    
  }
}

function mergeArray(arr, bt, mid, ed) {
  var mArr = [];
  var i = bt, j = mid + 1;
  while (i <= mid && j <= ed) {
    if (arr[i] <= arr[j]) {
      mArr.push(arr[i++]);
    } else {
      mArr.push(arr[j ++]);
    }
  }

  if (i <= mid) {
    mArr = mArr.concat(arr.slice(i, mid + 1));
  }

  if (j <= ed) {
    mArr = mArr.concat(arr.slice(j, ed + 1));
  }

  for (var h = 0; h < mArr.length; h ++) {
    arr[bt + h] = mArr[h];
  }
}


マージ ソートを作成するときに、もう 1 つの小さなエピソードがありました。js は自動的に切り上げることができなかったので、後で parseInt メソッドを使用しました。これは非常に魅力的でした。


声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
Python vs. JavaScript:開発者の比較分析Python vs. JavaScript:開発者の比較分析May 09, 2025 am 12:22 AM

PythonとJavaScriptの主な違いは、タイプシステムとアプリケーションシナリオです。 1。Pythonは、科学的コンピューティングとデータ分析に適した動的タイプを使用します。 2。JavaScriptは弱いタイプを採用し、フロントエンドとフルスタックの開発で広く使用されています。この2つは、非同期プログラミングとパフォーマンスの最適化に独自の利点があり、選択する際にプロジェクトの要件に従って決定する必要があります。

Python vs. JavaScript:ジョブに適したツールを選択するPython vs. JavaScript:ジョブに適したツールを選択するMay 08, 2025 am 12:10 AM

PythonまたはJavaScriptを選択するかどうかは、プロジェクトの種類によって異なります。1)データサイエンスおよび自動化タスクのPythonを選択します。 2)フロントエンドとフルスタック開発のためにJavaScriptを選択します。 Pythonは、データ処理と自動化における強力なライブラリに好まれていますが、JavaScriptはWebインタラクションとフルスタック開発の利点に不可欠です。

PythonとJavaScript:それぞれの強みを理解するPythonとJavaScript:それぞれの強みを理解するMay 06, 2025 am 12:15 AM

PythonとJavaScriptにはそれぞれ独自の利点があり、選択はプロジェクトのニーズと個人的な好みに依存します。 1. Pythonは、データサイエンスやバックエンド開発に適した簡潔な構文を備えた学習が簡単ですが、実行速度が遅くなっています。 2。JavaScriptはフロントエンド開発のいたるところにあり、強力な非同期プログラミング機能を備えています。 node.jsはフルスタックの開発に適していますが、構文は複雑でエラーが発生しやすい場合があります。

JavaScriptのコア:CまたはCの上に構築されていますか?JavaScriptのコア:CまたはCの上に構築されていますか?May 05, 2025 am 12:07 AM

javascriptisnotbuiltoncorc;それは、解釈されていることを解釈しました。

JavaScriptアプリケーション:フロントエンドからバックエンドまでJavaScriptアプリケーション:フロントエンドからバックエンドまでMay 04, 2025 am 12:12 AM

JavaScriptは、フロントエンドおよびバックエンド開発に使用できます。フロントエンドは、DOM操作を介してユーザーエクスペリエンスを強化し、バックエンドはnode.jsを介してサーバータスクを処理することを処理します。 1.フロントエンドの例:Webページテキストのコンテンツを変更します。 2。バックエンドの例:node.jsサーバーを作成します。

Python vs. Javascript:どの言語を学ぶべきですか?Python vs. Javascript:どの言語を学ぶべきですか?May 03, 2025 am 12:10 AM

PythonまたはJavaScriptの選択は、キャリア開発、学習曲線、エコシステムに基づいている必要があります。1)キャリア開発:Pythonはデータサイエンスとバックエンド開発に適していますが、JavaScriptはフロントエンドおよびフルスタック開発に適しています。 2)学習曲線:Python構文は簡潔で初心者に適しています。 JavaScriptの構文は柔軟です。 3)エコシステム:Pythonには豊富な科学コンピューティングライブラリがあり、JavaScriptには強力なフロントエンドフレームワークがあります。

JavaScriptフレームワーク:最新のWeb開発のパワーJavaScriptフレームワーク:最新のWeb開発のパワーMay 02, 2025 am 12:04 AM

JavaScriptフレームワークのパワーは、開発を簡素化し、ユーザーエクスペリエンスとアプリケーションのパフォーマンスを向上させることにあります。フレームワークを選択するときは、次のことを検討してください。1。プロジェクトのサイズと複雑さ、2。チームエクスペリエンス、3。エコシステムとコミュニティサポート。

JavaScript、C、およびブラウザの関係JavaScript、C、およびブラウザの関係May 01, 2025 am 12:06 AM

はじめに私はあなたがそれを奇妙に思うかもしれないことを知っています、JavaScript、C、およびブラウザは正確に何をしなければなりませんか?彼らは無関係であるように見えますが、実際、彼らは現代のウェブ開発において非常に重要な役割を果たしています。今日は、これら3つの間の密接なつながりについて説明します。この記事を通して、JavaScriptがブラウザでどのように実行されるか、ブラウザエンジンでのCの役割、およびそれらが協力してWebページのレンダリングと相互作用を駆動する方法を学びます。私たちは皆、JavaScriptとブラウザの関係を知っています。 JavaScriptは、フロントエンド開発のコア言語です。ブラウザで直接実行され、Webページが鮮明で興味深いものになります。なぜJavascrを疑問に思ったことがありますか

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 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

SublimeText3 Linux 新バージョン

SublimeText3 Linux 新バージョン

SublimeText3 Linux 最新バージョン

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強力な PHP 統合開発環境

EditPlus 中国語クラック版

EditPlus 中国語クラック版

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

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Eclipse を SAP NetWeaver アプリケーション サーバーと統合します。

MantisBT

MantisBT

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