本篇文章可以收获的知识：
- 排序算法
冒泡排序的实现及分析选择排序的实现及分析插入排序的实现及分析归并排序的实现及分析快速排序的实现及分析
- 搜素算法
顺序搜索的实现及分析二分搜索的实现及分析
- 两道LeetCode算法题巩固
搜索与排序 - 如何分析
时间复杂度和空间复杂度
排序算法
冒泡排序
// 实现思路
// 比较所有相邻，如果第一个比第二个大，则替换位置
// 一轮下来，可以保证最后一个数是最大的
// 执行n - 1轮就可以完成排序
// 时间复杂度是O(n ^ 2)
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 tmp = currentItem
this[j] = this[j + 1]
this[j + 1] = tmp
}
}
}
}
const arr = [5, 4, 3, 2, 1]
arr.bubbleSort()
选择排序
// 实现思路
// 找到第一个最小的值，将它保存在第一位
// 找到第二个最小的值，将它保存在第二位
// 以此类推，执行n - 1轮之后，排序完成
// 时间复杂度是O(n ^ 2)
Array.prototype.selectionSort = function () {
for (let i = 0; i < this.length - 1; i++) {
let minIndex = i
for (let j = i; j < this.length; j++) {
if (this[minIndex] > this[j]) {
minIndex = j
}
}
if (i !== minIndex) {
let tmp = this[minIndex]
this[minIndex] = this[i]
this[i] = tmp
}
}
}
const arr = [3, 1, 5, 9, 4]
arr.selectionSort()
插入排序
// 插入排序相对于选择排序、冒泡排序来说，效率相对较高，但是还是不推荐在实际应用中使用
// 实现思路
// 从第二个往前比
// 前面比后面大的往后排
// 以此类推，执行n - 1轮之后，排序完成
// 时间复杂度是O(n ^ 2)
Array.prototype.insertionSort = function () {
for (let i = 1; i < this.length; i++) {
let tmp = this[i]
let j = i
while (j > 0) {
if (this[j - 1] > tmp) {
this[j] = this[j - 1]
} else {
break
}
j -= 1
}
this[j] = tmp
}
}
const arr = [3, 1, 5, 9, 4]
arr.insertionSort()
归并排序
// 归并排序比冒泡排序、选择排序、插入排序的效率都高，而且归并排序是可以应用到实际的项目中的，火狐浏览器的sort算法使用的就是归并排序
// 实现思路
// 分：把数组分成两半，再递归地对子数组进行分操作，直到全部子数组分成一个个单独的数
// 合：把两个数合并为有序的数组，再对有序的数组进行合并，直到全部子数组合并为一个完整的数组
// 新建一个空数组res，用于存放最终排序后的数组
// 比较两个有序数组的头部，较小者出队并推入res中
// 如果两个数组还有值，重复上一步操作
// 分的时间复杂度是O(logn)
// 合的时间复杂度是O(n)
// 归并排序时间复杂度是O(nlogn)
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] ? orderRight.shift() : orderLeft.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((v, k) => (this[k] = v))
}
const arr = [3, 1, 5, 9, 4]
arr.mergeSort()
快速排序
// 快速排序比冒泡排序、选择排序、插入排序的效率都高，而且快速排序是可以应用到实际的项目中的，曾经的Chrome的sort算法使用的是快速排序
// 实现思路
// 分区：从数组中任意选择一个“基准”，所有比基准小的元素放在基准前面，所有比基准大的元素放在基准后面
// 递归：递归地对基准前后的子数组进行分区
// 递归的时间复杂度：O(logn)
// 分区操作的时间复杂度是O(n)
// 快速排序的时间复杂度是：O(nlogn)
Array.prototype.quickSort = function () {
const rec = (arr) => {
if ([0, 1].includes(arr.length)) return arr
const left = []
const right = []
const mid = arr[0]
for (let i = 1; i < arr.length; i++) {
const c = arr[i]
c > mid ? right.push(c) : left.push(c)
}
return [...rec(left), mid, ...rec(right)]
}
const res = rec(this)
res.forEach((v, k) => (this[k] = v))
}
const arr = [5, 3, 6, 2, 8, 0]
arr.quickSort()
搜索算法
顺序搜索
// 实现思路
// 遍历数组
// 找到目标值相等的元素，就返回它的下标
// 遍历结束后，如果没有搜索到目标值，就返回-1
// 时间复杂度是O(n)
Array.prototype.sequentialSearch = function (target) {
for (let i = 0; i < this.length; i++) {
if (this[i] === target) {
return i
}
}
return -1
}
[5, 3, 6, 2, 8, 0].sequentialSearch(3)
二分搜索
// 二分搜索（折半搜索），前提是这个数组是有序的
// 实现思路
// 从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束
// 如果目标值大于或小于中间元素，则在大于或小于中间元素的那一半数组中搜索
// 时间复杂度是O(logn)
Array.prototype.binarySearch = function (target) {
let low = 0
let high = this.length - 1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
const c = this[mid]
if (c > target) {
high = mid - 1
} else if (c < target) {
low = mid + 1
} else {
return mid
}
}
return -1
}
console.error([1, 2, 3, 4, 5].binarySearch(3)) // 2
LeetCode算法题：题号21，合并两个有序链表
解题思路：
- 与归并排序中合并两个有序数组很相似
- 将数组替换成链表即可
解题步骤：
- 新建一个新链表，作为返回结果
- 用指针遍历两个有序链表，并比较两个链表的当前节点，较小者先接入新链表，并将指针后移一步
- 遍历结束，返回新链表
代码实现：
/**
* 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)
let p = n
let p1 = l1
let p2 = l2
while(p1 && p2) {
if (p1.val > p2.val) {
p.next = p2
p2 = p2.next
} else {
p.next = p1
p1 = p1.next
}
p = p.next
}
if (p1) {
p.next = p1
}
if (p2) {
p.next = p2
}
return res.next
};
由于代码中使用了while循环，循环的最大次数是两个链表的数量之和，所以时间复杂度是O(n)，n是两个链表的数量之和。
由于代码中没有额外的使用线性增长的数据结构，所以空间复杂度是O(1)。
LeetCode算法题：题号374，猜数字大小
解题思路：
- 这到题明显使用的二分算法解题
- 调用guess函数，来判断中间元素是否是目标值
解题步骤：
- 从数组中间元素取值，如果中间元素正好是目标值，则搜索结束
- 如果目标值大于或者小于中间元素，则在数组大于或小于中间元素的那一半搜索
代码实现：
/**
* 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 = 0;
let high = n;
while(low <= high) {
const mid = Math.floor((low + high) / 2);
const ret = guess(mid)
if (ret === -1) {
high = mid - 1
} else if (ret === 1) {
low = mid + 1
} else if (ret === 0) {
return mid
}
}
};
代码中使用的是二分搜索，所以时间复杂度是O(logn)。
代码中没有使用到线性增长的数据结构，所以空间复杂度是O(1)。
最后，希望读者可以通过本篇文章对排序与搜索有一定的认识和觉悟。。。。。。
