ホームページ ウェブフロントエンド jsチュートリアル JSの一般的なソートアルゴリズムの詳細な説明

JSの一般的なソートアルゴリズムの詳細な説明

Jan 24, 2017 pm 01:47 PM
javascript 選別 アルゴリズム

こんな諺があります:

雷峰は雷峰塔を打ち倒し、Java は JavaScript を実装しました。

当時、私は Java を取り入れて人気者になりたくて、名前も JavaScript (元々は LiveScript として知られていました) に変えました。すでに明るく輝いています。ノード JS の出現により、JavaScript がフロントエンドとバックエンドの両方を引き継ぐことが可能になります。 Java は依然としてエンタープライズ ソフトウェア開発 (C/C + + 偉大な神々よ、どうか私を殴らないでください。 。 。 ) しかし、Web の世界では、JavaScript は比類のないものであり、トップの座を占めています。

しかし、従来のコンピューターアルゴリズムとデータ構造の分野では、ほとんどの専門的な教科書や書籍のデフォルト言語は Java または C/C+ です。 +。このことは、最近アルゴリズムとデータ構造の知識を補いたいと思っていた私にとって、JavaScript をデフォルト言語とするアルゴリズムの本を探していたため、少々問題を引き起こしました。オライリーの動物本シリーズに「データ構造とアルゴリズムの JavaScript 記述」という本があると知り、興奮して 2 日間かけてこの本を最初から最後まで読みました。これは、フロントエンド開発者にとっては優れたアルゴリズムの入門書ですが、大きな欠陥があります。つまり、私のような中途半端なプログラマでもすぐにわかるほど、明らかな小さな間違いがたくさんあるということです。一目見てわかります。もう 1 つの問題は、多くの重要なアルゴリズムとデータ構造の知識が本書では言及されていないことです。これらの問題は、末期の強迫性障害患者である私にとってはまったく耐えられません。そのため、同意できない場合は常に情報を探し、アルゴリズムを自分で要約することにしました。そこで、フィールドソートアルゴリズムの最も基礎的な知識のポイントからまとめていきます。

次のコードには、私自身では見つけられないバグやエラー、文法的な不規則性があるはずです。そのため、間違いを指摘していただければ幸いです。常に修正することによってのみ、長期的な進歩を達成することができます。 。


トップ 10 の古典的なアルゴリズム

JSの一般的なソートアルゴリズムの詳細な説明

用語の説明:

n: データスケール

k : 「バケツ」の数

In -place: 定数メモリを占有しますが、追加のメモリは占有しません

Out-place: 追加のメモリを占有します

安定性: ソート後の 2 つの等しいキー値の順序は、ソート前の順序と同じです


バブルソート

バブルソートは最も単純な並べ替えアルゴリズムの1つで、単語帳に載っているAbandonと同じ感覚を与えてくれます。一番馴染み深い。 。 。バブル ソートには別の最適化アルゴリズムがあります。これは、シーケンスの走査中に要素が交換されない場合にフラグを設定することで、シーケンスが正常であることを証明します。しかし、この改善はパフォーマンスの向上にはあまり役に立ちません。 。 。

いつが最も速いですか

入力データがすでに正の順序になっている場合(すでに正の順序になっていますが、バブルソートの用途は何ですか?)

いつが最も遅いですか

入力データがは逆順です (データを逆順に出力するには for ループを書くだけです。なぜバブル ソートを使用する必要があるのでしょうか。暇ですか...)コードの実装

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        //相邻元素两两对比
                var temp = arr[j+1];        //元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}
ログイン後にコピー

JSの一般的なソートアルゴリズムの詳細な説明

選択ソート

最も安定した並べ替えアルゴリズムの 1 つです。これは、どのようなデータが入力されるかに関係なく、時間計算量が O( n²) であるためです。 。 。したがって、使用する場合はデータサイズが小さいほど良いです。唯一の利点は、追加のメモリ空間を占有しないことです。

選択ソートアニメーションのデモ


