JS 中的排序算法

   <p style="text-align: center;"><img src="https://simg.open-open.com/show/d10d1322e3e7edf3b8aa6885deb51b10.png"></p>    <p>假设我们有一个没有任何排列顺序的号码簿。当需要添加联络人和电话时， 你只能将其写在下一个空位上。</p>    <p>假定你的联系人列表上有很多人，某天，你要找某个联系人及其电话号码。但是由于联系人列表没有按照任何顺序来组织，你只能逐个检查，直到找到那个你想要的联系人为止。</p>    <p>这个方法太吓人了，难道你不这么认为?想象一下你要在黄页上搜寻一个联系 人，但是那本黄页没有进行任何组织，那得花多久时间啊?!</p>    <p>因此(还有其他原因)，我们需要组织信息集，比如那些存储在数据结构里的信息。排序和搜索算法广泛地运用在待解决的日常问题中。</p>    <h2><strong>冒泡排序</strong></h2>    <p>从运行时间的角度来看，冒泡排序是最差的一个。</p>    <p>冒泡排序比较任何两个相邻的项，如果第一个比第二个大，则交换它们。元素项向上移动至 正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。</p>    <p>下面这个示意图展示了冒泡排序的工作过程:</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/0aebb84c7809c5fd565c6af9856953f5.png"></p>    <pre>  <code class="language-javascript">let arr = [5, 4, 3, 2, 1]  let len = arr.length  for (let i = 0; i < len; i++) {   for (let j = 0; j < len - 1; j++) {   if (arr[j] > arr[j+1]) {   swap(j, j+1)   }   }  }  function swap(index1, index2){   let tmp = arr[index1]   arr[index1] = arr[index2]   arr[index2] = tmp  }  </code></pre>    <h3><strong>改进后的冒泡排序</strong></h3>    <p>如果从内循环减去外循环中已跑过的轮数，就可以避免内循环中所有不必要的比较</p>    <p>下面这个示意图展示了改进后的冒泡排序算法是如何执行的:</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/e83831104802ac028b3348ffa16af088.png"></p>    <pre>  <code class="language-javascript">for (let i = 0; i < len; i++) {   for (j = 0; j < len - 1 - i; j++) {   if (arr[j] > arr[j+1]) {   swap(j, j+1)   }   }  }  </code></pre>    <p>即便我们做了这个小改变，改进 了一下冒泡排序算法，但我们还是不推荐该算法，它的复杂度是 O(n <sup>2</sup> )。</p>    <h2><strong>选择排序</strong></h2>    <p>选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/a3174009ace054e863f9aab02a2a2f10.png"></p>    <pre>  <code class="language-javascript">let arr = [5, 4, 3, 2, 1]  let len = arr.length  let indexMin = 0  for (let i = 0; i < len - 1; i++) {   indexMin = i   for (let j = i; j < len; j++) {   if (arr[indexMin] > arr[j]) {   indexMin = j   }   }   if (indexMin !== i) {   swap(indexMin, i)   }  }  </code></pre>    <p>选择排序同样也是一个复杂度为 O(n <sup>2</sup> ) 的算法。和冒泡排序一样，它包含有嵌套的两个循环， 这导致了二次方的复杂度。</p>    <h2><strong>插入排序</strong></h2>    <p>假定第一项已经排序了，接着，它和第二项进行比较，第二项是应该待在原位还是插到第一项之前呢?这样，头两项就已正确排序，接着和第三项比较(它是该插入到第一、第二还是第三的位置呢?)，以此类推。</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/70f075d457e968352673019df69dd04a.png"></p>    <pre>  <code class="language-javascript">let arr = [1, 2, 3, 4, 5]  let len = arr.length  let j = 0  let tmp = 0    for (let i = 1; i < len; i++) {   j = i   tmp = arr[i]   while (j > 0 && arr[j-1] > tmp) {   arr[j] = arr[j-1]   j--   }   arr[j] = tmp  }  </code></pre>    <p>排序小型数组时，此算法比选择排序和冒泡排序性能要好。</p>    <h2><strong>归并排序</strong></h2>    <p>前三个排序算法性能不好,但归并排序性能不错,其复杂度为 O(nlog <sup>n</sup> )。</p>    <p>JavaScript 的 Array 类定义了一个 sort 函数( Array.prototype.sort )用 以排序 JavaScript 数组。 ECMAScript 没有定义用哪 个排序算法，所以浏览器厂商可以自行去实现算法。例如， Mozilla Firefox 使用 归并排序作为 Array.prototype.sort 的实现，而 Chrome 使用了一个快速排序的变体。</p>    <p>归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。由于是分治法，归并排序也是递归的:</p>    <pre>  <code class="language-javascript">function mergeSort (arr){   let len = arr.length   if (len === 1) {   return arr   }   let mid = Math.floor(len / 2)   let left = arr.slice(0, mid)   let right = arr.slice(mid, len)   return merge(mergeSort(left), mergeSort(right))  }  function merge (leftArr, rightArr){   let result = []   let leftIndex = 0   let rightIndex = 0     while (leftIndex < leftArr.length && rightIndex < rightArr.length) {   if (leftArr[leftIndex] < rightArr[rightIndex]) {   result.push(leftArr[leftIndex])   leftIndex++   } else {   result.push(rightArr[rightIndex])   rightIndex++   }   }   while (leftIndex < leftArr.length) {   result.push(leftArr[leftIndex])   leftIndex++   }   while (rightIndex < rightArr.length) {   result.push(rightArr[rightIndex])   rightIndex++   }   return result  }  </code></pre>    <p>算法首先将原始数组分割直至只有一个元素的子数组，然后开始归并。归并过程</p>    <p>也会完成排序，直至原始数组完全合并并完成排序。</p>    <h2><strong>快速排序</strong></h2>    <p>快速排序的复杂度为 O(nlog <sup>n</sup> )，且它的性能通常比其他的复杂度为 O(nlog <sup>n</sup> ) 的排序算法要好。和归并排序一样，快速排序也使用分治的方法，将原始数组分为较小的数组(但它没有像归并排序那样将它们分割开)。</p>    <ol>     <li>首先，从数组中选择中间一项作为主元</li>     <li>创建两个指针，左边一个指向数组第一项，右边一个指向数组的最后一项。移动左指针，直到找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素，然后交换它们，重复这个过程，直到左指针超过了右指针。这个过程使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。这一步叫做划分操作。</li>     <li>接着，算法对划分后的小数组重复之前两个步骤，直至数组已完全排序。</li>    </ol>    <pre>  <code class="language-javascript">function quick (arr, left, right){   let index = 0   if (arr.length > 1) {   index = partition(arr, left, right)   if (left < index - 1) {   quick(arr, left, index - 1)   }   if (index < right) {   quick(arr, index, right)   }   }  }  function partition (arr, left, right){   let pivot = arr[Math.floor((right + left) / 2)]   let i = left   let j = right   while (i <= j) {   while (arr[i] < pivot) {   i++   }   while (arr[j] > pivot) {   j--   }   if (i <= j) {   swap(arr, i, j)   i++   j--   }   }   return i  }  </code></pre>    <p> </p>    <p>来自：http://mertensming.github.io/2016/11/10/js-sorting-algorithms/</p>    <p> </p>