jsの基本アルゴリズム：バブルソート、二分探索-jsチュートリアル-php.cn

jsの基本アルゴリズム：バブルソート、二分探索

高洛峰

リリース： 2016-10-08 17:51:06

オリジナル

1380 人が閲覧しました

知識の拡張:

時間計算量: アルゴリズムの時間計算量は、アルゴリズムの実行時間を記述する関数です。時間の複雑さが低いほど、効率は高くなります。

自己理解: アルゴリズムの時間計算量は、それを n 回実行すると、時間計算量は O(n) になります。

1. バブルソート

分析: 1. 2 つの隣接する要素を比較し、前者の要素が後者の要素より大きい場合、位置を交換します。

2. 最初のラウンドでは、最後の要素が最大の要素でなければなりません。

3. 手順1に従って、隣接する2つの要素を比較します。この時点では、最後の要素がすでに最大であるため、最後の要素を比較する必要はありません。

function sort(elements){
 for(var i=0;i<elements.length-1;i++){
  for(var j=0;j<elements.length-i-1;j++){
   if(elements[j]>elements[j+1]){
    var swap=elements[j];
    elements[j]=elements[j+1];
    elements[j+1]=swap;
   }
  }
 }
}
 
var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log(&#39;before: &#39; + elements);
sort(elements);
console.log(&#39; after: &#39; + elements);

ログイン後にコピー

2. クイックソート

分析: クイックソートは、最初のソートパスでデータが 2 つの部分に分割され、一方の部分はもう一方の部分のすべてのデータよりも小さくなります。次に、それを再帰的に呼び出し、両側でクイックソートを実行します。

function  quickSort(elements) {
 
　　if (elements.length <= 1) { return elements; }
 
    var pivotIndex = Math.floor(elements.length / 2);
 
    var pivot = elements.splice(pivotIndex, 1)[0];
 
 
　　var left = [];
 
　　var right = [];
 
　　for (var i = 0; i < elements.length; i++){
 
　　　　if (elements[i] < pivot) {
 
　　　　　　left.push(elements[i]);
 
　　　　} else {
 
　　　　　　right.push(elements[i]);
 
　　　　}
 
　　}
 
　　return quickSort(left).concat([pivot], quickSort(right));
 
};
 
var elements=[5,6,2,1,3,8,7,1.2,5.5,4.5];
alert(quickSort(elements));

ログイン後にコピー

3. 挿入ソート

分析:

(1) 最初の要素から始めて、その要素はソートされたとみなすことができます

(2) 次の要素を取り出し、ソートされた要素シーケンスを後方から進めますフロントスキャン

(3) (並べ替えられた) 要素が新しい要素より大きい場合、要素を次の位置に移動します

(4) 並べ替えられた要素が以下になる位置が見つかるまで手順 3 を繰り返します。新しい要素

(5) 次の位置に新しい要素を挿入します

(6) 手順 2 を繰り返します

insertSort: function(elements) {

    var i = 1,
    j, step, key, len = elements.length;

    for (; i < len; i++) {

        step = j = i;
        key = elements[j];

        while (--j > -1) {
            if (elements[j] > key) {
                elements[j + 1] = elements[j];
            } else {
                break;
            }
        }

        elements[j + 1] = key;
    }

    return elements;
}

ログイン後にコピー

2. 二分探索

分析: 二分探索、二分探索とも言えます。まず、中間の値を見つけます。その値と比較して、大きい方を左に配置します。次に、両側の中央の値を見つけ、位置が見つかるまで上記の操作を続けます。

(1)再帰的メソッド

function binarySearch(data,item,start,end){
    var end=end || data.length-1;
    var start=start || 0;
    var m=Math.floor((start+end)/2);
    if(item==data[m]){
        return m;
    }else if(item<data[m]){
        return binarySearch(data,item,start,m-1) //递归调用
    }else{
        return binarySearch(data,item,m+1,end);
    }
    return false;
}

    var arr=[34,12,5,123,2,745,32,4];

    binary(arr,5);

ログイン後にコピー

(2)非再帰的メソッド

function binarySearch(data, item){
    var h = data.length - 1,
        l = 0;
    while(l <= h){
        var m = Math.floor((h + l) / 2);
        if(data[m] == item){
            return m;
        }
        if(item > data[m]){
            l = m + 1;
        }else{
            h = m - 1;
        }
    }
  
    return false;
}
var arr=[34,12,5,123,2,745,32,4];
binarySearch(arr,5);

ログイン後にコピー