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

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

焦点：合并排序，拆分成阁下两块数组，别离排序后归并

留意：递归中最小的阁下数组较量为单个元素的数组，因此在较上层多个元素比拟时，阁下两个数组必然是次序的

代码：

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)的排序算法要好。和合并排序一样，快速排序也行使分治的要领，将原始数组分为较小的数组

（编辑：河北网）

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