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

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

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

代码：

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使用了一个快速排序的变体

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

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

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

（编辑：惠州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!