一、基本用法
jsarray.sort()是Javascript中的一个方法，可用于对数组进行排序。这个方法可以没有参数，也可以接受一个函数作为参数。
当没有参数时，默认按照Unicode位码的顺序进行排序。如果需要对数字进行排序，需要使用比较函数。
const arr1 = ['banana', 'apple', 'orange'];
arr1.sort();
console.log(arr1); // ['apple', 'banana', 'orange']
const arr2 = [10, 5, 20];
arr2.sort();
console.log(arr2); // [10, 20, 5]
const arr3 = [10, 5, 20];
arr3.sort((a, b) => a - b);
console.log(arr3); // [5, 10, 20]
以上示例展示了jsarray.sort()的基本用法。当没有参数时，sort()方法会按照默认规则排序。当需要对数字进行排序时，需要传入比较函数。
二、比较函数
比较函数是jsarray.sort()中重要的参数，它决定了排序的规则和结果。
比较函数有两个参数a和b，表示需要比较的两个元素。比较函数返回值决定了a和b在排序结果中的位置。
当返回值小于0时，a会排在b的前面；当返回值大于0时，a会排在b的后面；当返回值等于0时，a和b的相对位置不变。
const arr1 = [10, 5, 20];
arr1.sort((a, b) => a - b);
console.log(arr1); // [5, 10, 20]
const arr2 = [10, 5, 20];
arr2.sort((a, b) => b - a);
console.log(arr2); // [20, 10, 5]
const arr3 = [{name: 'apple', price: 1}, {name: 'banana', price: 2}, {name: 'orange', price: 3}];
arr3.sort((a, b) => a.price - b.price);
console.log(arr3); // [{name: 'apple', price: 1}, {name: 'banana', price: 2}, {name: 'orange', price: 3}]
以上示例展示了比较函数的用法。第一个例子表示从小到大排序，第二个例子表示从大到小排序，第三个例子表示按照price属性从小到大排序。
三、稳定排序
稳定排序是指排序前后，排序实现对于相等元素的顺序不变。在实际开发中，稳定排序尤为重要。
jsarray.sort()默认是非稳定排序，但是可以通过比较函数实现稳定排序。
const arr1 = [{name: 'apple', price: 1}, {name: 'banana', price: 2}, {name: 'orange', price: 3}, {name: 'apple2', price: 1}];
arr1.sort((a, b) => {
if (a.price b.price) {
return 1;
} else {
if (a.name b.name) {
return 1;
} else {
return 0;
}
}
});
console.log(arr1);
// [{name: 'apple', price: 1}, {name: 'apple2', price: 1}, {name: 'banana', price: 2}, {name: 'orange', price: 3}]
以上示例演示了如何实现稳定排序。当元素价格相等时，再比较元素名称的大小。
四、jsarray.sort()的实现方法
jsarray.sort()是在ECMAScript标准中规定的。大多数现代浏览器使用的是快排算法。
快排算法的基本思想是选取一个基准值，将数组分成左右两部分，左边部分的所有元素都小于基准值，右边部分的所有元素都大于基准值，然后递归地对左右两部分进行排序。
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivotIndex = Math.floor(arr.length / 2);
const pivot = arr[pivotIndex];
const left = [];
const right = [];
for (let i = 0; i < arr.length; i++) {
if (i === pivotIndex) {
continue;
}
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
const arr1 = [10, 5, 20];
console.log(quickSort(arr1)); // [5, 10, 20]
以上示例展示了快排算法的实现方法。快排非常高效，但是在某些情况下会退化成O(n^2)的时间复杂度，例如原数组已经有序或者几乎有序。
五、jsarray.sort()的时间复杂度
对于通用数组排序算法，最坏时间复杂度是O(nlogn)，平均时间复杂度也是O(nlogn)。但是具体实现排序算法的时间复杂度和效率都有所不同。
jsarray.sort()的默认排序算法是快排，时间复杂度为O(nlogn)。但是在某些情况下，例如原数组已经有序或者几乎有序，快排会退化为O(n^2)的时间复杂度。
除了快排，Chrome浏览器还有另一种排序算法TimSort。TimSort是由Tim Peters在2002年发明的，是一种稳定排序算法，被用于Python、Java和C#等语言中的实现。TimSort算法的时间复杂度为O(nlogn)。
六、总结
jsarray.sort()是Javascript中的一个重要方法，可用于对数组进行排序。比较函数是排序规则的决定因素，稳定排序尤为重要。jsarray.sort()默认使用快排算法实现，快排算法的时间复杂度为O(nlogn)。在某些情况下会退化为O(n^2)的时间复杂度。除了快排，Chrome浏览器还实现了TimSort算法，TimSort算法是一种稳定排序算法，时间复杂度为O(nlogn)。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/206011.html
微信扫一扫 
支付宝扫一扫 