JavaScriptコード実装

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     //寻找最小的数
                minIndex = j;                 //将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;}
ログイン後にコピー

JSの一般的なソートアルゴリズムの詳細な説明

挿入ソート

挿入ソート バブルソートと選択ソート、その後シンプルで大雑把ではありますが、その原理はポーカーをプレイしたことがある人であればすぐに理解できるはずなので、最も理解しやすいはずです。もちろん、ポーカーをプレイするときにカードをサイズに応じて並べ替えることはないと言うなら、おそらく、この世で挿入並べ替えアルゴリズムに興味を持たないでしょう。 。 。 バブルソートと同様に、挿入ソートにも分割半挿入と呼ばれる最適化アルゴリズムがあります。この種のアルゴリズムについては、怠け者の私が教科書に載っている古典的な格言を使用します。興味のある学生は授業後に自分で勉強してください。 。 。


挿入ソートアニメーションのデモ

JavaScript代码实现

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;}
ログイン後にコピー


希尔排序

希尔排序是插入排序的一种更高效率的实现。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法(第4版》的合著者Robert Sedgewick提出的。在这里,我就使用了这种方法。

JavaScript代码实现

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //动态定义间隔序列
        gap =gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;}
ログイン後にコピー


归并排序

作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

●自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第2种方法)

●自下而上的迭代

在《数据结构与算法JavaScript描述》中,作者给出了自下而上的迭代方法。但是对于递归法,作者却认为:

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。

说实话,我不太理解这句话。意思是JavaScript编译器内存太小,递归太深容易造成内存溢出吗?还望有大神能够指教。

和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(n log n)的时间复杂度。代价是需要额外的内存空间。

归并排序动图演示

JSの一般的なソートアルゴリズムの詳細な説明

归并排序JavaScript代码实现:

function mergeSort(arr) {  //采用自上而下的递归方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));}function merge(left, right){
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;}
ログイン後にコピー


快速排序

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高! 它是处理大数据最快的排序算法之一了。虽然Worst Case的时间复杂度达到了O(n²),但是人家就是优秀,在大多数情况下都比平均时间复杂度为O(n log n) 的排序算法表现要更好,可是这是为什么呢,我也不知道。。。好在我的强迫症又犯了,查了N多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案:

快速排序的最坏运行情况是O(n²),比如说顺序数列的快排。但它的平摊期望时间是O(n log n) ,且O(n log n)记号中隐含的常数因子很小,比复杂度稳定等于O(n log n)的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。

快速排序动图演示

JSの一般的なソートアルゴリズムの詳細な説明

快速排序JavaScript代码实现:

function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != &#39;number&#39; ? 0 : left,
        right = typeof right != &#39;number&#39; ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;}function partition(arr, left ,right) {     //分区操作
    var pivot = left,                      //设定基准值(pivot)
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }        
    }
    swap(arr, pivot, index - 1);
    return index-1;}function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;}
ログイン後にコピー


堆排序

堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:

1.大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列

2.小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列

堆排序动图演示

JSの一般的なソートアルゴリズムの詳細な説明

堆排序JavaScript代码实现:

var len;    //因为声明的多个函数都需要数据长度,所以把len设置成为全局变量function buildMaxHeap(arr) {   //建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }}function heapify(arr, i) {     //堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;

    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }}function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;}function heapSort(arr) {
    buildMaxHeap(arr);

    for (var i = arr.length-1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;}
ログイン後にコピー


计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

计数排序动图演示


JSの一般的なソートアルゴリズムの詳細な説明

计数排序JavaScript代码实现:

function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue+1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;

    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }

    return arr;}
ログイン後にコピー


桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。

为了使桶排序更加高效,我们需要做到这两点:

1.在额外空间充足的情况下,尽量增大桶的数量

2.使用的映射函数能够将输入的N个数据均匀的分配到K个桶中

同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。

什么时候最快

当输入的数据可以均匀的分配到每一个桶中

什么时候最慢

当输入的数据被分配到了同一个桶中

