{"id":10006964,"date":"2022-12-14T17:05:46","date_gmt":"2022-12-14T09:05:46","guid":{"rendered":"https:\/\/ityet.com\/?p=10006964"},"modified":"2022-12-14T17:05:46","modified_gmt":"2022-12-14T09:05:46","slug":"%e4%b8%8d%e5%a5%bd%e6%84%8f%e6%80%9d%ef%bc%81%f0%9f%8d%8e%e6%88%91%e7%9c%9f%e7%9a%84%e5%8f%aa%e4%bc%9a%e7%94%a8-array-prototype-sort-%e5%86%99%e2%9c%8d%e6%8e%92%e5%ba%8f%ef%bc%81","status":"publish","type":"post","link":"https:\/\/itmax.cn\/?p=10006964","title":{"rendered":"\u4e0d\u597d\u610f\u601d\uff01\ud83c\udf4e\u6211\u771f\u7684\u53ea\u4f1a\u7528 Array.prototype.sort() \u5199\u270d\u6392\u5e8f\uff01"},"content":{"rendered":"<p>\u672c\u6587\u53c2\u4e0e\u4e86 <a href=\"https:\/\/segmentfault.com\/a\/1190000042923114\">SegmentFault \u601d\u5426\u5e74\u5ea6\u5f81\u6587\u300c\u4e00\u540d\u6280\u672f\u4eba\u7684 2022\u300d<\/a>\uff0c\u6b22\u8fce\u6b63\u5728\u9605\u8bfb\u7684\u4f60\u4e5f\u52a0\u5165\u3002<\/p>\n<h2>\u524d\u8a00<\/h2>\n<p>\u4ec0\u4e48\u662f\u6392\u5e8f\uff1f\u6392\u5e8f\u5728 JavaScript \u4e2d\u5bf9\u4e8e\u5927\u90e8\u5206\u4eba\u6765\u8bb2\u662f\u8fd9\u6837\u7684\uff1a<\/p>\n<pre><code class=\"js\">arr.sort() \/\/ \u9ed8\u8ba4\u6392\u5e8f\uff0c\u4f1a\u5c06\u5143\u7d20\u8f6c\u6362\u4e3a\u5b57\u7b26\u4e32\uff0c\u7136\u540e\u6bd4\u8f83\u5b83\u4eec\u7684 UTF-16 \u4ee3\u7801\u5355\u5143\u503c\u5b9e\u73b0\u6392\u5e8f\narr.sort((a, b) =&gt; { return a - b }) \/\/ \u81ea\u5b9a\u4e49\u6392\u5e8f\uff0c\u9012\u589e\narr.sort((a, b) =&gt; { return b - a }) \/\/ \u81ea\u5b9a\u4e49\u6392\u5e8f\uff0c\u9012\u51cf<\/code><\/pre>\n<p>\u6709\u6bdb\u75c5\u5417\uff1f\u6ca1\u6bdb\u75c5\uff01\u4f46\u771f\u7684\u53ea\u662f\u8fd9\u6837\u5417\uff1f<\/p>\n<p><img decoding=\"async\" referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/bVc4J0V\" alt=\"23BEC8A5.jpg\" title=\"23BEC8A5.jpg\" loading=\"lazy\"><\/p>\n<p>\u6b7b\u4ea1\u8fde\u95ee\u7cfb\u5217\uff1a<\/p>\n<ul>\n<li>\u4e0d\u7528 sort() \u600e\u4e48\u5199\u6392\u5e8f\uff1f<\/li>\n<li>\u6709\u6ca1\u6709\u4e86\u89e3\u8fc7 sort() \u7684\u539f\u7406\uff1f<\/li>\n<li>\u4f60\u8fd8\u77e5\u9053\u54ea\u4e9b\u6392\u5e8f\u7b97\u6cd5\uff1f<\/li>\n<li>\u8fd9\u4e9b\u6392\u5e8f\u7b97\u6cd5\u90fd\u6709\u54ea\u4e9b\u533a\u522b\u5440\uff1f<\/li>\n<\/ul>\n<p><strong>\u4e0d\u597d\u610f\u601d\uff01\ud83c\udf4e\u6211\u771f\u7684\u53ea\u4f1a\u7528 Array.prototype.sort() \u5199\u270d\u6392\u5e8f\uff01<\/strong> \u5927\u90e8\u5206\u4eba\u7b2c\u4e00\u53cd\u5e94\u7edd\u5bf9\u662f\u4e1a\u52a1\u4e2d\u786e\u5b9e\u4e0d\u9700\u8981\u81ea\u5df1\u5199\u6392\u5e8f\u7b97\u6cd5\u5440\uff01\u95ee\u8fd9\u4e9b\u95ee\u9898\u5e72\u561b\uff01\uff08<del><code>\u4f60\u731c\u731c<\/code><\/del>\uff09<\/p>\n<p>\u5c31\u597d\u50cf\u4e70\u4e1c\u897f\uff0c\u6709\u4eba\u89c9\u5f97\u80fd\u89e3\u51b3\u5f53\u524d\u95ee\u9898\u5c31\u884c\uff0c\u6709\u4eba\u89c9\u5f97\u65e2\u53ef\u4ee5\u89e3\u51b3\u5f53\u524d\u95ee\u9898\u53c8\u53ef\u4ee5\u89e3\u51b3\u5176\u4ed6\u95ee\u9898\u624d\u884c\uff0c\u4e3a\u4ec0\u4e48\uff1f\u6ca1\u6709\u4e3a\u4ec0\u4e48\uff0c\u9762\u8bd5\u5b98\u4e5f\u6709\u4e0d\u540c\u7684\u9700\u6c42\uff01<img decoding=\"async\" referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/bVc4J0X\" alt=\"23BF0C55.png\" title=\"23BF0C55.png\" loading=\"lazy\"><\/p>\n<p>\u4e0b\u9762\u6211\u4eec\u5c31\u4ece\u4ee5\u4e0b\u4e24\u4e2a\u65b9\u9762\u6765\u804a\u4e00\u804a\uff1a<\/p>\n<ul>\n<li><strong>\u5e38\u89c1\u7684\u6392\u5e8f\u7b97\u6cd5<\/strong><\/li>\n<li><strong>Array.prototype.sort() \u7684\u539f\u7406<\/strong><\/li>\n<\/ul>\n<h2>\u5e38\u89c1\u7684\u6392\u5e8f\u7b97\u6cd5<\/h2>\n<p>\u5e38\u89c1\u6392\u5e8f\u7b97\u6cd5\u4e3b\u8981\u5305\u542b\u5982\u4e0b 5 \u79cd:<\/p>\n<ul>\n<li>\u5192\u6ce1\u6392\u5e8f<\/li>\n<li>\u9009\u62e9\u6392\u5e8f<\/li>\n<li>\u63d2\u5165\u6392\u5e8f<\/li>\n<li>\u5f52\u5e76\u6392\u5e8f<\/li>\n<li>\u5feb\u901f\u6392\u5e8f<\/li>\n<\/ul>\n<p>\u5982\u679c\u4f60\u8fd8\u5728\u6b7b\u8bb0\u6240\u8c13\u7684\u6a21\u677f\uff0c\u4e0d\u51fa\u610f\u5916\u7684\u8bdd\u4f1a\u4e09\u756a\u4e24\u6b21\u7684\u9057\u5fd8\uff0c\u4e0d\u5982\u7ed9\u81ea\u5df1\u4e00\u70b9\u65f6\u95f4\u53bb\u4e86\u89e3\u5176\u6838\u5fc3\u7684\u601d\u60f3\uff0c\u771f\u6b63\u505a\u5230\u8ba9 <strong>\u6838\u5fc3\u601d\u60f3<\/strong> \u5e26\u7740\u4f60\u628a\u4ee3\u7801\u5199\u51fa\u6765\uff01<\/p>\n<h3>\u5192\u6ce1\u6392\u5e8f \u2014 normal \u7248\u672c<\/h3>\n<p><strong>\u65f6\u95f4\u590d\u6742\u5ea6\uff1a<code>O(n^2)<\/code><\/strong><\/p>\n<h4>\u6838\u5fc3\u601d\u60f3<\/h4>\n<p>\u6240\u8c13\u7684 <strong>\u5192\u6ce1<\/strong> \u5176\u5b9e\u5c31\u662f\u5728 <strong>\u6bcf\u4e00\u8f6e\u7684\u904d\u5386<\/strong> \u4e2d\u9009\u51fa\u4e00\u4e2a <strong>\u6700\u503c\uff08\u6700\u5c0f\/\u6700\u5927\uff09<\/strong> \u503c\u79fb\u52a8\u5230\u6570\u7ec4\u7684 <strong>\u4e24\u7aef\uff08\u6700\u5de6\u7aef\/\u6700\u53f3\u7aef\uff09<\/strong>\u3002<\/p>\n<p>\u57fa\u4e8e <strong><code>\u6700\u5927\u503c\u5192\u6ce1<\/code><\/strong> \u53ef\u4ee5\u7406\u89e3\u4e3a\uff0c\u4ece\u7b2c\u4e00\u4e2a\u5143\u7d20\u5f00\u59cb\uff0c<strong><code>\u91cd\u590d\u6bd4\u8f83\u76f8\u90bb\u7684\u4e24\u4e2a\u5143\u7d20<\/code><\/strong>\uff1a<\/p>\n<ul>\n<li>\u5982\u679c <strong><code>\u524d\u4e00\u9879\u5143\u7d20 &gt; \u540e\u4e00\u9879\u5143\u7d20<\/code><\/strong>\uff0c\u5219\u4ea4\u6362\u5b83\u4eec\u7684\u4f4d\u7f6e<\/li>\n<li>\u5426\u5219 <strong><code>\u4e0d\u4ea4\u6362<\/code><\/strong>\uff0c\u7ee7\u7eed\u6bd4\u5bf9\u540e\u7eed\u7684\u5143\u7d20<\/li>\n<\/ul>\n<p>\u57fa\u4e8e <strong><code>\u6700\u5c0f\u503c\u5192\u6ce1<\/code><\/strong> \u53ef\u4ee5\u7406\u89e3\u4e3a\uff0c\u4ece\u7b2c\u4e00\u4e2a\u5143\u7d20\u5f00\u59cb\uff0c<strong><code>\u91cd\u590d\u6bd4\u8f83\u540e\u7eed\u7684\u5143\u7d20<\/code><\/strong>\uff1a<\/p>\n<ul>\n<li>\u5982\u679c <strong><code>\u5934\u90e8\u5143\u7d20 &gt; \u540e\u7eed\u5143\u7d20<\/code><\/strong>\uff0c\u5219\u4ea4\u6362\u5b83\u4eec\u7684\u4f4d\u7f6e<\/li>\n<li>\u5426\u5219 <strong><code>\u4e0d\u4ea4\u6362<\/code><\/strong>\uff0c\u7ee7\u7eed\u6bd4\u5bf9\u540e\u7eed\u7684\u5143\u7d20<\/li>\n<\/ul>\n<p><img decoding=\"async\" referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/bVc4JZP\" alt=\"\" title=\"\" loading=\"lazy\"><\/p>\n<h4>JavaScript \u5b9e\u73b0<\/h4>\n<p>\u5982\u4e0b\u662f\u9009\u62e9\u6bcf\u6b21\u904d\u5386\u7684 <strong>\u6700\u5927\u503c<\/strong> \u79fb\u52a8\u7aef\u6570\u7ec4\u7684 <strong>\u6700\u53f3\u7aef<\/strong> \u6765\u5b9e\u73b0 <strong>\u5192\u6ce1<\/strong>\uff1a<\/p>\n<pre><code class=\"js\">export function bubbleSort(arr) {\n  const len = arr.length;\n\n  \/\/ \u5916\u5c42\u904d\u5386\u8d1f\u8d23\u4ece\u5934\u5230\u5c3e\u8fdb\u884c\u6bd4\u8f83\n  for (let i = 0; i &lt; len; i++) {\n    for (let j = 0; j &lt; len; j++) {\n      \/\/ \u82e5\u76f8\u90bb\u5143\u7d20\u524d\u9762\u7684\u6570\u6bd4\u540e\u9762\u7684\u5927\uff0c\u5219\u4ea4\u6362\n      if (arr[j] &gt; arr[j + 1]) {\n        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];\n      }\n    }\n  }\n  \n  return arr;\n}<\/code><\/pre>\n<p>\u5982\u4e0b\u662f\u9009\u62e9\u6bcf\u6b21\u904d\u5386\u7684 <strong>\u6700\u5c0f\u503c<\/strong> \u79fb\u52a8\u7aef\u6570\u7ec4\u7684 <strong>\u6700\u5de6\u7aef<\/strong> \u6765\u5b9e\u73b0 <strong>\u5192\u6ce1<\/strong>\uff1a<\/p>\n<pre><code class=\"js\">export function bubbleSort(arr) {\n  const len = arr.length;\n  \n  \/\/ \u5916\u5c42\u5faa\u73af\u8d1f\u8d23\u4ece\u524d\u5f80\u540e\u904d\u5386\u6570\u7ec4\u5143\u7d20\uff0c\u6bcf\u6b21\u904d\u5386\u65f6\u627e\u51fa\u6bd4\u5b83\u5c0f\u7684\u548c\u5b83\u66ff\u6362\n  for (let i = 0; i &lt; len; i++) {\n      \/\/ \u5f53\u5185\u5c42\u5faa\u73af\u904d\u5386\u5b8c\u4e00\u6b21\u6570\u7ec4\uff0c\u5c31\u80fd\u627e\u51fa\u672c\u6b21\u904d\u5386\u4e2d\u7684\u6700\u5c0f\u503c\uff0c\u5e76\u628a\u6700\u5c0f\u503c\u79fb\u52a8\u5230\u6570\u7ec4\u5934\u90e8\n       for (let j = i + 1; j &lt; len; j++) {\n           \/\/ \u53ea\u8981\u5f53\u524d\u5934\u90e8\u5143\u7d20\u5927\u4e8e\u540e\u7eed\u4efb\u610f\u5143\u7d20\u5c31\u76f4\u63a5\u4ea4\u6362\u4f4d\u7f6e\n           if (arr[i] &gt; arr[j]) {\n               [arr[i], arr[j]] = [arr[j], arr[i]]\n           }\n       }\n   }\n\n  return arr;\n}<\/code><\/pre>\n<h3>\u5192\u6ce1\u6392\u5e8f \u2014 better \u7248\u672c<\/h3>\n<p><strong>\u65f6\u95f4\u590d\u6742\u5ea6\uff1a<code>O(n^2)<\/code><\/strong><\/p>\n<h4>\u6838\u5fc3\u601d\u60f3<\/h4>\n<p>\u4ee5\u4e0a <strong>normal \u7248\u672c<\/strong> \u7684\u5b9e\u73b0\u662f\u6700\u57fa\u672c\u7684\u5b9e\u73b0\uff0c\u53ea\u8003\u8651\u6838\u5fc3\u601d\u60f3\uff0c\u6ca1\u6709\u8003\u8651\u91cd\u590d\u6bd4\u8f83\u7684\u95ee\u9898\uff0c\u6bd4\u5982\u57fa\u4e8e <strong>\u6700\u5927\u503c\u5192\u6ce1<\/strong> \u7684\u65b9\u5f0f\u4e2d\u4f7f\u7528\u5230\u7684\u6838\u5fc3\u4ee3\u7801\u4e3a\uff1a<\/p>\n<pre><code class=\"js\">\/\/ \u5916\u5c42\u904d\u5386\u8d1f\u8d23\u4ece\u5934\u5230\u5c3e\u8fdb\u884c\u6bd4\u8f83\n  for (let i = 0; i &lt; len; i++) {\n    for (let j = 0; j &lt; len; j++) {\n      \/\/ \u82e5\u76f8\u90bb\u5143\u7d20\u524d\u9762\u7684\u6570\u6bd4\u540e\u9762\u7684\u5927\uff0c\u5219\u4ea4\u6362\n      if (arr[j] &gt; arr[j + 1]) {\n        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];\n      }\n    }\n  }<\/code><\/pre>\n<p>\u91cc\u9762\u7528\u5230\u7684 <strong>\u53cc\u91cd\u5faa\u73af<\/strong> \u4e2d\u7684\u5185\u5c42\u5faa\u73af\u6bcf\u6b21\u90fd\u53ea\u662f\u7b80\u5355\u7684\u4ece\u5934\u904d\u5386\u5230\u5c3e\uff0c\u4f46\u662f\u771f\u7684\u6709\u5fc5\u8981\u5417\uff1f<\/p>\n<p>\u524d\u9762\u6838\u5fc3\u601d\u60f3\u90e8\u5206\u6211\u4eec\u662f\u4e0d\u662f\u8bb2\u8fc7\uff0c<strong>\u5185\u5c42\u5faa\u73af\u6bcf\u6b21\u904d\u5386\u7ed3\u675f\u540e\uff0c\u672c\u6b21\u904d\u5386\u7684\u6700\u5927\u503c\u5c31\u4f1a\u88ab\u79fb\u52a8\u5230\u6570\u7ec4\u5c3e\u90e8<\/strong>\uff0c\u5373\u5982\u4e0b\uff1a<\/p>\n<ul>\n<li>\u7b2c 1 \u6b21\u5185\u5c42\u5faa\u73af\u904d\u5386\u7ed3\u675f\uff0c\u5f97\u5230 <strong><code>\u7b2c n \u5927\u503c<\/code><\/strong><\/li>\n<li>\u7b2c 2 \u6b21\u5185\u5c42\u5faa\u73af\u904d\u5386\u7ed3\u675f\uff0c\u5f97\u5230 <strong><code>\u7b2c n-1 \u5927\u503c<\/code><\/strong><\/li>\n<li>\u7b2c 3 \u6b21\u5185\u5c42\u5faa\u73af\u904d\u5386\u7ed3\u675f\uff0c\u5f97\u5230 <strong><code>\u7b2c n-2 \u5927\u503c<\/code><\/strong><\/li>\n<li>&#8230;&#8230;<\/li>\n<li>\u7b2c n \u6b21\u5185\u5c42\u5faa\u73af\u904d\u5386\u7ed3\u675f\uff0c\u5f97\u5230 <strong><code>\u7b2c 1 \u5927\u503c<\/code><\/strong> \u6216 <strong><code>\u6700\u5c0f\u503c<\/code><\/strong><\/li>\n<\/ul>\n<p>\u8fd9\u5c31\u5f15\u51fa\u4e86\u503c\u5f97\u4f18\u5316\u7684\u70b9\uff0c\u5c31\u662f\u6bcf\u6b21\u5185\u5c42\u5faa\u73af\u904d\u5386\u65f6\uff0c\u5c31\u53ea\u9700\u8981\u6bd4\u8f83 n &#8211; i \u4e4b\u524d\u7684\u5143\u7d20\uff0c\u56e0\u4e3a\u4ece n &#8211; i \u5230 n \u7684\u5143\u7d20\u90fd\u5df2\u7ecf\u6709\u5e8f\u4e86\u3002<\/p>\n<h4>JavaScript \u5b9e\u73b0<\/h4>\n<pre><code class=\"js\">export function betterBubbleSort(arr) {\n  const len = arr.length;\n\n  for (let i = 0; i &lt; len; i++) {\n    \/\/ len - i \u907f\u514d\u904d\u5386\u5230\u5df2\u7ecf\u6709\u5e8f\u7684\u90e8\u5206\n    for (let j = 0; j &lt; len - i; j++) {\n      if (arr[j] &gt; arr[j + 1]) {\n        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];\n      }\n    }\n  }\n\n  return arr;\n}<\/code><\/pre>\n<h3>\u5192\u6ce1\u6392\u5e8f \u2014 best \u7248\u672c<\/h3>\n<p><strong>\u65f6\u95f4\u590d\u6742\u5ea6\uff1a<code>O(n) \u2014\u2014 O(n^2)<\/code><\/strong><\/p>\n<h4>\u6838\u5fc3\u601d\u60f3<\/h4>\n<p>\u4ee5\u4e0a <strong>better \u7248\u672c<\/strong> \u7684\u5b9e\u73b0\u5df2\u7ecf\u662f\u4f18\u5316\u5185\u5c42\u5faa\u73af\u7684\u904d\u5386\u6b21\u6570\uff0c\u4f46\u662f\u8fd8\u6709\u4e00\u79cd\u60c5\u51b5\u4e0d\u5f97\u4e0d\u8003\u8651\uff0c\u90a3\u5c31\u662f\u4f20\u5165\u7684\u6570\u7ec4\u672c\u8eab\u5c31\u662f <strong>\u6709\u5e8f\u6570\u7ec4<\/strong> \u65f6\uff0c\u6309\u6b63\u5e38\u903b\u8f91\u6709\u5e8f\u6570\u7ec4\u5c31\u4e0d\u9700\u8981\u904d\u5386\u4e86\uff0c\u4f46\u662f JavaScript \u4e2d\u53ef\u6ca1\u6709\u63d0\u4f9b\u7ed9\u4f60\u4e00\u4e2a\u5565\u5c5e\u6027\u80fd\u591f\u6807\u8bc6\u5b83\u662f\u5426\u662f\u6709\u5e8f\u7684\uff0c\u56e0\u6b64\u8fd8\u662f\u5f97\u901a\u8fc7\u904d\u5386\u6570\u7ec4\u624d\u80fd\u77e5\u9053\u5b83\u5230\u5e95\u6709\u6ca1\u6709\u5e8f\u3002<\/p>\n<p>\u800c\u8fd9\u6837\u7684\u65b9\u5f0f\uff0c\u57fa\u4e8e <strong>better \u7248\u672c<\/strong> \u6765\u8bb2\uff0c\u5b83\u7684\u5185\u5c42\u5faa\u73af\u8be5\u904d\u5386\u591a\u5c11\u6b21\uff0c\u8fd8\u662f\u4f1a\u904d\u5386\u591a\u5c11\u6b21\uff0c\u5373\u4f7f\u4e00\u6b21\u4e5f\u6ca1\u6709\u53d1\u751f\u8fc7\u4ea4\u6362\u64cd\u4f5c\u3002<\/p>\n<p>\u90a3\u600e\u4e48\u529e\uff1f\u600e\u4e48\u6807\u8bc6\u4e00\u4e2a\u6570\u7ec4\u662f\u4e0d\u662f\u6709\u5e8f\u7684\u5462\uff1f<\/p>\n<p>\u6211\u4eec\u77e5\u9053\u53ea\u8981\u5185\u5c42\u5faa\u73af\u4e2d\u8fdb\u5165\u4ea4\u4e92\u64cd\u4f5c\u7684\u6761\u4ef6\u5206\u652f\uff0c\u90a3\u4e48\u8bc1\u660e\u6570\u7ec4\u5fc5\u7136\u662f\u65e0\u5e8f\u7684\uff0c\u56e0\u6b64\u53ef\u4ee5\u5b9a\u4e49\u4e00\u4e2a <strong><code>isOrder<\/code><\/strong> \u7528\u4e8e\u6807\u8bc6\u6570\u7ec4\u662f\u5426\u6709\u5e8f\uff0c<strong>\u9ed8\u8ba4\u6570\u7ec4\u662f\u6709\u5e8f\u7684<\/strong>\uff0c\u76f4\u63a5\u5411\u5916\u8fdb\u884c\u8fd4\u56de\u5373\u53ef\uff1b\u4f46\u53ea\u8981\u53d1\u751f\u4ea4\u6362\u64cd\u4f5c\uff0c\u5c31\u5c06 <strong><code>isOrder<\/code><\/strong> \u7684\u503c\u6539\u53d8\uff0c\u8bc1\u660e <strong>\u5f53\u524d\u6570\u7ec4\u662f\u65e0\u5e8f<\/strong> \u7684\uff0c\u9700\u8981\u7ee7\u7eed\u5f80\u540e\u8fdb\u884c\u5224\u65ad\u3002<\/p>\n<p>\u8fd9\u6837\u4e00\u6765\uff0c\u5f53\u4f20\u5165\u6570\u7ec4\u662f\u6709\u5e8f\u65f6\uff0c\u53ea\u9700\u8981\u5916\u5c42\u5faa\u73af\u6267\u884c 1 \u6b21\uff0c\u5185\u5c42\u5faa\u73af\u6267\u884c n \u6b21\uff0c\u5c31\u53ef\u4ee5\u5224\u65ad\u51fa\u5f53\u524d\u6570\u7ec4\u662f\u5426\u6709\u5e8f\uff0c\u56e0\u6b64 <strong>\u6700\u597d\u7684\u60c5\u51b5\u4e0b\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a <code>O(n)<\/code>\uff0c\u6700\u574f\u60c5\u51b5\u4e0b\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a <code>O(n^2)<\/code><\/strong>\u3002<\/p>\n<h4>JavaScript \u5b9e\u73b0<\/h4>\n<pre><code class=\"js\">export function bestBubbleSort(arr) {\n  const len = arr.length;\n  \/\/ \u5b9a\u4e49 isOrder \u7528\u4e8e\u6807\u8bc6\u6570\u7ec4\u662f\u5426\u6709\u5e8f\uff0c\u9ed8\u8ba4\u662f\u6709\u5e8f\u7684\n  let isOrder = true;\n\n  for (let i = 0; i &lt; len; i++) {\n    for (let j = 0; j &lt; len - i; j++) {\n      if (arr[j] &gt; arr[j + 1]) {\n        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];\n        isOrder = false;\n      }\n    }\n\n    \/\/ isOrder \u7684\u503c\u6ca1\u6709\u53d1\u751f\u66f4\u6539\uff0c\u610f\u5473\u7740\u6570\u7ec4\u662f\u6709\u5e8f\u7684\uff0c\u4e0d\u9700\u8981\u8fdb\u884c\u989d\u5916\u6392\u5e8f\n    if (isOrder) return arr;\n  }\n\n  return arr;\n}<\/code><\/pre>\n<h3>\u9009\u62e9\u6392\u5e8f<\/h3>\n<p><strong>\u65f6\u95f4\u590d\u6742\u5ea6\uff1a<code>O(n^2)<\/code><\/strong><\/p>\n<h4>\u6838\u5fc3\u601d\u60f3<\/h4>\n<p>\u6240\u8c13 <strong>\u9009\u62e9<\/strong> \u5c31\u662f\u9009\u62e9 <strong>\u6700\u503c\uff08\u6700\u5927\/\u6700\u5c0f\uff09<\/strong>\uff0c\u5c31\u662f\u6bcf\u6b21\u904d\u5386\u786e\u5b9a <strong>\u6700\u5c0f\u503c\u7d22\u5f15<\/strong>\uff0c\u6bcf\u8f6e\u904d\u5386\u7ed3\u675f\u628a <strong>\u6700\u5c0f\u503c\u653e\u5230\u6570\u7ec4\u5934\u90e8<\/strong>\uff08\u7531\u4e8e\u4e0a\u9762\u6211\u4eec\u5df2\u7ecf\u6f14\u793a\u8fc7\u4e0d\u540c\u6700\u503c\u7684\u5b9e\u73b0\u65b9\u5f0f\uff0c\u8003\u8651\u5230\u7bc7\u5e45\uff0c\u8fd9\u91cc\u6211\u4eec\u5c31\u4ee5\u6700\u5c0f\u503c\u7684\u5f62\u5f0f\u6765\u770b\u770b\uff09\u3002<\/p>\n<p><img decoding=\"async\" referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/bVc4JZ6\" alt=\"\" title=\"\" loading=\"lazy\"><\/p>\n<h4>JavaScript \u5b9e\u73b0<\/h4>\n<p>\u770b\u7740\u4e0b\u9762\u7684\u5b9e\u73b0\uff0c\u4e0d\u77e5\u9053\u4f60\u4f1a\u4e0d\u4f1a\u53d1\u73b0\uff0c\u8fd9\u548c\u6211\u4eec\u524d\u9762\u8bb2\u7684 <strong>\u57fa\u4e8e \u6700\u5c0f\u503c \u5192\u6ce1<\/strong> \u7684\u5b9e\u73b0\u65b9\u5f0f\u5f88\u7c7b\u4f3c\uff0c\u53ea\u662f\u5982\u4e0b\u7684\u65b9\u5f0f\u591a\u4e86 <strong>\u6700\u5c0f\u503c\u7d22\u5f15 minIdx<\/strong>\uff0c\u5e76\u4e14\u4ea4\u6362\u64cd\u4f5c\u662f\u53d1\u751f\u5728 <strong>\u5185\u5c42\u5faa\u73af\u7ed3\u675f\u540e<\/strong>\uff0c\u800c\u524d\u8005\u662f\u5728 <strong>\u5185\u5c42\u5faa\u73af\u4e2d<\/strong> \u8fdb\u884c\u7684\u4ea4\u6362\u64cd\u4f5c\u3002<\/p>\n<pre><code class=\"js\">export function selectSort(arr) {\n  const len = arr.length;\n\n  \/\/ \u5b9a\u4e49\u6700\u5c0f\u503c\u7d22\u5f15\n  let minIdx;\n\n  for (let i = 0; i &lt; len; i++) {\n    \/\/ \u5c06\u6bcf\u6b21\u5faa\u73af\u7d22\u5f15 i \u8ba4\u4e3a\u662f\u672c\u6b21\u904d\u5386\u7684 \u6700\u5c0f\u503c\u7d22\u5f15 minIdx\n    minIdx = i;\n\n    \/\/ i\u3001j \u5b9a\u4e49\u4e3a\u672c\u6b21\u9700\u8981\u904d\u5386\u533a\u95f4\u7684 \u8fb9\u754c\uff0ci \u4e3a \u5de6\u8fb9\u754c\uff0cj \u4e3a \u53f3\u8fb9\u754c\n    for (let j = i; j &lt; len; j++) {\n      if (arr[j] &lt; arr[minIdx]) {\n        minIdx = j;\n      }\n    }\n\n    \/\/ \u82e5\u5f53\u524d minIdx \u548c i \u4e0d\u76f8\u7b49\uff0c\u5219\u8868\u660e\u5f53\u524d\u5df2\u7ecf\u627e\u5230\u65b0\u7684\u6700\u5c0f\u7684\u5143\u7d20\uff0c\u5219\u8fdb\u884c\u4ea4\u6362\n    if (minIdx !== i) {\n      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];\n    }\n  }\n\n  return arr;\n}<\/code><\/pre>\n<h3>\u63d2\u5165\u6392\u5e8f<\/h3>\n<p><strong>\u65f6\u95f4\u590d\u6742\u5ea6\uff1a<code>O(n^2)<\/code><\/strong><\/p>\n<h4>\u6838\u5fc3\u601d\u60f3<\/h4>\n<p>\u6240\u8c13 <strong>\u63d2\u5165<\/strong> \u5c31\u662f\u6307\u5c06\u5f53\u524d\u904d\u5386\u5230\u7684\u5143\u7d20\u5f80 <strong>\u5df2\u6709\u5e8f\u7684\u90e8\u5206<\/strong> \u4e2d\u8fdb\u884c\u63d2\u5165\u52a8\u4f5c\uff0c\u5df2\u6709\u5e8f\u90e8\u5206\u4f60\u5927\u53ef\u4ee5\u9ed8\u8ba4\u6570\u7ec4\u7684 <strong>\u7b2c\u4e00\u4e2a\u5143\u7d20<\/strong> \u5c31\u662f <strong>\u5df2\u6709\u5e8f\u90e8\u5206<\/strong>\uff0c\u540e\u7eed\u904d\u5386\u7684\u5143\u7d20\u53ea\u8981\u4fdd\u8bc1\u5728\u524d\u9762\u5df2\u6709\u5e8f\u7684\u90e8\u5206\u4e2d\u627e\u5408\u9002\u7684\u4f4d\u7f6e\u8fdb\u884c\u63d2\u5165\u5373\u53ef\u3002<\/p>\n<p><img decoding=\"async\" referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/bVc4J0j\" alt=\"\" title=\"\" loading=\"lazy\"><\/p>\n<h4>JavaScript \u5b9e\u73b0<\/h4>\n<pre><code class=\"js\">export function insertSort(arr) {\n  const len = arr.length;\n\n  \/\/ temp \u7528\u6765\u4fdd\u5b58\u5f53\u524d\u9700\u8981\u63d2\u5165\u7684\u5143\u7d20\n  let temp;\n\n  \/\/ i = 1 \u5373\u9ed8\u8ba4\u7b2c\u4e00\u4f4d\u5143\u7d20\uff08\u5373 i = 0\uff09\u662f\u6709\u5e8f\u7684\n  for (let i = 1; i &lt; len; i++) {\n    \/\/ j \u7528\u4e8e\u5e2e\u52a9 temp \u5bfb\u627e\u81ea\u5df1\u5e94\u8be5\u6709\u7684\u5b9a\u4f4d\n    let j = i;\n    temp = arr[i];\n\n    \/\/ j \u6b64\u65f6\u4e3a\u6709\u5e8f\u533a\u57df\u7684 \u53f3\u8fb9\u754c\uff0c\u56e0\u6b64 j - 1 \u5c31\u662f\u6709\u5e8f\u533a\u57df\u4e2d\u7684\u5185\u5bb9\n    \/\/ \u5224\u65ad j \u524d\u9762\u4e00\u4e2a\u5143\u7d20\u662f\u5426\u6bd4 temp \u5927\n    while (arr[j - 1] &gt; temp) {\n      \/\/ \u5982\u679c\u662f\uff0c\u5219\u5c06 j \u524d\u9762\u7684\u4e00\u4e2a\u5143\u7d20\u540e\u79fb\u4e00\u4f4d\uff0c\u4e3a temp \u8ba9\u51fa\u4f4d\u7f6e\n      arr[j] = arr[j - 1];\n      j--;\n    }\n\n    \/\/ \u5faa\u73af\u8ba9\u4f4d\uff0c\u6700\u540e\u5f97\u5230\u7684 j \u5c31\u662f temp \u7684\u6b63\u786e\u7d22\u5f15\n    arr[j] = temp;\n  }\n\n  return arr;\n}<\/code><\/pre>\n<h3>\u5f52\u5e76\u6392\u5e8f<\/h3>\n<p><strong>\u65f6\u95f4\u590d\u6742\u5ea6\uff1a<code>O(nlog(n))<\/code><\/strong><\/p>\n<h4>\u6838\u5fc3\u601d\u60f3<\/h4>\n<p>\u6240\u8c13 <strong>\u5f52\u5e76<\/strong> \u7ffb\u8bd1\u8fc7\u6765\u5c31\u662f <strong>\u9012\u5f52 + \u5408\u5e76<\/strong>\uff0c <strong><code>\u9012\u5f52<\/code><\/strong> \u5c31\u662f\u7528\u4e8e\u5904\u7406\u76f8\u540c\u4e14\u91cd\u590d\u7684\u5185\u5bb9\uff0c\u90a3 <strong><code>\u5408\u5e76<\/code><\/strong> \u662f\u5408\u5e76\u4ec0\u4e48\uff01\u65e2\u7136 <strong>\u9700\u8981\u5408\u5e76<\/strong>\uff0c\u90a3\u610f\u5473\u7740 <strong>\u5148\u5f97\u5206\u5f00<\/strong>\uff0c\u5206\u8c01\uff1f\u5f53\u7136\u662f\u5c06\u6570\u7ec4\u5212\u5206\u6210\u5b50\u6570\u7ec4\u4e86\uff08<del><code>\u96be\u9053\u662f\u5206\u86cb\u7cd5\u5417<\/code><\/del>\uff09\uff0c\u5373\u53ea\u8981\u4fdd\u8bc1\u5b50\u6570\u7ec4\u6709\u5e8f\uff0c\u4e14\u4fdd\u8bc1\u5408\u5e76\u540e\u7684\u6570\u7ec4\u4e5f\u4fdd\u8bc1\u662f\u6709\u5e8f\u7684\uff0c\u90a3\u4e48\u6700\u540e\u4e00\u6b21\u5408\u5e76\u5f97\u5230\u7684\u6570\u7ec4\u81ea\u7136\u5c31\u662f\u6709\u5e8f\u7684\u3002<\/p>\n<p>\u8fd9\u5176\u5b9e\u662f <strong>\u5206\u800c\u6cbb\u4e4b<\/strong> \u7684\u601d\u60f3\uff0c\u6307\u7684\u662f <strong>\u5c06\u4e00\u4e2a\u5927\u95ee\u9898\u5206\u89e3\u4e3a\u82e5\u5e72\u4e2a\u5b50\u95ee\u9898\uff0c\u9488\u5bf9\u5b50\u95ee\u9898\u5206\u522b\u6c42\u89e3\u540e\uff0c\u518d\u5c06\u5b50\u95ee\u9898\u7684\u89e3\u6574\u5408\u4e3a\u5927\u95ee\u9898\u7684\u89e3<\/strong>\u3002<\/p>\n<p><img decoding=\"async\" referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/bVc4J0r\" alt=\"\" title=\"\" loading=\"lazy\"><\/p>\n<h4>JavaScript \u5b9e\u73b0<\/h4>\n<p><strong>\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u5206\u6790\uff1a<\/strong><\/p>\n<p>\u6bcf\u4e00\u8f6e\u9012\u5f52\uff0c\u90fd\u9700\u8981\u505a <strong>\u5207\u5206<\/strong> \u548c <strong>\u5408\u5e76<\/strong> \u64cd\u4f5c\uff0c\u5176\u4e2d\u5bf9\u4e8e <strong><code>n<\/code><\/strong>\u00a0\u7684\u6570\u7ec4\u6765\u8bf4\uff0c\u9700\u8981\u5207\u5206\u00a0<code>log2(n)<\/code>\u00a0\u6b21\uff0c\u800c\u5207\u5206\u7684\u5b9e\u9645\u52a8\u4f5c\u662f\u56fa\u5b9a\u7684\u5982\u4e0b\u4ee3\u7801\u6240\u793a\uff0c\u56e0\u6b64\u5176\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a <code>O(1)<\/code>\uff0c\u800c\u5728\u5408\u5e76\u64cd\u4f5c\u4e2d\u901a\u8fc7 <code>while<\/code> \u6765\u5b9e\u73b0\u4e24\u4e2a\u6570\u7ec4\u7684\u6709\u5e8f\u5408\u5e76\uff0c\u56e0\u6b64\u5176\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a <code>O(n)<\/code>\uff0c\u6240\u4ee5\u6700\u7ec8\u6574\u4f53\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a <code>O(nlog(n))<\/code>\u3002<\/p>\n<pre><code class=\"js\">\/\/ \u8ba1\u7b97\u5206\u5272\u70b9 \nconst mid = Math.floor(len \/ 2) \n\/\/ \u9012\u5f52\u5206\u5272\u5de6\u5b50\u6570\u7ec4\uff0c\u7136\u540e\u5408\u5e76\u4e3a\u6709\u5e8f\u6570\u7ec4 \nconst leftArr = mergeSort(arr.slice(0, mid)) \n\/\/ \u9012\u5f52\u5206\u5272\u53f3\u5b50\u6570\u7ec4\uff0c\u7136\u540e\u5408\u5e76\u4e3a\u6709\u5e8f\u6570\u7ec4 \nconst rightArr = mergeSort(arr.slice(mid,len))<\/code><\/pre>\n<blockquote><p><strong>log2(n)<\/strong> \u8868\u793a\u7684\u662f\u00a0<strong>\u4ee5 2 \u7684\u591a\u5c11\u6b21\u65b9\u7b49\u4e8e n<\/strong>\uff0c\u6570\u5b66\u4e0a\u53eb <strong>\u4ee5 2 \u4e3a\u5e95 n \u7684 \u5bf9\u6570<\/strong>\uff0c\u4f46\u5728\u65f6\u95f4\u590d\u6742\u5ea6\u4e2d\u4e00\u822c\u6d89\u53ca\u5e38\u6570\u90e8\u5206\u53ef\u4ee5\u76f4\u63a5\u5ffd\u7565\u4e0d\u8003\u8651\uff0c\u5373 <strong>log2(n)<\/strong> \u8868\u793a\u4e3a <strong>log(n)<\/strong><\/p><\/blockquote>\n<pre><code class=\"js\">export function mergeSort(arr) {\n  const len = arr.length;\n\n  \/\/ \u5b9a\u4e49\u9012\u5f52\u8fb9\u754c\n  if (len &lt;= 1) {\n    return arr;\n  }\n\n  \/\/ \u83b7\u53d6\u4e2d\u95f4\u5143\u7d20\u7684\u7d22\u5f15\u503c\n  const midIdx = Math.floor(len \/ 2);\n\n  \/\/ \u6839\u636e\u4e2d\u95f4\u7d22\u5f15 midIdx \u5212\u5206\u5de6\u53f3\u4e24\u4e2a\u5b50\u6570\u7ec4\uff0c\u5373\u8fdb\u884c\u4e86 \u5206\u5272\n  const left = mergeSort(arr.slice(0, midIdx));\n  const right = mergeSort(arr.slice(midIdx, len));\n\n  \/\/ \u5c06\u5de6\u53f3\u4e24\u4e2a\u5b50\u6570\u7ec4\u8fdb\u884c\u6709\u5e8f\u7684\u5408\u5e76\n  return mergeArr(left, right);\n}\n\n\/\/ \u901a\u8fc7\u53cc\u9488\u6307\u9488\u5408\u5e76\u4e24\u4e2a\u6709\u5e8f\u6570\u7ec4\nfunction mergeArr(arr1, arr2) {\n  const len1 = arr1.length;\n  const len2 = arr2.length;\n\n  \/\/ \u5b9a\u4e49 l r \u6307\u9488\uff0c\u5206\u522b\u6307\u5411 arr1 arr2 \u4e2d\u7684\u5143\u7d20\n  let i = 0,\n    j = 0;\n\n  \/\/ \u5b9a\u4e49\u7ed3\u679c\u96c6\n  const res: any[] = [];\n\n  \/\/ \u5faa\u73af\u5408\u5e76\u6570\u7ec4\uff0c\u76f4\u5230\u81f3\u5c11\u4e00\u4e2a\u6570\u7ec4\u88ab\u904d\u5386\u5b8c\n  while (i &lt; len1 &amp;&amp; j &lt; len2) {\n    if (arr1[i] &gt; arr2[j]) {\n      res.push(arr2[j]);\n      j++;\n    } else {\n      res.push(arr1[i]);\n      i++;\n    }\n  }\n\n  \/\/ \u5224\u65ad\u5177\u4f53\u662f\u54ea\u4e2a\u6570\u7ec4\u88ab\u904d\u5386\u5b8c\uff0c\u5c06\u53e6\u4e00\u4e2a\u6570\u7ec4\u76f4\u63a5\u8fdb\u884c\u5408\u5e76\u5373\u53ef\n  if (i &lt; len1) {\n    return res.concat(arr1.slice(i));\n  } else {\n    return res.concat(arr2.slice(j));\n  }\n}<\/code><\/pre>\n<h3>\u5feb\u901f\u6392\u5e8f<\/h3>\n<p><strong>\u65f6\u95f4\u590d\u6742\u5ea6\uff1a<code>O(nlog(n)) \u2014\u2014 O(n^2)<\/code><\/strong><\/p>\n<h4>\u6838\u5fc3\u601d\u60f3<\/h4>\n<p><strong>\u5feb\u901f\u6392\u5e8f<\/strong> \u5b9e\u9645\u4e0a\u548c <strong>\u5f52\u5e76\u6392\u5e8f<\/strong> \u7684\u601d\u60f3\u662f\u9ad8\u5ea6\u7edf\u4e00\u7684\uff0c\u90fd\u662f\u5229\u7528 <strong>\u5206\u6cbb\u601d\u60f3<\/strong> \u5c06\u5927\u95ee\u9898\u7684\u89e3\u53d8\u6210\u5c0f\u95ee\u9898\u7684\u89e3\uff0c\u4f46\u533a\u522b\u5728\u4e8e <strong>\u5f52\u5e76<\/strong> \u662f\u5c06\u6570\u7ec4\u771f\u6b63\u8fdb\u884c\u4e86\u5206\u5272\uff0c\u800c <strong>\u5feb\u6392<\/strong> \u5219\u662f\u76f4\u63a5\u5728\u539f\u6709\u7684\u6570\u7ec4\u5185\u90e8\u8fdb\u884c\u6392\u5e8f\uff0c\u4e0d\u4f1a\u771f\u6b63\u5c06\u6570\u7ec4\u8fdb\u884c\u5206\u5272\uff0c\u800c\u662f\u7528\u7d22\u5f15\u503c\u4f5c\u4e3a\u6307\u9488\u6765\u4ee3\u66ff\u3002<\/p>\n<p><img decoding=\"async\" referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/bVc4J0s\" alt=\"\" title=\"\" loading=\"lazy\"><\/p>\n<h4>JavaScript \u5b9e\u73b0<\/h4>\n<p><strong>\u65f6\u95f4\u590d\u6742\u5ea6\u5206\u6790\uff1a<\/strong><\/p>\n<ul>\n<li>\n<p>\u6700\u597d\u60c5\u51b5<\/p>\n<ul>\n<li>\u6bcf\u6b21\u9009\u62e9\u57fa\u51c6\u503c\uff0c\u90fd\u521a\u597d\u662f\u5f53\u524d\u5b50\u6570\u7ec4\u7684\u4e2d\u95f4\u6570\uff0c\u5373\u786e\u4fdd\u6bcf\u4e00\u6b21\u5206\u5272\u90fd\u80fd\u5c06\u6570\u7ec4\u5206\u4e3a\u4e24\u534a\uff0c\u8fdb\u800c\u53ea\u9700\u8981\u9012\u5f52 <code>log2(n)<\/code> \u6b21<\/li>\n<li>\u4e5f\u53ef\u4ee5\u8ba4\u4e3a <strong>\u5feb\u6392<\/strong> \u548c <strong>\u5f52\u5e76<\/strong> \u6838\u5fc3\u601d\u8def\u4e00\u81f4\uff0c\u4e8e\u662f\u65f6\u95f4\u590d\u6742\u5ea6\u4e5f\u4e3a\u00a0<code>O(nlog(n))<\/code><\/li>\n<\/ul>\n<\/li>\n<li>\n<p>\u6700\u574f\u60c5\u51b5<\/p>\n<ul>\n<li>\u6bcf\u6b21\u5212\u5206\u53d6\u5230\u7684\u90fd\u662f\u5f53\u524d\u6570\u7ec4\u4e2d\u7684 <strong>\u6700\u5927\u503c\/\u6700\u5c0f\u503c<\/strong>\uff0c\u6b64\u65f6 <strong>\u5feb\u6392<\/strong> \u9000\u5316\u4e3a <strong>\u5192\u6ce1\u6392\u5e8f<\/strong>\uff0c\u56e0\u6b64\u65f6\u95f4\u590d\u6742\u5ea6\u662f\u00a0<code>O(n^2)<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<pre><code class=\"js\">export function quickSort(arr, left = 0, right = arr.length - 1) {\n  \/\/ \u9012\u5f52\u8fb9\u754c\n  if (arr.length &gt; 1) {\n    \/\/ lineIndex \u8868\u793a\u4e0b\u4e00\u6b21\u5212\u5206\u5de6\u53f3\u5b50\u6570\u7ec4\u7684\u7d22\u5f15\u4f4d\n    const lineIndex = partition(arr, left, right);\n\n    \/\/ \u5982\u679c\u5de6\u8fb9\u5b50\u6570\u7ec4\u7684\u957f\u5ea6\u4e0d\u5c0f\u4e8e 1\uff0c\u5219\u9012\u5f52\u5feb\u6392\u8fd9\u4e2a\u5b50\u6570\u7ec4\n    if (left &lt; lineIndex - 1) {\n      \/\/ \u5de6\u5b50\u6570\u7ec4\u4ee5 lineIndex-1 \u4e3a\u53f3\u8fb9\u754c\n      quickSort(arr, left, lineIndex - 1);\n    }\n\n    \/\/ \u5982\u679c\u53f3\u8fb9\u5b50\u6570\u7ec4\u7684\u957f\u5ea6\u4e0d\u5c0f\u4e8e1\uff0c\u5219\u9012\u5f52\u5feb\u6392\u8fd9\u4e2a\u5b50\u6570\u7ec4\n    if (right &gt; lineIndex) {\n      \/\/ \u53f3\u5b50\u6570\u7ec4\u4ee5 lineIndex \u4e3a\u5de6\u8fb9\u754c\n      quickSort(arr, lineIndex, right);\n    }\n  }\n\n  return arr;\n}\n\n\/\/ \u4ee5\u57fa\u51c6\u503c\u4e3a\u8f74\u5fc3\uff0c\u5212\u5206\u5de6\u53f3\u5b50\u6570\u7ec4\u7684\u8fc7\u7a0b\nfunction partition(arr, left, right) {\n  \/\/ \u57fa\u51c6\u503c\u9ed8\u8ba4\u53d6\u4e2d\u95f4\u4f4d\u7f6e\u7684\u5143\u7d20\n  let pivotValue = arr[Math.floor(left + (right - left) \/ 2)];\n\n  \/\/ \u521d\u59cb\u5316\u5de6\u53f3\u6307\u9488\n  let i = left;\n  let j = right;\n\n  \/\/ \u5f53\u5de6\u53f3\u6307\u9488\u4e0d\u8d8a\u754c\u65f6\uff0c\u5faa\u73af\u6267\u884c\u4ee5\u4e0b\u903b\u8f91\n  while (i &lt;= j) {\n    \/\/ \u5de6\u6307\u9488\u6240\u6307\u5143\u7d20\u82e5\u5c0f\u4e8e\u57fa\u51c6\u503c\uff0c\u5219\u53f3\u79fb\u5de6\u6307\u9488\n    while (arr[i] &lt; pivotValue) {\n      i++;\n    }\n\n    \/\/ \u53f3\u6307\u9488\u6240\u6307\u5143\u7d20\u5927\u4e8e\u57fa\u51c6\u503c\uff0c\u5219\u5de6\u79fb\u53f3\u6307\u9488\n    while (arr[j] &gt; pivotValue) {\n      j--;\n    }\n\n    \/\/ \u82e5 i&lt;=j\uff0c\u5219\u610f\u5473\u7740\u57fa\u51c6\u503c\u3010\u5de6\u8fb9\u3011\u5b58\u5728\u8f83\u5927\u5143\u7d20 \u6216\u3010\u53f3\u8fb9\u3011\u5b58\u5728\u8f83\u5c0f\u5143\u7d20\n    \/\/ \u4ea4\u6362\u4e24\u4e2a\u5143\u7d20\u786e\u4fdd\u5de6\u53f3\u4e24\u4fa7\u6709\u5e8f\n    if (i &lt;= j) {\n      [arr[i], arr[j]] = [arr[j], arr[i]];\n      i++;\n      j--;\n    }\n  }\n\n  \/\/ \u8fd4\u56de\u5de6\u6307\u9488\u7d22\u5f15\u4f5c\u4e3a\u4e0b\u4e00\u6b21\u5212\u5206\u5de6\u53f3\u5b50\u6570\u7ec4\u7684\u4f9d\u636e\n  return i;\n}<\/code><\/pre>\n<h2>Array.prototype.sort() \u7684\u539f\u7406<\/h2>\n<p><strong>v8<\/strong> \u4e3a\u4e86\u5b9e\u73b0 <strong>\u5b57\u8282\u7801 + \u5373\u65f6\u7f16\u8bd1\uff08JIT\uff09<\/strong> \u7684\u4f18\u5316\uff0c<strong>sort<\/strong> \u51fd\u6570\u5728 <strong>7.0<\/strong> \u540e\u4f7f\u7528\u8c37\u6b4c\u81ea\u7814\u7684\u00a0<strong>Torque<\/strong> \u8bed\u8a00\uff08\u5373 <code>.tq<\/code>\uff09\u6765\u5f00\u53d1\uff0c\u4e14\u6392\u5e8f\u7b97\u6cd5\u53d8\u6210\u4e86 <strong>TimSort<\/strong>\u3002<\/p>\n<h3>7.0 \u7248\u672c\u53ca\u4e4b\u524d\u7684\u5b9e\u73b0<\/h3>\n<p><a href=\"https:\/\/link.segmentfault.com\/?enc=lIiO8XSh46Bj6xFHSPXxDw%3D%3D.pOROXLbjEFsPFlTGc1LjVp5S0og%2FVTJOlE6%2FZ61y0ESUii1049jdiPzLFbx5eI%2B7A%2F3CX6Gfqoe5s6%2B2kwStES5A%2Fn7ddYWCOBgJzc%2FTCMwmfUT465m0N9O876nIvgD4\" rel=\"nofollow\"><strong>\u6e90\u7801\u5730\u5740<\/strong><\/a><\/p>\n<p>\u8be5\u7248\u672c\u53ca\u4e4b\u524d\u4f7f\u7528 <code>js<\/code> \u6765\u5f00\u53d1\uff0c\u6838\u5fc3\u5185\u5bb9\u5982\u4e0b\uff1a<\/p>\n<ul>\n<li><strong><code>\u6570\u7ec4\u957f\u5ea6 &lt;= 10<\/code><\/strong> \u65f6\uff0c\u4f7f\u7528 <strong><code>\u63d2\u5165\u6392\u5e8f<\/code><\/strong><\/li>\n<li><strong><code>\u6570\u7ec4\u957f\u5ea6 &gt; 10<\/code><\/strong> \u65f6\uff0c\u4f7f\u7528 <strong><code>\u5feb\u901f\u6392\u5e8f<\/code><\/strong><\/li>\n<\/ul>\n<pre><code class=\"js\">  \/\/ Insertion sort is faster for short arrays.\n  if (to - from &lt;= 10) {\n    \/\/ \u63d2\u5165\u6392\u5e8f\n    InsertionSort(a, from, to);\n    return;\n  }\n  ...\n  if (to - high_start &lt; low_end - from) {\n    \/\/ \u5feb\u901f\u6392\u5e8f\n    QuickSort(a, high_start, to);\n    to = low_end;\n  } else {\n    QuickSort(a, from, low_end);\n    from = high_start;\n  }<\/code><\/pre>\n<p>\u539f\u56e0\u5728\u4e8e\u5f53\u6570\u636e\u6bd4\u8f83\u5c11\u7684\u65f6\u5019\uff0c<strong>\u63d2\u5165\u6392\u5e8f<\/strong> \u53ef\u80fd\u6267\u884c\u65f6\u95f4 <strong>\u66f4\u77ed<\/strong>\uff0c\u6bd4\u5982\u6570\u7ec4\u957f\u5ea6\u4e3a <code>10<\/code> \u65f6:<\/p>\n<ul>\n<li><strong>\u63d2\u6392<\/strong> \u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a\uff1a<code>O(n^2)<\/code>\uff0c\u5373\u6b64\u65f6\u53ea\u9700\u8981\u6267\u884c <code>10*10=100<\/code> \u6b21<\/li>\n<li><strong>\u5feb\u6392<\/strong> \u7684\u65f6\u95f4\u590d\u6742\u5ea6\u867d\u53ef\u80fd\u4e3a <code>O(nlog(n))<\/code>\uff0c\u4f46\u5176\u53ef\u80fd\u4e3a <code>f*n*(log n)+c<\/code>\uff0c\u5176\u4e2d <code>f<\/code> \u4e3a\u7cfb\u6570\uff0c<code>c<\/code> \u4e3a\u5e38\u6570\uff0c\u5047\u8bbe <code>f=10\uff0cc=20<\/code>\uff0c\u6b64\u65f6 <code>O(10) = 10*10*log10+20<\/code>\uff0c\u5728\u8fd9\u79cd\u60c5\u51b5\u4e0b\u660e\u663e\u6267\u884c\u6b21\u6570\u4f1a\u5927\u4e8e <code>100<\/code><\/li>\n<\/ul>\n<h3>Torque \u4e2d\u7684\u5b9e\u73b0<\/h3>\n<p><a href=\"https:\/\/link.segmentfault.com\/?enc=mK2ainALpLJcROOkrrS%2FyA%3D%3D.%2Ft1qPtjgBtqPZxkeAAEX1FNhHUGVVuKOezdsnq3gAFjB88vjXYC23jkGpA7Z9AA63857bqUyx4mXJO1o%2Fb1VatDqz8es7oENv0sOxaAVHps%3D\" rel=\"nofollow\"><strong>\u6e90\u7801\u5730\u5740<\/strong><\/a><\/p>\n<p>\u8be5\u7248\u672c\u53ca\u4f7f\u7528 <code>tq<\/code> \u6765\u5f00\u53d1\uff0c\u6838\u5fc3\u5185\u5bb9\u5982\u4e0b\uff1a<\/p>\n<ul>\n<li><strong><code>\u6570\u7ec4\u957f\u5ea6\u8f83\u5c0f<\/code><\/strong> \u65f6\uff0c\u4f7f\u7528 <strong><code>\u4e8c\u5206\u63d2\u5165\u6392\u5e8f<\/code><\/strong><\/li>\n<li><strong><code>\u6570\u7ec4\u957f\u5ea6\u8f83\u5927<\/code><\/strong> \u65f6\uff0c\u4f7f\u7528 <strong><code>\u5f52\u5e76\u6392\u5e8f<\/code><\/strong><\/li>\n<\/ul>\n<p>\u5176\u4ed6\u5177\u4f53\u5185\u5bb9\u53ef\u76f4\u63a5\u67e5\u770b\u6e90\u7801\u4e2d\u4e0e TimeSort \u76f8\u5173\u90e8\u5206\u3002<\/p>\n<pre><code class=\"js\">  while (remaining != 0) {\n    let currentRunLength: Smi = CountAndMakeRun(low, low + remaining);\n\n    \/\/ If the run is short, extend it to min(minRunLength, remaining).\n    if (currentRunLength &lt; minRunLength) {\n      const forcedRunLength: Smi = SmiMin(minRunLength, remaining);\n      \n      \/\/ \u4e8c\u5206\u63d2\u5165\u6392\u5e8f\n      BinaryInsertionSort(low, low + currentRunLength, low + forcedRunLength);\n      \n    }\n    \n    ...\n\n    \/\/ \u5f52\u5e76\n    MergeCollapse(context, sortState);\n}<\/code><\/pre>\n<h2>\u6700\u540e<\/h2>\n<p>2022 \u5373\u5c06\u8fc7\u53bb\uff0c\u6536\u62fe\u597d\u5fc3\u60c5\uff0c\u7ee7\u7eed\u52aa\u529b\uff01\uff01\uff01\u672a\u6765\u53ef\u671f\uff0c\u5927\u5bb6\u52a0\u6cb9\uff01\uff01\uff01<\/p>\n<p><a href=\"https:\/\/segmentfault.com\/a\/1190000043036856\">https:\/\/segmentfault.com\/a\/1190000043036856<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u672c\u6587\u53c2\u4e0e\u4e86 SegmentFault \u601d\u5426\u5e74\u5ea6\u5f81\u6587\u300c\u4e00\u540d\u6280\u672f\u4eba\u7684 2022\u300d\uff0c\u6b22\u8fce\u6b63\u5728\u9605\u8bfb\u7684\u4f60\u4e5f\u52a0\u5165\u3002 \u524d\u8a00  [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4],"tags":[],"class_list":["post-10006964","post","type-post","status-publish","format-standard","hentry","category-share"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/posts\/10006964","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=10006964"}],"version-history":[{"count":0,"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/posts\/10006964\/revisions"}],"wp:attachment":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=10006964"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=10006964"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=10006964"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}