JavaScript 中的算法

JavaScript 中的算法

Sort

以下例子全部以正序为标准

• bubbleSort 冒泡排序

冒泡排序算法的原理是比较前置位和后置位的大小，通过交换位置进行排序，就好像气泡升至表面一样，冒泡排序因此得名，算法复杂度是 O(n²)，并不推荐此算法。

看代码实现：

Array.prototype.bubbleSort = function() {
  for (let i = 0; i < this.length; i++) {
    for (let j = 0; j < this.length - 1 - i; j++) {
      if (this[j] > this[j + 1]) {
        let aux = this[j];
        this[j] = this[j + 1];
        this[j + 1] = aux;
      }
      console.log(this)
    }
    console.log('==========')
  }
};
// bubbleSort, 如 sort [5,3,1,6,8,2,9]，算法的复杂度是 O(n²)，并不推荐此算法。
// 内层循环必须要减去i,因为每经历一轮sort，最大值都会被放置在最右侧
// ~~~ 第一轮sort开始
// 第一步：比较5和3，发现5>3，则交换5和3，变成了[3,5,1,6,8,2,9]
// 第二部：比较5和1，发现5>1，则交换5和1，变成了[3,1,5,6,8,2,9]
// 第三部：比较5和6，发现5<6，保持[3,1,5,6,8,2,9]
// 第四部：比较6和8，发现6<8，保持[3,1,5,6,8,2,9]
// 第五部：比较8和2，发现8>2，则交换8和2，变成了[3,1,5,6,2,8,9]
// 第六部：比较8和9，发现8<9，保持[3,1,5,6,2,8,9]
// ~~~ 第二轮sort开始
// 第一步：比较3和1，发现3>1，则交换3和1，变成了[1,3,5,6,2,8,9]
// 第二部：比较3和5，发现3<5，保持[1,3,5,6,2,8,9]
// 第三部，比较5和6，发现5<6，保持[1,3,5,6,2,8,9]
// 第四部，比较6和2，发现6>2，则交换6和2，变成了[1,3,5,2,6,8,9]
// 第五部，比较6和8，发现6<8，保持[1,3,5,2,6,8,9]
// 第六部，比较8和9，发现8<9，保持[1,3,5,2,6,8,9]
// ~~~ 第三轮sort开始
// 第一步：比较1和3，发现1<3，保持[1,3,5,2,6,8,9]
// 第二部：比较3和5，发现3<5，保持[1,3,5,2,6,8,9]
// 第三部，比较5和2，发现5>2，则交换5和2，变成了[1,3,2,5,6,8,9]
// 第四部，比较5和6，发现5<6，保持[1,3,2,5,6,8,9]
// 第五部，比较6和8，发现6<8，保持[1,3,2,5,6,8,9]
// 第六部，比较8和9，发现8<9，保持[1,3,2,5,6,8,9]
// ~~~ 第四轮sort开始
// ...........
const array = [5,3,1,6,8,2,9];
array.bubbleSort();
// 上述sort是未经过优化的算法，由打印的结果知道，在最后一轮循环中，console.log(this)并未执行，意味着已经排序成功，那么是可以节省下面的循环的
// 下面是优化后的代码，能够节省一层循环
Array.prototype.bubbleSort = function() {
  let isSortFinish = false;
  for (let i = 0; i < this.length; i++) {
    for (let j = 0; j < this.length - 1 - i; j++) {
      if (this[j] > this[j + 1]) {
        let aux = this[j];
        this[j] = this[j + 1];
        this[j + 1] = aux;
        isSortFinish = false;
      }
      console.log(this);
    }
    if (isSortFinish) {
      break;
    }
    console.log('==========');
  }
};

• selectSort 选择排序

选择排序是一种原址比较排序算法，原理是依次选举一个最小值并将其放到左侧第一位，第二位...，以此类推，算法的复杂度是 O(n²)，并不推荐此算法

看代码实现：

