javascript中快速稳定的排序算法实现

javascript中快速稳定的排序算法实现

我正在寻找一个大约200-300个对象的数组,对特定的键和给定的顺序(asc / desc)进行排序。结果的顺序必须一致且稳定。

什么是最好的算法,你能提供一个在javascript中实现它的例子吗?

谢谢!


忽然笑
浏览 730回答 3
3回答

米脂

我知道这个问题已经回答了一段时间,但我碰巧在我的剪贴板中有一个很好的稳定合并排序实现Array和jQuery,所以我将分享它,希望未来的一些搜索者可能会觉得它很有用。它允许您像正常Array.sort实现一样指定自己的比较函数。履行//&nbsp;Add&nbsp;stable&nbsp;merge&nbsp;sort&nbsp;to&nbsp;Array&nbsp;and&nbsp;jQuery&nbsp;prototypes//&nbsp;Note:&nbsp;We&nbsp;wrap&nbsp;it&nbsp;in&nbsp;a&nbsp;closure&nbsp;so&nbsp;it&nbsp;doesn't&nbsp;pollute&nbsp;the&nbsp;global//&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;namespace,&nbsp;but&nbsp;we&nbsp;don't&nbsp;put&nbsp;it&nbsp;in&nbsp;$(document).ready,&nbsp;since&nbsp;it's//&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;not&nbsp;dependent&nbsp;on&nbsp;the&nbsp;DOM(function()&nbsp;{ &nbsp;&nbsp;//&nbsp;expose&nbsp;to&nbsp;Array&nbsp;and&nbsp;jQuery &nbsp;&nbsp;Array.prototype.mergeSort&nbsp;=&nbsp;jQuery.fn.mergeSort&nbsp;=&nbsp;mergeSort; &nbsp;&nbsp;function&nbsp;mergeSort(compare)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;length&nbsp;=&nbsp;this.length, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;middle&nbsp;=&nbsp;Math.floor(length&nbsp;/&nbsp;2); &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(!compare)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;compare&nbsp;=&nbsp;function(left,&nbsp;right)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(left&nbsp;<&nbsp;right) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;-1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(left&nbsp;==&nbsp;right) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(length&nbsp;<&nbsp;2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;this; &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;merge( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;this.slice(0,&nbsp;middle).mergeSort(compare), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;this.slice(middle,&nbsp;length).mergeSort(compare), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;compare&nbsp;&nbsp;&nbsp;&nbsp;); &nbsp;&nbsp;} &nbsp;&nbsp;function&nbsp;merge(left,&nbsp;right,&nbsp;compare)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;result&nbsp;=&nbsp;[]; &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(left.length&nbsp;>&nbsp;0&nbsp;||&nbsp;right.length&nbsp;>&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(left.length&nbsp;>&nbsp;0&nbsp;&&&nbsp;right.length&nbsp;>&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(compare(left[0],&nbsp;right[0])&nbsp;<=&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result.push(left[0]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;left&nbsp;=&nbsp;left.slice(1); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result.push(right[0]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;right&nbsp;=&nbsp;right.slice(1); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if&nbsp;(left.length&nbsp;>&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result.push(left[0]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;left&nbsp;=&nbsp;left.slice(1); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if&nbsp;(right.length&nbsp;>&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result.push(right[0]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;right&nbsp;=&nbsp;right.slice(1); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;result; &nbsp;&nbsp;}})();示例用法var&nbsp;sorted&nbsp;=&nbsp;[ &nbsp;&nbsp;'Finger', &nbsp;&nbsp;'Sandwich', &nbsp;&nbsp;'sandwich', &nbsp;&nbsp;'5&nbsp;pork&nbsp;rinds', &nbsp;&nbsp;'a&nbsp;guy&nbsp;named&nbsp;Steve', &nbsp;&nbsp;'some&nbsp;noodles', &nbsp;&nbsp;'mops&nbsp;and&nbsp;brooms', &nbsp;&nbsp;'Potato&nbsp;Chip&nbsp;Brand®&nbsp;chips'].mergeSort(function(left,&nbsp;right)&nbsp;{ &nbsp;&nbsp;lval&nbsp;=&nbsp;left.toLowerCase(); &nbsp;&nbsp;rval&nbsp;=&nbsp;right.toLowerCase(); &nbsp;&nbsp;console.log(lval,&nbsp;rval); &nbsp;&nbsp;if&nbsp;(lval&nbsp;<&nbsp;rval) &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;-1; &nbsp;&nbsp;else&nbsp;if&nbsp;(lval&nbsp;==&nbsp;rval) &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0; &nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;1;});sorted&nbsp;==&nbsp;["5&nbsp;pork&nbsp;rinds",&nbsp;"a&nbsp;guy&nbsp;named&nbsp;Steve",&nbsp;"Finger",&nbsp;"mops&nbsp;and&nbsp;brooms",&nbsp;"Potato&nbsp;Chip&nbsp;Brand®&nbsp;chips",&nbsp;"Sandwich",&nbsp;"sandwich",&nbsp;"some&nbsp;noodles"];
打开App,查看更多内容
随时随地看视频慕课网APP