2017.9.24並べ替えアルゴリズムのまとめ-バブル並べ替え、挿入並べ替え、選択並べ替え

ソートアルゴリズムを復習するには、まず最初に最も基本的なのはバブルソートと挿入ソートです.そして、これも面接でよく聞かれます.ここでまとめてみましょう.

バブルソート

隣接する要素を比較します.1つ目が2つ目より大きい場合は、2つを交換します.
各ペアの隣接要素について同じ作業を行い、最初のペアから最後のペアまで行います.このステップが終わると、最後の要素が最大の数になります.
最後の1つを除いて、すべての要素について上記の手順を繰り返します.
比較する必要がなくなるまで、ますます少ない要素に対して上記の手順を繰り返します.
JavaScriptは次のように実装されています.

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; 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;
}

ソートの挿入

個人的には、一つの配列にほかならないが、二つの部分に分けて、一部は順序があり、一部は順序がない(最初の要素を順序があると見なす)、そして順序のない要素と順序のある部分を比較して、適切な場所に挿入することを提案する.
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;
}

ソートの選択

ソートを選択して、個人の理解も2つの部分に分けられて、一部は秩序があって、一部は順序がなくて、最初はすべて順序がなくて、完全な配列を遍歴して、最小(大きい)のあの要素を探し出して、秩序の中に挿入して、それから次の小さい(大きい)のあの数を探して秩序の中に挿入します.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;
}