18
Tôi đã thực hiện một thử nghiệm nhỏ và phát hiện ra rằng array.sort(function(a, b) { return a - b; }); nhanh hơn rất nhiều so với array.sort(); trong JavaScript.JavaScript, sắp xếp với thông số thứ hai nhanh hơn
Kết quả khá sốc, nhanh hơn khoảng 1,7 lần trong IE9, 1,6 lần trong FF7 và 6,7 lần trong Chrome.
Ngoài ra, bằng cách thực hiện quicksort một mình trong JS, tôi thấy nó thậm chí còn nhanh hơn cả hai phương pháp được đề cập ở trên. (Hai cách triển khai khác nhau, một hàm chấp nhận hàm so sánh làm tham số, hàm kia không. Cả hai đều nhanh hơn.)
Có giải thích hợp lý nào không?
EDIT: hiện thực của tôi:
Không Comparer:
function quickSort(array, from, to) {
if(typeof from === 'undefined') {
from = 0;
to = array.length - 1;
}
else if(typeof to === 'undefined') {
to = array.length - 1;
}
if(to - from < 1) {
return;
}
var i = from, pivot = to, t;
while(i < pivot) {
if(array[i] > array[pivot]) {
t = array[i];
array[i] = array[pivot - 1];
array[pivot - 1] = array[pivot];
array[pivot] = t;
pivot--;
}
else {
i++;
}
}
quickSort(array, from, pivot - 1);
quickSort(array, pivot + 1, to);
}
Với Comparer:
function quickSortFunc(array, sortfunc, from, to) {
if(typeof from === 'undefined') {
from = 0;
to = array.length - 1;
}
else if(typeof to === 'undefined') {
to = array.length - 1;
}
if(to - from < 1) {
return;
}
var i = from, pivot = to, t;
while(i < pivot) {
if(sortfunc(array[i], array[pivot]) > 0) {
t = array[i];
array[i] = array[pivot - 1];
array[pivot - 1] = array[pivot];
array[pivot] = t;
pivot--;
}
else {
i++;
}
}
quickSortFunc(array, sortfunc, from, pivot - 1);
quickSortFunc(array, sortfunc, pivot + 1, to);
}
đó là một khả năng rằng các chức năng sắp xếp được điều hành từ trung bình. Làm thế nào lớn là mảng mà bạn sử dụng? – Matt
Sắp xếp "bình thường" hoạt động trên biểu diễn chuỗi của các phần tử. Đó có thể là một chi phí có thể. –
Matt, tôi đã thử nghiệm nó trên các mảng 100, 1000, 10000 và 100000 phần tử. Felix, tôi mặc dù về hai, nó vẫn không giải thích tại sao việc thực hiện của tôi với một so sánh nhanh hơn so với việc thực hiện bản địa với một so sánh. –