JS数据结构与算法_排序和搜索算法(2)

核心：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

注意：从第二项开始，依次向前比较，保证当前项以前的序列是顺序排列

代码：

function insertionSort(arr) {  
  const len = arr.length;  
  let current, pointer;  
  for (let i = 1; i < len; i += 1) {  
    current = arr[i];  
    pointer = i;  
    while(pointer >= 0 && current < arr[pointer - 1]) { // 每次向前比较  
      arr[pointer] = arr[pointer - 1]; // 前一项大于指针项，则向前移动一项  
      pointer -= 1;  
    }  
    arr[pointer] = current; // 指针项还原成当前项  
  }  
  return arr;  
} 

2.4 归并排序

归并排序和快速排序相较于上面三种排序算法在实际中更具有可行性（在第四小节我们会通过实践复杂度来比较这几种排序算法）

JavaScript的Array类定义了一个sort函数(Array.prototype.sort)用以排序JavaScript数组。ECMAScript没有定义用哪个排序算法，所以浏览器厂商可以自行去实现算法。例如，Mozilla Firefox使用归并排序作为Array.prototype.sort的实现，而Chrome使用了一个快速排序的变体

归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一 个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。因此需要用到递归

核心：归并排序，拆分成左右两块数组，分别排序后合并

注意：递归中最小的左右数组比较为单个元素的数组，因此在较上层多个元素对比时，左右两个数组一定是顺序的

代码：

function mergeSort(arr) {  
  const len = arr.length;  
  if (len < 2) return arr; // 递归的终止条件  
  const middle = Math.floor(len / 2); // 拆分左右数组  
  const left = arr.slice(0, middle);  
  const right = arr.slice(middle);  
  return merge(mergeSort(left), mergeSort(right));  
}  
function merge(left, right) { // 将左右两侧比较后进行合并  
  const ret = [];  
  while (left.length && right.length) {  
    if (left[0] > right[0]) {  
      ret.push(right.shift());  
    } else {  
      ret.push(left.shift());  
    }  
  }  
  while (left.length) {  
    ret.push(left.shift());  
  }  
  while (right.length) {  
    ret.push(right.shift());  
  }  
  return ret;  
} 

2.5 快速排序

快速排序也许是最常用的排序算法了。它的复杂度为O(nlogn)，，且它的性能通常比其他的复 杂度为O(nlogn)的排序算法要好。和归并排序一样，快速排序也使用分治的方法，将原始数组分为较小的数组

（编辑：ASP站长网）