JavaScriptArray.Sort实现？

Question

JavaScriptArray.Sort实现？

JavaScript是哪种算法Array#sort()功能使用？我知道它可以使用各种参数和函数来执行不同类型的排序，我只对普通排序所使用的算法感兴趣。

Answer 1

如果你看看这个虫子224128，看来MergeSort正在被Mozilla使用。

Answer 2

JS不需要使用特定的排序算法。正如许多人在这里提到的，Mozilla使用合并排序，但是，在Chrome的V8源代码中，到目前为止，它使用的是快速排序和InsertionSort，用于较小的数组。V8发动机源从807-891号线&nbsp;&nbsp;var&nbsp;QuickSort&nbsp;=&nbsp;function&nbsp;QuickSort(a,&nbsp;from,&nbsp;to)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;third_index&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(true)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;Insertion&nbsp;sort&nbsp;is&nbsp;faster&nbsp;for&nbsp;short&nbsp;arrays. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(to&nbsp;-&nbsp;from&nbsp;<=&nbsp;10)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;InsertionSort(a,&nbsp;from,&nbsp;to); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(to&nbsp;-&nbsp;from&nbsp;>&nbsp;1000)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;third_index&nbsp;=&nbsp;GetThirdIndex(a,&nbsp;from,&nbsp;to); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;third_index&nbsp;=&nbsp;from&nbsp;+&nbsp;((to&nbsp;-&nbsp;from)&nbsp;>>&nbsp;1); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;Find&nbsp;a&nbsp;pivot&nbsp;as&nbsp;the&nbsp;median&nbsp;of&nbsp;first,&nbsp;last&nbsp;and&nbsp;middle&nbsp;element. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;v0&nbsp;=&nbsp;a[from]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;v1&nbsp;=&nbsp;a[to&nbsp;-&nbsp;1]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;v2&nbsp;=&nbsp;a[third_index]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;c01&nbsp;=&nbsp;comparefn(v0,&nbsp;v1); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(c01&nbsp;>&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;v1&nbsp;<&nbsp;v0,&nbsp;so&nbsp;swap&nbsp;them. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;tmp&nbsp;=&nbsp;v0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;v0&nbsp;=&nbsp;v1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;v1&nbsp;=&nbsp;tmp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;//&nbsp;v0&nbsp;<=&nbsp;v1. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;c02&nbsp;=&nbsp;comparefn(v0,&nbsp;v2); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(c02&nbsp;>=&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;v2&nbsp;<=&nbsp;v0&nbsp;<=&nbsp;v1. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;tmp&nbsp;=&nbsp;v0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;v0&nbsp;=&nbsp;v2; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;v2&nbsp;=&nbsp;v1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;v1&nbsp;=&nbsp;tmp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;v0&nbsp;<=&nbsp;v1&nbsp;&&&nbsp;v0&nbsp;<&nbsp;v2 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;c12&nbsp;=&nbsp;comparefn(v1,&nbsp;v2); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(c12&nbsp;>&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;v0&nbsp;<=&nbsp;v2&nbsp;<&nbsp;v1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;tmp&nbsp;=&nbsp;v1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;v1&nbsp;=&nbsp;v2; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;v2&nbsp;=&nbsp;tmp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;v0&nbsp;<=&nbsp;v1&nbsp;<=&nbsp;v2 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[from]&nbsp;=&nbsp;v0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[to&nbsp;-&nbsp;1]&nbsp;=&nbsp;v2; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;pivot&nbsp;=&nbsp;v1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;low_end&nbsp;=&nbsp;from&nbsp;+&nbsp;1;&nbsp;&nbsp;&nbsp;//&nbsp;Upper&nbsp;bound&nbsp;of&nbsp;elements&nbsp;lower&nbsp;than&nbsp;pivot. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;high_start&nbsp;=&nbsp;to&nbsp;-&nbsp;1;&nbsp;&nbsp;//&nbsp;Lower&nbsp;bound&nbsp;of&nbsp;elements&nbsp;greater&nbsp;than&nbsp;pivot. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[third_index]&nbsp;=&nbsp;a[low_end]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[low_end]&nbsp;=&nbsp;pivot; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;From&nbsp;low_end&nbsp;to&nbsp;i&nbsp;are&nbsp;elements&nbsp;equal&nbsp;to&nbsp;pivot. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;From&nbsp;i&nbsp;to&nbsp;high_start&nbsp;are&nbsp;elements&nbsp;that&nbsp;haven't&nbsp;been&nbsp;compared&nbsp;yet. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;partition:&nbsp;for&nbsp;(var&nbsp;i&nbsp;=&nbsp;low_end&nbsp;+&nbsp;1;&nbsp;i&nbsp;<&nbsp;high_start;&nbsp;i++)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;element&nbsp;=&nbsp;a[i]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;order&nbsp;=&nbsp;comparefn(element,&nbsp;pivot); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(order&nbsp;<&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[i]&nbsp;=&nbsp;a[low_end]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[low_end]&nbsp;=&nbsp;element; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;low_end++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;if&nbsp;(order&nbsp;>&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;do&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;high_start--; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(high_start&nbsp;==&nbsp;i)&nbsp;break&nbsp;partition; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;top_elem&nbsp;=&nbsp;a[high_start]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;order&nbsp;=&nbsp;comparefn(top_elem,&nbsp;pivot); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;while&nbsp;(order&nbsp;>&nbsp;0); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[i]&nbsp;=&nbsp;a[high_start]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[high_start]&nbsp;=&nbsp;element; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(order&nbsp;<&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;element&nbsp;=&nbsp;a[i]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[i]&nbsp;=&nbsp;a[low_end]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[low_end]&nbsp;=&nbsp;element; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;low_end++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(to&nbsp;-&nbsp;high_start&nbsp;<&nbsp;low_end&nbsp;-&nbsp;from)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;QuickSort(a,&nbsp;high_start,&nbsp;to); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;to&nbsp;=&nbsp;low_end; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;QuickSort(a,&nbsp;from,&nbsp;low_end); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;from&nbsp;=&nbsp;high_start; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;};V8使用TimSort，谢谢@celwell。来源