排序

冒泡排序

• 思路
  • 比较所以相邻元素，如果第一个比第二个大，则交换他们
  • 一轮下来，可以保证最后一个数是最大的
  • 执行n-1轮，就可以完成排序
• 时间复杂度O(n^2)

Array.prototype.bubbleSort = function (config) {
  const swap = (j) => {
    const tmp = this[j]
    this[j] = this[j + 1]
    this[j + 1] = tmp
  }
  const forEach = (i) => {
    if (!config || config === 'up') {
      // 升序
      for (let j = 0; j < this.length - 1 - i; j++) {
        if (this[j] > this[j + 1]) swap(j)
      }
    } else if (config === 'down') {
      // 降序
      for (let j = this.length - 1 - i; j >= 0; j--) {
        if (this[j] < this[j + 1]) swap(j)
      }
    }
  }
  for (let i = 0; i < this.length - 1; i++) {
    forEach(i);
  }
}
const arr = [5, 6, 3, 2, 8];
arr.bubbleSort('down');

选择排序

• 思路
  • 找到数组中的最小值，选中它并将其放置在第一位
  • 接着找到第二小的值，选中它并将其放置在第二位
  • 以此类推执行n-1轮
• 时间复杂度O(n^2) ```javascript Array.prototype.selectionSort = function () { // 升序 let indexMini = 0; for (let i = 0; i < this.length - 1; i++) { for (let j = i; j < this.length; j++) {

  if (this[j] < this[indexMini]) {
    indexMini = j;
  }

  } if (i !== indexMini) {

  const tmp = this[i];
  this[i] = this[indexMini];
  this[indexMini] = tmp;

  } }

}

const arr = [5, 6, 3, 2, 8]; arr.selectionSort();

<a name="zPRVq"></a>
## 插入排序
- 思路
   - 从第二个数**往前比**
   - 比它大的就**往后排**
   - 依次类推，进行到最后一个数
- 时间复杂度`O(n^2)`
```javascript
Array.prototype.insertionSort = function () {
  // 升序
  for (let i = 1; i < this.length; i++) {
    const tmp = this[i];
    let j = i;
    while (j > 0) {
      if (this[j - 1] > tmp) {
        this[j] = this[j - 1];
      } else {
        break;
      }
      j--;
    }
    this[j] = tmp;
  }
}
const arr = [5, 6, 3, 2, 8];
arr.insertionSort();

归并排序

• 思路
  • 分：把数组劈成两半，再递归地对子数组进行“分”操作，直到分成一个个单独的数
  • 合：把两个数合并成有序数组，再对有序数组进行合并，直到全部的子数组合并成一个完整的数组
    • 新建一个空数组res，用于存放最终排序后的数组
    • 比较两个有序数组的头部，较小者出队并推入res中
    • 如果两个数组还有值，就重复第二步
• 时间复杂度O(nlogn)

Array.prototype.mergeSort = function () {
  // 递归
  const dfs = (arr) => {
    // 分
    if (arr.length === 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid, arr.length);
    const orderLeft = dfs(left);
    const orderRight = dfs(right);
    const res = []; // 存放结果
    // 合
    while (orderLeft.length || orderRight.length) {
      if (orderLeft.length && orderRight.length) {
        res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift());
      } else if (orderLeft.length) {
        res.push(orderLeft.shift())
      } else {
        res.push(orderRight.shift())
      }
    }
    return res;
  }
  const res = dfs(this);
  res.forEach((num, i) => { this[i] = num });
}
const arr = [5, 6, 3, 2, 8];
arr.mergeSort();

快速排序

• 思路
  • 分区：从数组中任意选择一个“基准”，所有比基准小的元素放在基准前面，比基准大的元素放在基准后面
• 时间复杂度O(n*logn)
  • 递归的时间复杂度O(logn)
  • 分区操作的时间复杂度O(n)

搜索

顺序搜索

• 思路
  • 遍历数组
  • 找到目标值相等的元素，就返回它的坐标
  • 遍历结束后，如果没有搜索到目标值，就返回-1
• 时间复杂度O(n) ```javascript Array.prototype.sequantialSearch = function (item) { for(let i = 0; i < this.length; i++) { if(this[i] === item) {

  return i

  } } return -1; }

const res = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].sequantialSearch(3); console.log(res);

<a name="zgqaL"></a>
## 二分搜索
- 思路——前提数组有序
   - 在数组的中间元素开始，如果中间元素正好是目标值，则搜索结束
   - 如果目标值大于或小于中间元素，则在大于或小于中间元素的那一半数组中搜索
   - 直到找到目标值，没找到返回-1
- 时间复杂度`O(logn)`
```javascript
Array.prototype.binarySearch = function (item) {
  let low = 0;
  let high = this.length - 1;
  while (low <= high) {
    const mid = (low + high) >> 1;
    if (this[mid] < item) {
      low = mid + 1;
    } else if (this[mid] > item) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}
const res = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].binarySearch(3);
console.log(res);