实现js sort

JavaScript 数组排序方法

JavaScript 提供了 Array.prototype.sort() 方法用于对数组元素进行排序。该方法默认将元素转换为字符串后按照 Unicode 码点顺序排序。

基本用法

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

数字排序

默认的排序方式会导致数字被转换为字符串后比较：

const numbers = [40, 1, 5, 200];
numbers.sort();
console.log(numbers); // [1, 200, 40, 5] (不正确)

需要提供比较函数来实现正确的数字排序：

const numbers = [40, 1, 5, 200];
numbers.sort((a, b) => a - b);
console.log(numbers); // [1, 5, 40, 200] (升序)
numbers.sort((a, b) => b - a);
console.log(numbers); // [200, 40, 5, 1] (降序)

对象数组排序

对于对象数组，可以根据某个属性进行排序：

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

// 按value属性升序
items.sort((a, b) => a.value - b.value);

// 按name属性字母顺序
items.sort((a, b) => {
  const nameA = a.name.toUpperCase();
  const nameB = b.name.toUpperCase();
  if (nameA < nameB) return -1;
  if (nameA > nameB) return 1;
  return 0;
});

稳定排序

从 ES2019 开始，JavaScript 规范要求排序算法是稳定的，即相同值的元素在排序后保持原有相对顺序。

性能考虑

sort() 方法的时间复杂度和空间复杂度取决于具体实现。现代 JavaScript 引擎通常使用高效的排序算法如 TimSort（时间复杂度 O(n log n)）。