Array.prototype.selectSort = function() {
  let indexMin;
  for (let i = 0; i < this.length - 1; i++){
    indexMin = i;
    for (let j = i + 1; j < this.length; j++){ 
      if(this[indexMin] > this[j]) {
        indexMin = j;
      }
    } 
    if (i !== indexMin){
      let aux = this[i];
      this[i] = this[indexMin];
      this[indexMin] = aux;
    }
    console.log(this);
  }
  return this;
};

// selectSort，如 sort [5,3,1,6,8,2,9]
// ~~~ 第一轮sort开始
// 第一步：当轮最小值下标是0，比较arr[0]和arr[0]，发现arr[0]=arr[0]，当轮最小值下标是0
// 第二步：当轮最小值下标是0，比较arr[0]和arr[1]，发现arr[0]>arr[1]，当轮最小值下标是1
// 第三步：当轮最小值下标是1，比较arr[1]和arr[2]，发现arr[1]>arr[2]，当轮最小值下标是2
// 第四步：当轮最小值下标是2，比较arr[2]和arr[3]，发现arr[2]<arr[3]，当轮最小值下标是2
// 第无步：当轮最小值下标是2，比较arr[2]和arr[4]，发现arr[2]<arr[4]，当轮最小值下标是2
// 第六步：当轮最小值下标是2，比较arr[2]和arr[5]，发现arr[2]<arr[5]，当轮最小值下标是2
// 第七步：当轮最小值下标是2，比较arr[2]和arr[6]，发现arr[2]<arr[6]，当轮最小值下标是2
// 当前最小值下标是2，当前sort为第（1-1=0）轮，交换位置，生成[1,3,5,6,8,2,9]
// ~~~ 第二轮sort开始
// 第一步：当轮最小值下标是1，比较arr[1]和arr[1]，发现arr[1]=arr[1]，当轮最小值下标是1
// 第二步：当轮最小值下标是1，比较arr[1]和arr[2]，发现arr[1]<arr[2]，当轮最小值下标是1
// 第三步：当轮最小值下标是1，比较arr[1]和arr[3]，发现arr[1]<arr[3]，当轮最小值下标是1
// 第四步：当轮最小值下标是1，比较arr[1]和arr[4]，发现arr[1]<arr[4]，当轮最小值下标是1
// 第无步：当轮最小值下标是1，比较arr[1]和arr[5]，发现arr[1]>arr[5]，当轮最小值下标是5
// 第六步：当轮最小值下标是5，比较arr[5]和arr[6]，发现arr[5]<arr[6]，当轮最小值下标是5
// 当前最小值下标是5，当前sort为第（2-1=1）轮，交换位置，生成[1,2,5,6,8,3,9]
// ~~~ 第三轮sort开始
// .....
const array = [5,3,1,6,8,2,9];
array.selectSort();

• insertSort 插入排序

插入排序原理是假定第一位已经排序了，与下一位进行比较，判断是应该插入到第一位前面还是后面，然后拿第二位和第三位进行比较，判断是应该插入到第二位前面还是第一位前面还是第二位后面，以此类推

看代码实现：

Array.prototype.insertSort = function() {
  let j,
    temp;
  for (let i = 1; i < this.length; i++) {
    j = i;
    temp = this[i];
    while (j > 0 && this[j - 1] > temp) {
        this[j] = this[j - 1];
        j--;
    } 
    this[j] = temp;
  }
  return this;
};

// insertSort，如 sort [5,3,1,6,8,2,9]
// 比较5和3，发现5>3，把3插入到5前面（类似交换位置），得到[3,5,1,6,8,2,9]
// 比较5和1，发现5>3，比较3和1，发现3>1, 把1插入到3前面（类似多次交换位置），得到[1,3,5,6,8,2,9]
// 比较5和6，发现5<6，维持现状[1,3,5,6,8,2,9]
// .... 以此类推
const array = [5,3,1,6,8,2,9];
array.insertSort();

