Внутренняя работа JavaScript Array.sort ([compareFunc]);

Question

Я очень стараюсь "увидеть", что происходит в вызове Array.sort () при передаче простой функции сравнения.Я дошел до этого далеко, но цифры, кажется, никогда не складываются, и я хотел бы знать, как JavaScript приходит к выводу.Может быть, я упускаю какой-то фундаментальный момент в этом.

var nums = new Array(40,20,230,65);

var b = a.sort(function(a,b){

return a-b;

});

, поэтому я работаю так:

1. 40-20 = 20 = (> 0) т. б, а или 20,40

2. 230-65 = 165 (> 0) т. б, а или 230,65

3. 40-65 = -25 (<0), так что a, b или 40,65 </p>

Я запустил его с этими числами, он делает три вычисления и получается 20,40,65,230, что правильно, но я не знаю, «как» ... Каким образом он выбрал числа для помещения в сгенерированный массив сортировки.Я имею в виду, я получаю шесть цифр из ответа (результаты трех вычислений), так как мне превратить эти шесть в необходимые четыре?

Любая помощь.Я действительно хочу понять это наизнанку.:)

РЕДАКТИРОВАТЬ: Хорошо, я вижу, как это работает сейчас, это дурачит с оригинальным массивом, переупорядочивая числа согласно значению, возвращенному функцией сортировки.Но когда я использую массив из четырех чисел, я могу обработать его двумя «ходами», но JavaScript делает три, и последнее кажется немного посторонним.Попробуйте и посмотрите.:)

---

Последнее и самое лучшее обновление !!

Хорошо, с тех пор как я задал этот вопрос, я копался на бумаге и с помощью JavaScript, и я обнаружил, как быстро сортироватьработает иш.Я не очень разбираюсь в журналах, но думаю, это научит меня уделять больше внимания математике.

Я взял свой последний пример, чтобы сэкономить место, так что вот еще один пример, который я выполнил, и какЭто прошло.Он совпадает с той же сортировкой, которую я делал на бумаге, за исключением того, что порядок пар чисел, которые JS выбирает из массива для сортировки, несколько непредсказуем, поэтому на самом деле он выполняет больше сравнений, чем мне нужно, но я полагаю, потому что я могудумайте о результатах заранее и выбирайте пары чисел так, как я хочу (очень не по типу компьютера).

В этом тесте я сделал это в шести расчетах, JS сделал это в десяти, что, честно говоря, более тщательно.

Array == 2,16,7,3,10

2 - 16 == -14 (<0) |2,16,7,3,10 </p>

16 - 7 == 9 (> 0) |2,7,16,3,10

16 - 3 == 13 (> 0) |2,7,3,16,10

16 - 10 == 6 (> 0) |2,7,3,10,16

2 - 7 == -5 (<0) |2,7,3,10,16 </p>

7 - 3 == 4 (> 0) |2,3,7,10,16

Array == 2,3,7,10,16

Не уверен, если это, строго говоря, быстрая сортировка, так как быстрая сортировкаиспользует число разворота и использует его в качестве центральной точки, вокруг которой делится массив в сортировке.Но это мое понимание того, как JS делает это.Поправьте меня если я ошибаюсь.:)

Answer 1

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

Answer 2

Учитывая массив из N элементов, существует N факторных перестановок, из которых сортируется только один. Поскольку каждое сравнение делит перестановки на два набора, для сравнения перестановки с элементами необходимо выполнить O (log (N!)), Хотя это зависит от алгоритма и исходной перестановки.

В исходном случае с 4-элементным массивом вы можете написать собственную процедуру сортировки, которая не делает никаких предположений относительно исходного массива и гарантирует сортировку массива за 5 сравнений, но в трети случаев вам повезет, и вы будете использовать только 4 сравнения. С другой стороны, для пузырьковой сортировки потребуется только 3 сравнения в маловероятном случае, когда массив уже отсортирован, но часто требуется 6 сравнений. Большинство браузеров используют один из стандартных универсальных алгоритмов сортировки с хорошо известными характеристиками производительности.