js sort实现

JavaScript 数组排序实现

JavaScript 提供了 Array.prototype.sort() 方法用于对数组元素进行排序。默认情况下，sort() 方法将元素转换为字符串并按照 Unicode 码点顺序排序。对于数字或其他复杂排序需求，需要自定义比较函数。

默认排序（字符串排序）

const fruits = ['banana', 'apple', 'orange', 'grape'];
fruits.sort();
console.log(fruits); // ['apple', 'banana', 'grape', 'orange']

数字升序排序

const numbers = [40, 100, 1, 5, 25];
numbers.sort((a, b) => a - b);
console.log(numbers); // [1, 5, 25, 40, 100]

数字降序排序

const numbers = [40, 100, 1, 5, 25];
numbers.sort((a, b) => b - a);
console.log(numbers); // [100, 40, 25, 5, 1]

对象数组排序

const users = [
  { name: 'John', age: 25 },
  { name: 'Jane', age: 30 },
  { name: 'Bob', age: 20 }
];

// 按年龄升序
users.sort((a, b) => a.age - b.age);

// 按姓名字母顺序
users.sort((a, b) => a.name.localeCompare(b.name));

稳定排序实现

从 ES2019 开始，JavaScript 要求 sort() 方法必须是稳定排序（相同元素的相对位置保持不变）。对于需要稳定排序的旧环境，可以手动实现：

function stableSort(array, compare) {
  const stabilized = array.map((el, index) => ({ el, index }));
  stabilized.sort((a, b) => {
    const order = compare(a.el, b.el);
    if (order !== 0) return order;
    return a.index - b.index;
  });
  return stabilized.map(entry => entry.el);
}

多条件排序

const items = [
  { name: 'Edward', value: 21 },
  { name: 'Sharpe', value: 37 },
  { name: 'And', value: 45 },
  { name: 'Edward', value: 12 }
];

items.sort((a, b) => {
  if (a.name > b.name) return 1;
  if (a.name < b.name) return -1;
  return a.value - b.value;
});

本地化字符串排序

const items = ['réservé', 'Premier', 'Cliché', 'communiqué'];
items.sort((a, b) => a.localeCompare(b, 'fr', { sensitivity: 'base' }));

注意事项

• sort() 方法会修改原数组
• 比较函数应返回负数、零或正数
• 对于大型数据集，可能需要考虑性能优化
• 默认排序时间复杂度通常为 O(n log n)，但具体实现取决于 JavaScript 引擎