• mergeSort 归并排序

归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一 个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组，非常依赖javascript（所有）语言的执行特性。前三个排序算法性能不好，但归并排序性能不错，其复杂度为O(n log^n)。

看代码实现：

Array.prototype.mergeSort = function() {
  const merge = (left, right) => {
    console.log(left)
    console.log(right)
      const result = []
      let il = 0
      let ir = 0
      while(il < left.length && ir < right.length) {
          if(left[il] < right[ir]) {
              result.push(left[il++])
          } else {
              result.push(right[ir++])
          }
      }
      while (il < left.length) {
          result.push(left[il++])
      }
      while (ir < right.length) {
          result.push(right[ir++])
      }
      console.log(result);
      console.log('==========')
      return result
  }
  const mergeSortRec = array => {
      if (array.length === 1) {
          return array
      }
      const mid = Math.floor(array.length / 2)
      const left = array.slice(0, mid)
      const right = array.slice(mid, array.length)
      return merge(mergeSortRec(left), mergeSortRec(right))
  }
  return mergeSortRec(this)
};
// mergeSort，如 sort [5,3,1,6,8,2,9]
// 第一次拆分：[5,3,1], [6,8,2,9]
// 第二次拆分：[5], [3,1]  按照javascript语言的特性，从左向右执行代码，暂且不考虑右侧数组
// 第三次拆分：[3], [1]  为什么[5],[3,1] 下一步只剩下[3],[1]呢? 因为5不能被拆分了，所以停留在上一层等待下层嵌套代码返回结果。
// 代码执行从上而下，剥离到最后一层时，开始依次向上层返回结果，打印的结果应该依次是
// 第一次打印： [3] [1]    [1,3]
// 第二次打印： [5], [1,3]    [1,3,5]
// 第三次打印： [6], [8]    [6,8]
// ..... 依次类推
// 核心比较代码是merge函数
const array = [5,3,1,6,8,2,9];
array.mergeSort();

• quickSort 快速排序

快速排序也许是最常用的排序算法了。它的复杂度为O(nlog^{n)，且它的性能通常比其他的复杂度为O(nlog}n)的排序算法要好。和归并排序一样，快速排序也使用分治的方法，将原始数组分为较小的数组（但它没有像归并排序那样将它们分割开)。
①：首先，从数组中选择中间一项作为主元
②：创建两个指针，左边一个指向数组第一个项，右边一个指向数组最后一个项。移动左指 针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素，然后交 换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之 前，而比主元大的值都排在主元之后。这一步叫作划分操作。
③：接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的 子数组）重复之前的两个步骤，直至数组已完全排序。

看代码实现：

Array.prototype.quickSort = function() {
  const partition = (array, left, right) => {
    var pivot = array[Math.floor((right + left) / 2)];
    let i = left;
    let j = right;
    while (i <= j) {
      while (array[i] < pivot) {
        i++;
      }
      while (array[j] > pivot) {
        j--;
      }
      if (i <= j) {
        let aux = array[i];
        array[i] = array[j];
        array[j] = aux;
        i++;
        j--;
      }
    }
    return i;
  }
  const quick = (array, left, right) => {
    let index;
    if (array.length > 1) {
      index = partition(array, left, right);
      if (left < index - 1) {
        quick(array, left, index - 1);
      }
      if (index < right) {
        quick(array, index, right);
      }
    }
  }
  quick(this, 0, this.length - 1);
  return this;
}

const array = [5,3,1,6,8,2,9];
array.quickSort();

Search

• sequentialSearch 顺序搜索

顺序或线性搜索是最基本的搜索算法，顺序搜索是最低效的一种搜索算法。

看代码实现：

Array.prototype.sequentialSearch = function(item) {
  for (let i = 0; i < this.length; i++) {
    if (item === this[i]) return i;
  }
  return -1;
};

• binarySearch 二分搜索

这个算法要求被搜索的数据结构已排序

...... 未完待续