Sort 排序

Sort 排序

排序演算法複雜度

演算法 Time Complexity 時間複雜度 Space Complexity 空間複雜度
Bubble Sort 氣泡排序法 O(n^2) O(1)
Insert Sort 插入排序法 O(n^2) O(1)
Selection Sort 選擇排序法 O(n^2) O(1)
Merge Sort 合併排序法 O(n log n) O(n)
Quick Sort 快速排序法 平均:O(n log n) 最差:O(n^2) O(1)
Heap Sort 堆積排序法 O(n log n) O(1)

程式預設排序 演算法

JavaScript

環境 情境 使用的排序演算法
Mozilla Merge Sort 合併排序法
WebKit(Chrome, Safari, etc) 數字陣列 Quick Sort 快速排序法
WebKit(Chrome, Safari, etc) 非數字陣列 Merge Sort 合併排序法
WebKit(Chrome, Safari, etc) 其他 Selection Sort 選擇排序法

程式

JavaScript

Array.prototype.sort() - JavaScript | MDN

如果沒有 callback 排序函式,則預設的排序順序是根據字串的 Unicode 編碼位置(code points) 而定

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

const array1 = [1, 30, 4, 21, 100000];
array1.sort();
// [1, 100000, 21, 30, 4]
console.log(array1);

傳入比較的兩個變數 a, b

狀況 回傳值
a 要排前面 -1,或負值
b 要排前面 1,或正值
a 與 b 順序不變 0

按照數字大小排序

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

按照指定鍵值排序

var items = [
  { name: 'Edward', value: 21 },
  { name: 'Sharpe', value: 37 },
  { name: 'And', value: 45 },
  { name: 'The', value: -12 },
  { name: 'Magnetic', value: 13 },
  { name: 'Zeros', value: 37 }
];

// 排序數字大小
items.sort(function (a, b) {
    if (a.value < b.value) {
        // a 比較小,排前面
        return -1;
    } else if (a.value > b.value){
        // b 比較小,排前面
        return 1;
    } else {
        // 一樣大,不調整位置
        return 0;
    }
});


items.sort(function (a, b) {
  return a.value - b.value;
});

// [
//   { name: 'The', value: -12 },
//   { name: 'Magnetic', value: 13 },
//   { name: 'Edward', value: 21 },
//   { name: 'Sharpe', value: 37 },
//   { name: 'Zeros', value: 37 },
//   { name: 'And', value: 45 }
// ]
console.log(items);

按照字母大小排序

var items = [
    { name: 'Edward', value: 21 },
    { name: 'Sharpe', value: 37 },
    { name: 'And', value: 45 },
    { name: 'The', value: -12 },
    { name: 'Magnetic', value: 13 },
    { name: 'Zeros', value: 37 }
];

// 依照名稱字母順序排序
items.sort(function(a, b) {
    var nameA = a.name.toUpperCase(); // ignore upper and lowercase
    var nameB = b.name.toUpperCase(); // ignore upper and lowercase
    if (nameA < nameB) {
        // nameA 字母順序比較低,排前面
        return -1;
    }
    if (nameA > nameB) {
        // nameB 字母順序比較低,排前面
        return 1;
    }

    // nameA 與 nameB 字母順序一樣(同樣字串),不調整排序
    return 0;
});

// [
//   { name: 'And', value: 45 },
//   { name: 'Edward', value: 21 },
//   { name: 'Magnetic', value: 13 },
//   { name: 'Sharpe', value: 37 },
//   { name: 'The', value: -12 },
//   { name: 'Zeros', value: 37 }
// ]
console.log(items);

參考資料


Bubble sort 氣泡排序法

Bubble sort 氣泡排序法

Insertion sort 插入排序法

Insertion sort 插入排序法

Selection sort 選擇排序法

Selection sort 選擇排序法

Merge sort 合併排序法

Merge sort 合併排序法

Quick Sort 快速排序法

Quick Sort 快速排序法

Heap Sort 堆積排序法

Heap Sort 堆積排序法