mergSortによるいくつかの思考

4517 ワード

アルゴリズム先端 javascript

整理整頓と並べ替え、関連するものをいくつか整理します.
整理整頓については、もし何かを思い出す必要があれば、このリンクをクリックしてもいいです.中には様々な並べ替えのアニメのデモンストレーションと解説があります.
先に正規化された並べ替えを提供するjsコードの実装:

function mergeSort(arr, l, r) {
    if (l === r) {
        return;
    }
    let mid = Math.floor((r + l) / 2);
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}

function merge(arr, l, mid, r) {
    let leftIndex = l;
    let rightIndex = mid + 1;
    let helpArr = [];
    while(leftIndex <= mid && rightIndex <= r) {
        let leftItem = arr[leftIndex];
        let rightItem = arr[rightIndex];
        if (leftItem < rightItem) {
            helpArr.push(leftItem);
            leftIndex++;
        } else {
            helpArr.push(rightItem);
            rightIndex++;
        }
    }

    //           ，         ，         ，         
    while(leftIndex <= mid) {
        helpArr.push(arr[leftIndex]);
        leftIndex++;
    }

    while(rightIndex <= r) {
        helpArr.push(arr[rightIndex]);
        rightIndex++;
    }

    for (let index = 0; index < helpArr.length; index++) {
        arr[l] = helpArr[index];
        l++;
    }
}

どうやって並べ替えの時間の複雑さを推定しますか?
再帰的な書き方を採用していますので、再帰的な時間の複雑さをmaster式で推定します.以下は数式の詳細です.T(n)=a*T(n/b)+O(n^d)(1)、ロゴ(b,a)>d=>複雑度はO(n^log(b,a))(2)、log(b,a)=d=>複雑度はO(n^d*logn)(3)、log(b,a)複雑度はO(n)です.
aは再帰の回数を表し、mergSortで2回のmergSortを呼び出したので、帰順中a=2です.bはサンプルの数を表していますが、サンプルの量は2つに分かれていますので、アレイはleftとright部分に分けられます.O(n^d)は他の動作の時間複雑さを表しているので、正規化順序付けでは主にmergeという関数であり、これに相当して1回の配列遍歴を実行した場合、O(n)となります.a=2,b=2,d=1はマスター式により複雑度はnlognとなります.
泡の並べ替え、並べ替えを選択し、並べ替えを挿入する時間の複雑さはO(n^2)であることを知っています.サンプル量が大きい場合、n^2はnlognに比べて悪くなります.これはなぜですか?他の3つの並べ替えの中で、元素の間の比較を浪費することができます.例えば、泡の並べ替えが泡のように、1つの元素だけを位置づけて、次の泡がまた1つの元素だけを位置づけて、元素の間の相互比較を浪費します.整理整頓は分治によって、小さい時から大きい時まで比較的に合併する過程で、前回比較的に合併した元素は再び比較が発生しないで、整然とした区域が規模になって増加して、このように比較を浪費することはなくて、時間を節約しました.
行列の小と問題と行列の逆順を正規化して並べ替えて導入します.
和のテーマの要求によって、私達は考えてみます.並べ替えの過程で、leftとrightの部分を比較合併すると、実は左の部分が右の部分より小さい数が見つけられます.つまり、私達は簡単にmergeという函数の実行過程で配列の小さと速さを計算することができます.合併する時は左右二回とも秩序がありますので、一つの数字が右の一番目の数字より小さいなら、この数字は右の数字より小さいと分かります.
例えば、left=[1,2,3],right=[4,5,6]のように、1は4以下で、右側の3つの数はいずれも1より大きいと説明します.小さいとsumに等しいとsumは1*3を加算します.
コードを実現してください.

function smallSum(arr) {
    if (!arr || arr.length < 2) {
        return 0;
    }
    return mergeSort(arr, 0, arr.length - 1);
}

function mergeSort(arr, l, r) {
    if (l === r) {
        return 0;
    }
    let mid = Math.floor((l + r)/2);
    return mergeSort(arr, l, mid)
            + mergeSort(arr, mid + 1, r)
            + merge(arr, l, mid, r)
}

function merge(arr, l, mid, r) {
    let leftIndex = l;
    let rightIndex = mid + 1;
    let helpArr = [];
    let sum = 0;
    while(leftIndex <= mid && rightIndex <= r) {
        let leftItem = arr[leftIndex];
        let rightItem = arr[rightIndex];
        if (leftItem < rightItem) {
            /**            **/
            let tempSum = (r - rightIndex + 1) * leftItem
            sum += tempSum;
            /***************************/
            helpArr.push(leftItem);
            leftIndex++;
        } else {
            helpArr.push(rightItem);
            rightIndex++;
        }
    }

    /**        merge    **/

    return sum;
}

和ちゃんについては、どうやって使いますか?順を追って解いたら、逆の順で小と同じです.逆のだけです.下のコードを直接貼り付けます.

function inversePairs(arr) {
    if (!arr || arr.length < 2) {
        return [];
    }
    return mergeSort(arr, 0, arr.length - 1);
}

function mergeSort(arr, l, r) {
    if (l === r) {
        return [];
    }
    let mid = Math.floor((l + r)/2);
    return [
        ...mergeSort(arr, l, mid),
        ...mergeSort(arr, mid + 1, r),
        ...merge(arr, l, mid, r)
    ];
}

function merge(arr, l, mid, r) {
    let leftIndex = l;
    let rightIndex = mid + 1;
    let helpArr = [];
    let res = [];
    while(leftIndex <= mid && rightIndex <= r) {
        let leftItem = arr[leftIndex];
        let rightItem = arr[rightIndex];
        if (leftItem < rightItem) {
            helpArr.push(leftItem);
            leftIndex++;
        } else {
            /**            **/
            res.push([leftItem, rightItem]);
            /***************************/
            helpArr.push(rightItem);
            rightIndex++;
        }
    }

    /**        merge    **/

    return res;
}

以上は、この部分をまとめてまとめた回顧と回顧であり、自分の理解を深め、他の多くのところで運用できるようにしたい.もし正しくないところがあれば、皆さんから積極的に指摘してもらえます.

JavaScriptにおけるbreakとcontinueの違い