Пытаясь выполнить шаги сортировки числового массива в Javascript

Question

Я учусь выполнять сортировку массива в Javascript по массиву чисел, я просмотрел страницу mdn и выполнил поиск, вот что я пытаюсь понять:

 var numbers = [4, 2, 5, 1, 3];
numbers.sort(function(a, b) {
  return a - b;
});
console.log(numbers);

// [1, 2, 3, 4, 5]

Я понимаю, что происходит, я просто не могу найти простую пошаговую статью о сортировке массивов javascript, которая показывает, как 'a' и 'b' сравниваются и перемещаются, например, когда достигнут конец массива, повторяется ли сортировка, пока не отсортированы все элементы? Думаю, мне интересно узнать о реализации простым и понятным способом.

Чтобы добавить, я попытался записать в консоль вывод, но все еще был немного смущен тем, как это было сделано, поэтому искал более конкретный ответ от кого-то, кто знает.

Answer 1

Если вы хотите увидеть, что происходит, поместите некоторые записи в функцию сравнения:

var numbers = [4, 2, 5, 1, 3];
numbers.sort(function(a, b) {
  console.log("["+numbers.join()+"], comparing element #"+numbers.indexOf(a)+" ("+a+") and #"+numbers.indexOf(b)+" ("+b+"): "+(a-b));
  return a - b;
});
console.log(numbers.join());

Затем, проявив немного терпения, вы сможете отследить, как движутся элементы, и распознать алгоритм сортировки в действии.

Answer 2

Конкретный используемый алгоритм сортировки не указан в спецификации ; движок JavaScript может свободно использовать любой алгоритм сортировки , который ему нравится, будь то пузырьковая сортировка , быстрая сортировка или что-то еще. Но да, алгоритмы сортировки в общем случае должны делать больше, чем просто один проход данных и одно сравнение для каждого элемента. Гораздо больше.

Answer 3

Метод Array.sort является встроенным. Он использует быструю сортировку на машинном языке, которая будет быстрее, чем все, что вы могли бы сделать в своем коде. У Computerphile хорошее видео на быстрой сортировке.

Однако любой алгоритм сортировки должен знать, какой из двух элементов стоит первым, и для этого предназначена функция. Он будет передан независимо от того, какие два элемента массива сравниваются в этот момент в общем алгоритме, и вернет:

отрицательное число: первый аргумент должен сортироваться первым. положительное число: второй аргумент должен сортировать первый. ноль: они равны.

Надеюсь, это прояснит!

Answer 4

Реализация функции sort связана с браузером

Например, реализация WebKit: https://gist.github.com/964673