桶排序JavaScript代码实现:

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                //输入数据的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                //输入数据的最大值
      }
    }

    //桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            //设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;   
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

    //利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      //对每个桶进行排序,这里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                      
        }
    }

    return arr;}
ログイン後にコピー


基数排序

基数排序有两种方法

1.MSD 从高位开始进行排序

2.LSD 从低位开始进行排序

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:

●基数排序:根据键值的每位数字来分配桶

●计数排序:每个桶只存储单一键值

●桶排序:每个桶存储一定范围的数值

LSD基数排序动图演示:

JSの一般的なソートアルゴリズムの詳細な説明

基数排序JavaScript代码实现:

//LSD Radix Sortvar counter = [];function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;}
ログイン後にコピー


写在最后

排序算法实在是博大精深,还有hin多hin多我没有总结到或者我自己还没弄明白的算法,仅仅是总结这十种排序算法都把我写哭了。。。

因此,以后如果我掌握了更多的排序姿势,我一定还会回来的!

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホット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ヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

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

SublimeText3 中国語版

SublimeText3 中国語版

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

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

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

CLIP-BEVFormer: BEVFormer 構造を明示的に監視して、ロングテール検出パフォーマンスを向上させます。 CLIP-BEVFormer: BEVFormer 構造を明示的に監視して、ロングテール検出パフォーマンスを向上させます。 Mar 26, 2024 pm 12:41 PM

上記および筆者の個人的な理解: 現在、自動運転システム全体において、認識モジュールが重要な役割を果たしている。道路を走行する自動運転車は、認識モジュールを通じてのみ正確な認識結果を得ることができる。下流の規制および制御モジュール自動運転システムでは、タイムリーかつ正確な判断と行動決定が行われます。現在、自動運転機能を備えた自動車には通常、サラウンドビューカメラセンサー、ライダーセンサー、ミリ波レーダーセンサーなどのさまざまなデータ情報センサーが搭載されており、さまざまなモダリティで情報を収集して正確な認識タスクを実現しています。純粋な視覚に基づく BEV 認識アルゴリズムは、ハードウェア コストが低く導入が容易であるため、業界で好まれており、その出力結果はさまざまな下流タスクに簡単に適用できます。

C++ での機械学習アルゴリズムの実装: 一般的な課題と解決策 C++ での機械学習アルゴリズムの実装: 一般的な課題と解決策 Jun 03, 2024 pm 01:25 PM

C++ の機械学習アルゴリズムが直面する一般的な課題には、メモリ管理、マルチスレッド、パフォーマンスの最適化、保守性などがあります。解決策には、スマート ポインター、最新のスレッド ライブラリ、SIMD 命令、サードパーティ ライブラリの使用、コーディング スタイル ガイドラインの遵守、自動化ツールの使用が含まれます。実践的な事例では、Eigen ライブラリを使用して線形回帰アルゴリズムを実装し、メモリを効果的に管理し、高性能の行列演算を使用する方法を示します。

C++sort 関数の基礎となる原則とアルゴリズムの選択を調べる C++sort 関数の基礎となる原則とアルゴリズムの選択を調べる Apr 02, 2024 pm 05:36 PM

C++sort 関数の最下層はマージ ソートを使用し、その複雑さは O(nlogn) で、クイック ソート、ヒープ ソート、安定したソートなど、さまざまなソート アルゴリズムの選択肢を提供します。

改良された検出アルゴリズム: 高解像度の光学式リモートセンシング画像でのターゲット検出用 改良された検出アルゴリズム: 高解像度の光学式リモートセンシング画像でのターゲット検出用 Jun 06, 2024 pm 12:33 PM

