フロントエンド面接ではよく質問(泡立ちと速排)と安定性の問題があります

秋の募集に触れたばかりなのに、面接が来るとコードを引き裂くという人が多いのを聞いた.私は他の人に経を取って、泡と速い列をまとめて、後でハソートアルゴリズムの安定性をまとめました.

バブルソート:(データ規模が小さい場合に適用)

バブルは通俗的に並べ替えに関与するデータが水中の気泡がゆっくりと水面に浮かぶように数列の先端に「浮かぶ」ことだ.
バブルソートのポイント:
1、2層の循環、外層の循環は訪問数列の繰り返しの回数を制御して、内層の循環はデータの比較、交換を行って、データの“浮上”です.
2、内層循環は隣接するデータで比較する.
例えば、arr=[1,5,8,2,4,9]の配列があり、内層サイクルは1対5比であり、その後5対8比であり、、、、このようにずっと比である.

    var arr = [9, 2, 4, 1, 8];
    function bubbleSort(arr) {
        var i = arr.length;
        var j;
        var temp;
        while (i > 0) {
            for (j = 0; j < i - 1; j++) {
                console.log(arr[j],arr[j+1]);//       
                console.log("------------");
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            console.log("i===="+i);
            i--;
        }
        return arr;
    }
    console.log(bubbleSort(arr));

配列外ループ回数は配列長である.外部サイクルごとに内サイクルを2回比較した後,最大値を配列末尾に並べた.

クイックソート:

クイックソートの考え方:
1配列の最中間を先に探す個数を基準とする
2配列をこの基準で基準より小さいleft配列と基準より大きいright配列に分け、
3上記の2つのステップを繰り返します.

    var arr = [90,9,12,6,30,60,36,32,40];
    function quickSort(arr){
        if (arr.length <= 1) { return arr; }
        var pivotIndex = Math.floor(arr.length / 2); //      
        var pivot = arr.splice(pivotIndex, 1)[0];    //    
        var left = [];  //       
        var right = [];//       
        for (var i = 0; i < arr.length; i++){
            if (arr[i] < pivot) {
                left.push(arr[i]); //    
            } else {
                right.push(arr[i]);
            }
        }
        return quickSort(left).concat([pivot], quickSort(right));
    }
    //concat()              ,            ，                。
    console.log(quickSort(arr));

グループ化、1つの基準を探して、小さい数は左に置いて、大きい数は右に置いて、順番にグループ化して配列要素が1になるまで

ソートアルゴリズム:

不安定:高速ソート、選択ソート、スタックソート、ヒルソート(高速選択スタック希)
安定:挿入ソート、バブルソート、集計ソート、基数ソート(プラグインベース)
アルゴリズムの安定性判断:並べ替え前の2つの等しい数のシーケンスにおける前後位置順序と並べ替え後の2つの前後位置順序は同じである