排序

冒泡排序

• 比较所有相邻元素，如果第一个比第二个大，则交换他们；
• 一轮下来，可以保证最后一个数是最大的；
• 执行 n - 1 轮，就可以完成排序；

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

Array.prototype.bubbleSort = function() {
  for(let i = 0; i < this.length - 1; i += 1) {
    for (let j = 0; j < this.length - 1 - i; j += 1) {
      if (this[j] > this[j + 1]) {
        [this[j], this[j+1]] = [this[j + 1], this[j]]
      }
    }
  }
}

const arr = [1, 5, 1, 4, 5, 2, 3]
arr.bubbleSort()
console.log(arr)

选择排序

• 找到数组中的最小值，选中它并将其放置在第一位；
• 接着找到第二小的值，选中它并将其放置在第二位；
• 以此类推，执行 n - 1 轮；

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

Array.prototype.selectionSort = function() {
  for(let i = 0; i < this.length - 1; i += 1) {
    let indexMin = i
    for (let j = i; j < this.length; j += 1) {
      if (this[j] < this[indexMin]) {
        indexMin = j
      }
    }
    [this[i], this[indexMin]] = [this[indexMin], this[i]]
  }
}

const arr = [4, 5, 1, 4, 5, 2, 3]
arr.selectionSort()
console.log(arr)

插入排序

• 从第二个数开始往前比；
• 比他大就往后排；
• 以此类推进行到最后一个数；

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

Array.prototype.insertionSort = function() {
  // 从第二个元素开始，i 为 1
  for (let i = 1; i < this.length; i += 1) {
    const temp = this[i]
    let j = i
    while(j > 0) {
      if (this[j - 1] > temp) {
        this[j] = this[j - 1]
      } else {
        break
      }
      j -= 1
    }
    this[j] = temp
  }
}

const arr = [1, 5, 1, 4, 5, 2, 3]
arr.insertionSort()
console.log(arr)

归并排序

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

合并两个有序数组：

• 新建一个空数组 res，用于存放最终排序后的数组；
• 比较两个有序数组的头部，较小者出队并推入 res 中；
• 如果两个数组还有值，就重复第二步骤；

时间复杂度：O(n * logn)

Array.prototype.mergeSort = function() {
  const rec = (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 = rec(left)
    const orderRight = rec(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 if (orderRight.length) {
        res.push(orderRight.shift())
      }
    }
    return res
  }
  const res = rec(this)
  res.forEach((n, i) => {
    this[i] = n
  })
}

快速排序

• 分区：从数组中任意选择一个 “基准”，所有比基准小的元素放在基准前面，比基准大的元素放在基准的后面；
• 递归：递归地对基准前后的子数组进行分区；

时间复杂度：O(n * logn)

Array.prototype.quickSort = function() {
  const rec = (arr) => {
    if (arr.length === 1) { return arr }
    const left = []
    const right = []

    // 基准元素
    const mid = arr[0]
    for (let i = 1; i < arr.length; i += 1) {
      if (arr[i] < mid) {
        left.push(arr[i])
      } else {
        right.push(arr[i])
      }
    }
    return [...rec(left), mid, ...rec(right)]
  }
  const res = rec(this)
  // 将值拷贝到 this 上
  res.forEach((n, i) => {
    this[i] = n
  })
}

搜索

顺序搜索

• 遍历数组；
• 找到跟目标值相等的元素，就返回他的下标；
• 遍历结束后，如果没有搜索到目标值，就返回 -1；

时间复杂度：O(n)

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

const res = [1, 2, 5, 6, 3].sequentialSearch(3)
console.log(res)

二分搜索

前提是在有序数组中进行搜索；

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

时间复杂度：O(logn)

Array.prototype.binarySearch = function (item) {
  // 搜索的最小下标和最大下标
  let low = 0
  let high = this.length - 1
  while(low <= high) {
    const mid = Math.floor((low + high) / 2)
    const element = this[mid]
    if(element < item) {
      low = mid + 1
    } else if (element > item) {
      high = mid - 1
    } else {
      return mid
    }
  }
  return -1
}

算法题

合并两个有序链表

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

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

链接：https://leetcode-cn.com/problems/merge-two-sorted-lists

• 解题思路：与归并排序中合并两个有序数组相似；将数组替换成链表即可。

• 解题步骤：新建一个新链表，作为返回结果；用指针遍历两个有序链表，并比较两个链表的当前节点，较小者先进入新链表，并将指针后移一位。链表遍历结束，返回新链表。

• 时间复杂度：O(m + n)

• 空间复杂度：O(1)

var mergeTwoLists = function(l1, l2) {
    const res = new ListNode(0);
    let p = res;
    let p1 = l1;
    let p2 = l2;

    while(p1 && p2) {
        if (p1.val < p2.val) {
            p.next = p1;
            p1 = p1.next;
        } else {
            p.next = p2;
            p2 = p2.next;
        }
        p = p.next;
    }
    if (p1) {
        p.next = p1;
    }

    if (p2) {
        p.next = p2;
    }
    return res.next;
};

猜数字大小

• 解题步骤：二分搜索，通过调用 guess 函数，来判断中间元素是否是目标值；

• 解题思路：从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束；如果目标值大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找；

https://leetcode-cn.com/problems/guess-number-higher-or-lower/

• 时间复杂度：O(m + n)
• 空间复杂度：O(1)

/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function(n) {
    let low = 1;
    let high = n;
    while(low <= high) {
        const mid = Math.floor((low + high) / 2);
        const res = guess(mid)
        if (res === 0) {
            return mid;
        } else if (res === 1) {
            low  = mid + 1;
        } else {
            high = mid - 1;
        }
    }
};

阅读量：

评 论：