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 堆积排序法