2017.9.24並べ替えアルゴリズムのまとめ-バブル並べ替え、挿入並べ替え、選択並べ替え
1929 ワード
ソートアルゴリズムを復習するには、まず最初に最も基本的なのはバブルソートと挿入ソートです.そして、これも面接でよく聞かれます.ここでまとめてみましょう.
隣接する要素を比較します.1つ目が2つ目より大きい場合は、2つを交換します.
各ペアの隣接要素について同じ作業を行い、最初のペアから最後のペアまで行います.このステップが終わると、最後の要素が最大の数になります.
最後の1つを除いて、すべての要素について上記の手順を繰り返します.
比較する必要がなくなるまで、ますます少ない要素に対して上記の手順を繰り返します.
JavaScriptは次のように実装されています.
個人的には、一つの配列にほかならないが、二つの部分に分けて、一部は順序があり、一部は順序がない(最初の要素を順序があると見なす)、そして順序のない要素と順序のある部分を比較して、適切な場所に挿入することを提案する.
JavaScript実装:
ソートを選択して、個人の理解も2つの部分に分けられて、一部は秩序があって、一部は順序がなくて、最初はすべて順序がなくて、完全な配列を遍歴して、最小(大きい)のあの要素を探し出して、秩序の中に挿入して、それから次の小さい(大きい)のあの数を探して秩序の中に挿入します.JavaScript実装コード:
バブルソート
隣接する要素を比較します.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;
}