01 今後の概要 現時点では、検出効率と検出結果の適切なバランスを実現することが困難です。我々は、光学リモートセンシング画像におけるターゲット検出ネットワークの効果を向上させるために、多層特徴ピラミッド、マルチ検出ヘッド戦略、およびハイブリッドアテンションモジュールを使用して、高解像度光学リモートセンシング画像におけるターゲット検出のための強化されたYOLOv5アルゴリズムを開発しました。 SIMD データセットによると、新しいアルゴリズムの mAP は YOLOv5 より 2.2%、YOLOX より 8.48% 優れており、検出結果と速度のバランスがより優れています。 02 背景と動機 リモート センシング技術の急速な発展に伴い、航空機、自動車、建物など、地表上の多くの物体を記述するために高解像度の光学式リモート センシング画像が使用されています。リモートセンシング画像の判読における物体検出

人工知能は犯罪を予測できるのか? CrimeGPT の機能を調べる 人工知能は犯罪を予測できるのか? CrimeGPT の機能を調べる Mar 22, 2024 pm 10:10 PM

人工知能 (AI) と法執行機関の融合により、犯罪の予防と検出の新たな可能性が開かれます。人工知能の予測機能は、犯罪行為を予測するためにCrimeGPT (犯罪予測技術) などのシステムで広く使用されています。この記事では、犯罪予測における人工知能の可能性、その現在の応用、人工知能が直面する課題、およびこの技術の倫理的影響について考察します。人工知能と犯罪予測: 基本 CrimeGPT は、機械学習アルゴリズムを使用して大規模なデータセットを分析し、犯罪がいつどこで発生する可能性があるかを予測できるパターンを特定します。これらのデータセットには、過去の犯罪統計、人口統計情報、経済指標、気象パターンなどが含まれます。人間のアナリストが見逃す可能性のある傾向を特定することで、人工知能は法執行機関に力を与えることができます

WPS スコアを並べ替える方法 WPS スコアを並べ替える方法 Mar 20, 2024 am 11:28 AM

私たちの仕事では、wps ソフトウェアをよく使用します。wps ソフトウェアではデータを処理する方法がたくさんあり、機能も非常に強力です。平均値や要約などを求める関数をよく使用します。統計データに使用できるメソッドは、WPS ソフトウェア ライブラリで誰でも利用できるように用意されています。以下では、WPS でスコアをソートする手順を紹介します。これを読んだ後、経験から学ぶことができます。 1. まず、ランク付けする必要があるテーブルを開きます。以下に示すように。 2. 次に、数式 =rank(B2, B2: B5, 0) を入力します。必ず 0 を入力してください。以下に示すように。 3. 数式を入力した後、コンピュータのキーボードの F4 キーを押すと、相対参照が絶対参照に変更されます。

エクセルで並べ替える方法 エクセルで並べ替える方法 Mar 05, 2024 pm 04:12 PM

Excel での並べ替え方法: 1. 単一列の並べ替え; 2. 複数列の並べ替え; 3. カスタム並べ替え。詳細な紹介: 1. 単一列の並べ替えは、最も一般的な並べ替え方法です。選択した列に従って並べ替えられます。2. 複数列の並べ替えは、複数の列でデータを並べ替えることを指します。通常は、最初に特定の列に従って並べ替えられます。 of、別の列で並べ替える; 3. カスタム並べ替え、ユーザーが独自のニーズに応じて並べ替え順序を定義できるようにします。

データ統計を容易にするために WPS テーブルをソートする方法 データ統計を容易にするために WPS テーブルをソートする方法 Mar 20, 2024 pm 04:31 PM

WPS は、テキスト編集、データ テーブル、PPT プレゼンテーション、PDF 形式、フローチャート、その他の機能を含む、非常に完成度の高いオフィス ソフトウェアです。その中でも私たちがよく使うのはテキスト、表、デモであり、私たちにとって最も馴染みのあるものでもあります。私たちの研究では、データ統計を作成するために WPS テーブルを使用することがあります。たとえば、学校は各生徒の得点を数えます。非常に多くの生徒の得点を手動で並べ替える必要がある場合、本当に頭の痛い作業になります。実際、WPS テーブルにはこの問題を解決する並べ替え機能があるため、心配する必要はありません。次に、WPS を並べ替える方法を一緒に学びましょう。方法のステップ: ステップ 1: まず、並べ替える必要がある WPS テーブルを開く必要があります。

See all articles