JavaScriptベース-配列並び替えの6つの方法

1.sort()
ソフト()はASCIIの文字順で、デフォルトの昇順です.
標準配列

//   
var sum = 0;
var numbers = [4, 2, 5, 1, 3];
numbers.sort(function(a, b) {
    sum++;
    return a - b;
});

console.log(numbers); // 1 2 3 4 5
console.log(sum); // 7

//    
const months = ['March', 'Jan', 'Feb', 'Dec'];
months.sort();

console.log(months);  // ['Dec', 'Feb', 'Jan', 'March']

配列オブジェクト

var student = [
    {'name': 'jack', 'age': 18},
    {'name': 'apple', 'age': 16},
    {'name': 'tony', 'age': 30},
    {'name': 'marry', 'age': 8},
]
//    
student.sort(function (a, b) {
    return (a.age - b.age)
});

//    
student.sort(function (a, b) {
  var nameA = a.name.toUpperCase();
  var nameB = b.name.toUpperCase();
  if (nameA < nameB) {
    return -1;
  }
  if (nameA > nameB) {
    return 1;
  }
});

2.発泡体の並べ替え
隣の二つの数を一つずつ比較して、前の数が後の数より小さいなら、位置を交換します.
ポイント:交換プロセスは、変数が小さい値/大きな値を記憶する必要があります.

var numbers = [4, 2, 5, 1, 3];

var sum = 0;
function bubbleSort (arr) {
    let temp = '';
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
            sum++;
        }
    }
    return arr;
};

console.log(bubbleSort(numbers));
console.log(sum) // 20

3.快速並べ替え
泡並べ替えの改良アルゴリズム.並べ替えは複数の比較と交換によって実現される.
ポイント:境界値を設定する必要があります.境界値によって配列を左右に分けます.そして左右で境界値と左右の部分を取る作業を繰り返します.

var numbers = [4, 2, 5, 1, 3];

var sum = 0;
function quickSort (arr) {
    if (arr.length <= 1) {
        return arr;
    }
    var medianIndex = Math.floor(arr.length / 2); //      
    var medianValue = arr.splice(medianIndex, 1); //    
    var left = [];
    var right = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < medianValue) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
        sum++;
    }
    console.log(medianIndex, medianValue, left, right)
    return quickSort(left).concat(medianValue,quickSort(right));
};

console.log(quickSort(numbers));
console.log(sum) // 10

4.並べ替えの挿入
前のn−1の要素が順序付けされていると仮定して、n番目の要素を前の列に挿入します.
ポイント:順序配列の最後の位置を定義し、最後のビットから連続的に前の要素と比較し、挿入位置が見つかるまで.

var numbers = [4, 2, 5, 1, 3];

var sum = 0;
function insertSort(arr) {
    //             
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < arr[i - 1]) {
            //              i   
            var temp = arr[i];
            //             
            var j = i - 1;
            arr[i] = arr[j];
            //         ，      ，       
            while(j >= 0 && temp < arr[j]){
                arr[ j+1 ] = arr[j];
                j--;
                sum++;
            };
            //  
            arr[ j+1 ] = temp;
        }
    }
}

console.log(insertSort(numbers));
console.log(sum) // 6

5.ヒルの並べ替え
ヒル順序付けは、記録を下付きの一定の増分パケットで、各グループに直接挿入順序付けアルゴリズムを使用して並べ替えます.
ヒルの並べ替えは、並べ替えアルゴリズムを挿入するより効率的な改良バージョンです.

var numbers = [4, 2, 5, 1, 3];
var sum = 0;

function shellSort(arr) {
    var len = arr.length;
    //       
    var fraction = Math.floor(len / 2);
    // fraction = Math.floor(fraction / 2) =>          
    for (fraction; fraction > 0; fraction = Math.floor(fraction / 2)) {
        //         
        for (var i = fraction; i < len; i++) {
            //             
            for (var j = i - fraction; j >= 0 && arr[j] > arr[fraction + j]; j -= fraction) {
                var temp = arr[j];
                arr[j] = arr[fraction + j]; //   
                arr[fraction + j] = temp; //   
                sum++;
            }
        }
    }
}

console.log(shellSort(numbers));
console.log(sum) // 6

6.並べ替えの選択
並べ替えられるデータ要素の中から最小/最大の要素を選択して、シーケンスの開始位置に保存し、残りの並べ替えられていない要素の中から最小/最大要素を探して、並べ替えられたシーケンスの最後に置く.この類推により、並べ替え対象のデータ要素の個数がゼロになるまで.

var numbers = [4, 2, 5, 1, 3];

var sum = 0;
function selectionSort(arr) {
    if (arr == null || arr.length < 2) {
        return arr;
    }
    for (var i = 0; i < (arr.length - 1); i++) {
        let minIndex = i;
        for (let j = i + 1; j < arr.length; j++) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            sum++;
        }
        let temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}


console.log(selectionSort(numbers));
console.log(sum) // 10

7.比較
計算回数は同じ配列[4, 2, 5, 1, 3]の異なる方法で比較される.
方法
回数を計算する
安定性
sort()
7
泡の並べ替え
20
安定している
クイックソート
10
不安定です
並べ替えの挿入
6
安定している
ヒルの並べ替え
6
不安定です
並べ替えを選択
10
不安定です