最快的方法来sorting在JavaScript中的32位有符号整数数组？
_radixSort_0 = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]; /* RADIX SORT Use 256 bins Use shadow array - Get counts - Transform counts to pointers - Sort from LSB - MSB */ function radixSort(intArr) { var cpy = new Int32Array(intArr.length); var c4 = [].concat(_radixSort_0); var c3 = [].concat(_radixSort_0); var c2 = [].concat(_radixSort_0); var c1 = [].concat(_radixSort_0); var o4 = 0; var t4; var o3 = 0; var t3; var o2 = 0; var t2; var o1 = 0; var t1; var x; for(x=0; x<intArr.length; x++) { t4 = intArr[x] & 0xFF; t3 = (intArr[x] >> 8) & 0xFF; t2 = (intArr[x] >> 16) & 0xFF; t1 = (intArr[x] >> 24) & 0xFF ^ 0x80; c4[t4]++; c3[t3]++; c2[t2]++; c1[t1]++; } for (x=0; x<256; x++) { t4 = o4 + c4[x]; t3 = o3 + c3[x]; t2 = o2 + c2[x]; t1 = o1 + c1[x]; c4[x] = o4; c3[x] = o3; c2[x] = o2; c1[x] = o1; o4 = t4; o3 = t3; o2 = t2; o1 = t1; } for(x=0; x<intArr.length; x++) { t4 = intArr[x] & 0xFF; cpy[c4[t4]] = intArr[x]; c4[t4]++; } for(x=0; x<intArr.length; x++) { t3 = (cpy[x] >> 8) & 0xFF; intArr[c3[t3]] = cpy[x]; c3[t3]++; } for(x=0; x<intArr.length; x++) { t2 = (intArr[x] >> 16) & 0xFF; cpy[c2[t2]] = intArr[x]; c2[t2]++; } for(x=0; x<intArr.length; x++) { t1 = (cpy[x] >> 24) & 0xFF ^ 0x80; intArr[c1[t1]] = cpy[x]; c1[t1]++; } return intArr; } 编辑：
到目前为止，最好的/唯一的主要优化是JStypes的数组。 对正常基数sorting的阴影数组使用types化数组已经产生了最好的结果。 我也能够挤出一点额外的地方快速sorting使用JS内置的堆栈推/popup。
最新的jsfiddle基准
Intel i7 870, 4GB, FireFox 8.0 2mil radixSort(intArr): 172 ms radixSortIP(intArr): 1738 ms quickSortIP(arr): 661 ms 200k radixSort(intArr): 18 ms radixSortIP(intArr): 26 ms quickSortIP(arr): 58 ms
看起来标准的基数sorting确实是这个工作stream程的王者。 如果有人有时间尝试循环展开或其他修改，我将不胜感激。
我有一个特定的用例，我希望在JavaScript中尽可能快地进行sorting。 将有客户端脚本将访问的大型（50,000 – 2mil），未分类（基本上是随机），整型（32位带符号）数组，然后需要对这些数据进行sorting和呈现。
我已经实现了一个相当快的基数sorting和适当的地方快速sortingjsfiddle基准，但对于我的上限数组长度，他们仍然相当缓慢。 快速sorting在我的上限数组大小上执行得更好，而基数sorting在我的下限上执行得更好。
defaultSort is the built-in JavaScript array.sort with an integer compare function Intel C2Q 9650, 4GB, FireFox 3.6 2mil radixSortIP(intArr): 5554 ms quickSortIP(arr): 1796 ms 200k radixSortIP(intArr): 139 ms quickSortIP(arr): 190 ms defaultSort(intArr): 354 ms Intel i7 870, 4GB, FireFox 8.0 2mil radixSortIP(intArr): 990 ms quickSortIP(arr): 882 ms defaultSort(intArr): 3632 ms 200k radixSortIP(intArr): 28 ms quickSortIP(arr): 68 ms defaultSort(intArr): 306 ms
问题
- 是否有更好的实现任何sortingalgorithm，可以满足我的用例/需求？
- 是否有任何优化，可以在我的地方基数/快速sorting实现来提高性能？
-
- 有没有一种有效的方法来将我的基数从recursion转换为迭代函数？ 内存和执行速度。
目标
- 我希望这些答案能帮助我在基准testing中获得20-30％的性能提升。
澄清/注意事项
- “DEFINE FAST”我更喜欢在所有现代浏览器上运行良好的一般情况，但是如果有一个浏览器特定的优化，使得可以接受的显着改进。
- sorting可能是服务器端，但我宁愿避免这个，因为JS应用程序可能会成为一个独立的（配对一些现成的专有应用程序，将传感器数据stream到一个文件）。
- JavaScript可能不是最好的语言，但这是一个要求。
- 我已经问过这个问题https://stackoverflow.com/questions/7111525/fastest-way-to-sort-integer-arrays-in-javascript不正确的答案是投了票，问题被closures。
- 我试图使用多个浏览器窗口实例作为临时multithreading; 它没有泛滥。 我会有兴趣在产生多个窗口的并发性有用的信息。
我testing过types化数组 ，QSIP版本在现代浏览器中似乎很好：
200万个元素
QSIP_TYPED | RDXIP_TYPED | QSIP_STD | RDXIP_STD ---------------------------------------------------------- Chrome | 300 1000 600 1300 Firefox | 550 1500 800 1600
支持 （ 来源： http ： //caniuse.com/typedarrays ）：
IE 10+ | FF 4+ | Chrome 7+ | Safari 5.1+ | Opera 11.6+
您是否考虑过使用最大化caching的algorithm组合？ 我在基准testing中看到，当子arrays变小时，您将切换到插入sorting。 一个有趣的方法是改为heapsort。 与quicksort结合使用，可以将最坏的情况归结为O（nlog（n））而不是O（n ^ 2）。 看看Introsort 。
我摆弄你的基准，并添加我自己的sortingfunction。 它和radixsort一样，但它的思想（和实现）更简单，就像一个基数，但是在二进制中，所以你只有两个存储桶，可以在原地进行。 看看http://jsfiddle.net/KaRV9/7/ 。
我把我的代码放在“Quicksort in place”（因为它与quicksort非常相似，只是透过其他方式select了pivot）。 运行他们几次，在我的Chrome 15他们执行如此接近，无法区分他们。
我不打算评论你的sortingalgorithm。 你比我更了解这些。
但一个好主意是使用networking工作者。 这允许你的sorting在它自己的线程中运行在后台，因此不会阻塞这个接口。 不pipe怎样，这都是好的做法。 Chrome和Firefox支持得很好。 Opera有一个非线程版本。 不确定在IE中的支持，但很容易解决这个问题。 当然，使用multithreading会涉及很多开销。
合并sorting可以很容易地变成一个multithreading版本，这会给你一些性能提升。 消息传递带来了时间上的损失，所以如果运行速度更快的话，它将取决于你的具体情况。 请记住，非阻塞性质可能会让应用程序对于最终用户来说运行得更快。
编辑：我看到你已经使用插入sorting较小的子arrays。 我错过了。
使用quicksort的现实世界方法是检查子数组的大小，如果足够短，则使用快速低开销sorting，对于较大的数组（如插入sorting）来说太慢。
伪代码是沿着以下方向的东西：
quicksort(array, start, end): if ( (end-start) < THRESHOLD ) { insertion_sort(array, start, end); return; } // regular quicksort here // ...
要确定THRESHOLD，你需要在你关心的平台上计算它，在你的情况下 – 可能是不同的浏览器。 测量具有不同阈值的随机arrays的时间以find接近最佳的一个。 如果您发现显着差异，您也可以为不同的浏览器select不同的阈值。
现在，如果您的input不是真正的随机（这是很常见的），你可以看到更好的枢轴select提高性能。 常用的方法是三位的中位数 。
