排序算法

1.冒泡排序

比较所有的相邻元素，如果第一个比第二个大，则交换他们
一轮下来，可以保证最后一个数是最大的

执行n-1轮，就可以完成排序

Array.prototype.bubble = function() {
  for(let i = 0; i < this.length -1; i++) {
        // 执行n-1轮，因为this[j + 1]可能超出数组长度，而且最后一轮只有一个元素，不需要交换
        // this.length - 1 - i 每次交换，最后一个数为最大，也不需要在查找
      for(let j = 0; j< this.length - 1 - i; j++) {
            // 比较所有的相邻元素，如果第一个比第二个大，则交换他们
          if(this[j] > this[j + 1]) {
              const temp = this[j];
              this[j] = this[j + 1]
              this[j + 1] = temp
          }
      }
  }
}

两个嵌套排序

时间复杂度：O(n^2)

2.选择排序

```javascript Array.prototype.selectionSort = function() { for(let i = 0; i < this.length - 1; i ++) {

    // 定义最小元素的下标
  let minIndex = i
  // 找到最小元素的下标，并保证minIndex为最小元素的下标
  // 每次交换过后，数组头的元素就是最小，不参与下一次排序
  for(let j = i; j < this.length; j++) {
      if(this[j] < this[minIndex]) {
          minIndex = j
      }
  }
    // 有可能找到的元素下标和minIndex一样，所以在不一样的时候才交换
    // 交换最小的元素和轮次执行的头部元素
  if(this[i] !== this[minIndex]) {
      const temp = this[i]
      this[i] = this[minIndex]
      this[minIndex] = temp
  }

} }


- 两个嵌套循环
- 时间复杂度：O(n^2)
<a name="obWF9"></a>
## 3.插入排序
```javascript
Array.prototype.insertionSort = function() {
      // 因为默认第1个元素已经排序了，所以i从1取，而且j-1会报错
      // 因为是向前比较，最后一个元素也是需要向前插入，所以次数是数组的长度
    for(let i = 1; i< this.length; i++) {
          // 拿到需要插入的元素
        const temp = this[i]
        // 遍历之前的元素
        // 每次循环后，之前的元素已经排序好了
        let j = i
        while (j> 0) {
              // 如果上一个元素比需要插入的元素大
            if(this[j-1] > temp) {
                  // 就把上一个元素后移！！
                this[j] = this[j -1]
            }else {
                  // 因为前面已经排序了，所以直接跳出循环
                break
            }
              // 继续和前面的元素比较
            j--
        }
          // 最后把需要排序的元素插入到没有它大的元素的后面
        this[j] = temp
    }
}

两个嵌套循环
时间复杂度：O(n^2)

4.归并排序
分：把数组劈成两半，再递归地堆子数组进行“分”操作，直到分成一个个单独的数
合：把两个数组合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组

合并有序数组

新建一个空数组res，用来存放最终排序后的数组
比较两个有序数组的头部，较小者出队并推入res中

如果两个数组还有值，就重复第二步 ```javascript Array.prototype.mergeSort = function() {

// 定义递归函数

const rec = (arr) => {

    // 5. 递归结束条件 数组长度为1时就不需要分了，返回只有1个元素的数组
  if(arr.length === 1) return arr
    // 分
    // 1. 获取中间元素的下标
  const mid = Math.floor(arr.length/2)
  // 2. 获取左边的数组
  let leftArr = arr.slice(0, mid)
  // 3. 获取右边的数组
  let rightArr = arr.slice(mid, arr.length)
  // 4. 递归再对左边的数组进行分
  // 6. 得到只有一个元素的左边的数组
  const leftRes = rec(leftArr)
  // 4. 递归对右边的数组进行分
  // 6. 得到右边只有一个元素的数组
  const rightRes = rec(rightArr)
  // 合
  // 定义新的数组用来依次放比较后的元素
  let res = []
  // 7. 拿到左右两边的的数组，长度不为0 就进入循环
  while(leftRes.length || leftRes.length) {
        // 8. 比较左右两边数组的头部元素
        // 如果两个数组都有值，就判断两个数组的头部元素的大小
      if(leftRes.length && rightRes.length) {
            // 小的那个元素就被push进入res，同时去掉该数组头部元素
          res.push(leftRes[0] < rightRes[0] ? leftRes.shift() : rightRes.shift())
      } else if(leftRes.length) {
            // 如果只有一边数组有值，就直接push该数组的头部元素
          res.push(leftRes.shift())
      } else if(rightRes.length) {
          res.push(rightRes.shift())
      }
  }
    // 返回整理好的数组
  return res

} // 调用递归元素的方法，得到新的元素 const result = rec(this) // 因为sort()方法是会改变数组的，所以将this（该数组）的各个元素重新进行赋值 result.forEach((n, i) => {this[i] = n}) }

const arr = [5,4,3,2,1] arr.mergeSort()


- 分的时间复杂度是O(logN)
- 合的时间复杂度是O(n)
- 分和合是嵌套关系，所以整体时间复杂度是：O(n*logN)
<a name="zwhdp"></a>
## 5.快速排序
- 分区：从数组中任意选择一个“基准”，所有比基准小的元素放在基准前面，比基准大的元素放在基准的后面
- 递归地对基准前后的子数组进行分区
```javascript
Array.prototype.quickSort = function() {
    const rec = (arr) => {
        if(arr.length === 1) return arr
        let left = []
        let right = []
        let mid = arr[0]
        for(let i = 1; i < arr.length; i++) {
            if(arr[i] < mid) {
                left.push(arr[i])
            } else {
                right.push(arr[i])
            }
        }
        return [...rec(left), mid, ...rec(right)]
    }
    const res = rec(this);
    res.forEach((n,i) => {this[i] = n})
}
const arr = [2,4,5,3,1]

