进阶算法之“搜索算法”
一、理论
1. 排序和搜索简介
- 排序：把某个乱序的数组变成升序或降序数组
- 搜索：找出数组中某个元素的下标
1.1 js中的排序和搜索
- js中的排序：sort()
- js中的搜索：indexOf()
1.2 排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
1.3 搜索算法
- 顺序搜索
- 二分搜索
2. js实现排序
2.1 冒泡排序
2.2.1 思路
- 比较相邻元素，如果第一个比第二个大，则交换他们
- 一轮下来，保证最后一个数是最大的
- 执行n-1轮即完成排序
2.2.2 动画演示
2.2.3 coding part
Array.prototype.bubbleSort = function () {
for(let i = 0; i < 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
}
}
}
}
2.2.4 时间复杂度
- 时间复杂度：O(n^2)
2.2 选择排序
2.2.1 思路
- 找到数组的最小值，选中并将其放在第一位
- 找到数组的第二小值，选中并将其放在第二位
- 以此类推，执行n-1轮
2.2.2 动画演示
2.2.3 coding part
Array.prototype.selectionSort = function () {
for(let i = 0; i < this.length-1; i++) {
let indexMin = i
for(let j = i; j < this.length; j++) {
if(this[j] < this[indexMin]) {
indexMin = j
}
}
if(indexMin !== i) {
const temp = this[i]
this[i] = this[indexMin]
this[indexMin] = temp
}
}
}
2.2.4 时间复杂度
- 时间复杂度：O(n^2)
2.3 插入排序
2.3.1 思路
- 从第二个数开始往前比
- 比他大就往后排
- 以此类推进行到最后一个数
2.3.2 动画演示
2.3.3 coding part
Array.prototype.insertionSort = function () {
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
}
}
2.3.4 时间复杂度
- 时间复杂度：O(n^2)
2.4 归并排序
2.4.1 思路
- 分：把数组劈成两半，再递归得将子数组进行“分”操作，直到分成一个个单独的数
- 合：把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组合并成一个完整数组
合并两个有序数组
- 新建一个空数组res，用于存放最终排序后的数组
- 比较两个有序数组的头部，较小者出队并推入res中
2.4.2 动画演示
2.4.3 coding part
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)
}
2.4.4 时间复杂度
- 分的时间复杂度：O(logn)
- 合的时间复杂度：O(n)
- 时间复杂度：O(nlogn)
2.5 快速排序
2.5.1 思路
- 分区：从数组中任意选择一个基准，所有比基准小的元素放在基准前，比基准小的元素放在基准后
- 递归：递归地对基准前后的子数组进行分区
2.5.2 动画演示
2.5.3 coding part
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 < this.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)
}
2.5.4 时间复杂度
- 递归的时间复杂度：O(logn)
- 分区的时间复杂度：O(n)
- 时间复杂度：O(nlogn)
3. js实现搜索
3.1 顺序搜索
3.1.1 思路
- 遍历数组
- 找到跟目标值相等的元素，返回其下标
- 遍历结束后，若没有找到相等元素则返回-1
3.1.2 coding part
Array.prototype.sequentialSearch = function(item) {
for(let i = 0; i < this.length; i++) {
if(this[i] === item) {
return i
}
}
return -1
}
3.1.3 时间复杂度
- 时间复杂度：O(n)
3.2 二分搜索
前提：数组有序
3.2.1 思路
- 从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束
- 如果目标值大于或小于中间元素，则在大于或小于中间元素的那一半数组中搜索
3.2.2 coding part
Array.prototype.binarySearch = function(item) {
let low = 0, 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
}
3.2.3 时间复杂度
- 时间复杂度：O(logn)
二、刷题
1. 合并两个有序链表（21）
1.1 题目描述
- 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
1.2 解题思路
- 与归并排序中合并两个有序数组很相似
- 将数组替换成链表
1.3 解题步骤
- 新建一个新链表，作为返回结果
- 用指针遍历两个有序数组，并比较两个链表当前节点，较小者先接入新链表并将指针后移一步
- 链表遍历结束，返回新链表
function mergeTwoLists(l1, l2) {
const res = new ListNode(0);
let p = res, p1 = l1, 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
}
1.4 时间复杂度&空间复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(1)
2. 猜数字大小（374）
2.1 题目描述
- 猜数字游戏的规则如下：
- 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
- 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
- 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
- -1：我的数字比较小 pick < num
- 1：我的数字比较大 pick > num
- 0：恭喜！你猜对了！pick == num
2.2 解题思路
输入：n = 10, pick = 6
输出：6
- 二分搜索
- 调用guess函数来判断中间元素是否是目标值
2.3 解题步骤
- 二分搜索
function guessNumber(n) {
let low = 1, 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 if(res === -1) {
high = mid - 1
}
}
}
2.4 时间复杂度&空间复杂度
- 时间复杂度：O(logn)
- 空间复杂度：O(1)