递归的时间复杂度，因为是劈成了两半，时间复杂度是O(logN)
分区的时间复杂度是O(N)，找出所有比基准大小的元素

搜索算法

1.顺序搜索
遍历数组
找到跟目标值相等的元素，就返回它的下标

遍历结束后，如果没有搜索到目标值，就返回-1

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

时间复杂度：O(N)

2.二分搜索
从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束
如果目标值大于或者小于中间元素，则在大于或者小于中间元素的那一半数组中搜索

基于数组是有序的

Array.prototype.sequentialSearch = function (target) {
  let low = 0;
  let hight = this.length -1;
  while(low <= hight) {
        // 拿到中间元素
      const mid = Math.floor((low+hight) /2);
      const element = this[mid]
      // 如果目标值比中间元素小
      if(target < element) {
            // 就把hight的值改为中间元素的上一位，在左边的数组中搜索
          hight = mid - 1
      // 如果目标值比中间元素大，就在右边的数组中搜索
      } else if(target > element) {
          low = mid + 1
      } else {
            // 相等则返回该元素的下标
          return mid
      }
  }
    // 没找到返回-1
  return -1
}

时间复杂度：O(logN)

题目

1.合并两个有序链表 - 21
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：
输入：l1 = [], l2 = []
输出：[]

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递减顺序排列

思路：

与归并排序中合并两个有序数组很相似
将数组替换为链表即可

解题步骤：

新建一个新链表，作为返回结果
用指针遍历两个有序链表，并比较两个链表的当前节点，较小者先接入新链表，并将指针后移一步
链表遍历结束，返回新链表

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
      // 新建返回节点
    let res = new ListNode(0)
    // 新建3个指针
    let p = res
    let p1 = l1
    let p2 = l2
    // 当p1和p2有值的情况下
    while(p1 && p2) {
          // 比较头部元素
        if(p1.val < p2.val) {
              // 将p的next指向较小的元素
            p.next = p1
              // 同时p1的当前元素不能用了，就往后移动一位
            p1 = p1.next
        } else {
            p.next = p2
            p2 = p2.next
        }
        p = p.next
    }
      // 因为是升序链表，如果都比较结束后，还有一个链表有值，就一定比p链表大，直接拼接到后面
    if(p1) {
        p.next = p1
    }
    if(p2) {
        p.next = p2
    }
    return res.next
};

时间复杂度：O(N)
空间复杂度：O(1) 常量变量，空间不会新增
2.猜数字大小 - 374
猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
返回我选出的数字。

示例 1：
输入：n = 10, pick = 6
输出：6

示例 2：
输入：n = 1, pick = 1
输出：1

示例 3：
输入：n = 2, pick = 1
输出：1

示例 4：
输入：n = 2, pick = 2
输出：2

提示：

1 <= n <= 231 - 1
1 <= pick <= n

思路：

二分搜索
调用guess函数，来判断中间元素是否是目标值

解题步骤：

从数组的中间元素，如果中间值正好是目标值，则返回目标值，结束搜索过程
如果中间元素大于或者小于中间元素，则在数组大于或者小于中间元素的那一半中去查找 ```javascript /**
- Forward declaration of guess API.
- @param {number} num your guess
- @return -1 if num is lower than the guess number
- 1 if num is higher than the guess number
- otherwise return 0
- var guess = function(num) {} */

/**

@param {number} n

@return {number} */ var guessNumber = function(n) { let low = 1 let high = n while(low <= high) {

   // 从中间开始搜索
 let mid = Math.floor((low + high) /2)
 // 猜大小
 const res = guess(mid)
 // 刚好
 if(0 === res) {
     return mid
 // 小了
 } else if(-1 === res) {
       // 最大值为mid -1
     high = mid -1
 } else {
       // 最小值为mid + 1
     low = mid + 1
 }

} }; ```

时间复杂度O(logN)，分为一半
空间复杂度：O(1), 没有线性增长的需要

排序搜索

排序算法

1.冒泡排序

2.选择排序

4.归并排序

搜索算法

1.顺序搜索

2.二分搜索

题目

1.合并两个有序链表 - 21

2.猜数字大小 - 374