龙空技术网

2022.2,我的算法学习笔记

前端晚间课 227

前言:

现在看官们对“双向链表排序算法保证复杂度”大致比较关切,我们都想要了解一些“双向链表排序算法保证复杂度”的相关内容。那么小编同时在网上网罗了一些对于“双向链表排序算法保证复杂度””的相关资讯,希望大家能喜欢,各位老铁们一起来了解一下吧!

前端开发是否有必要知道或者精通数据结构和算法?答案是肯定的,在实际的应用中,做前端开发并不会用到复杂的数据结构和算法,但是,想码出好代码却应该有个扎实的数据结构和算法基础,处理问题的思路也会不同,会算法的前端会想尽办法让代码得到更低的时间复杂度/空间复杂度,应对复杂的问题,会更加信手拈来。自认为自己就是个算法渣渣,遇到问题,就是嵌套几层循环,暴力输出,虽然能解决80%的问题,但是一旦真遇到棘手需求确实是寸步难行。

举个例子,

去年在接到公司的一个需求,需要针对面包屑导航来模拟一个类似浏览器前进后退的功能(当然对高手来说,应该很简单,哈哈),绞尽脑汁,写出来后,虽然最终实现了,但是bug层出不穷,改的是心力交瘁。今年在看相关算法的书时,里面一章关于介绍的小节,就介绍了如何用栈来实现浏览器的前进、后退功能,下面贴一下具体图示:

于是感慨算法真是个好东西,以前觉得前端不会用到那么多算法知识的,现在才知道算法的重要性,于是想在2022年花些时间把这个短板给补一下,下面是2月份学习的基础算法知识,所记下来的一些笔记(相对基础)。

单项链表与双向链表

let head = { next: '...', data: '...' };// 链表查找const find = (value) => {    const p = head;    while (p !== null && p.data !== value) {        p.next;    }    return p;}// 链表插入const insert = (b, x) => {    if (x === null) {        x.next = head;        head = x;    } else {        x.next = b.next;        b.next = x;    }}// 链表删除const remove = (b, x) => {    if (x === null) {        x.next = head;        head = x;    } else {        b.next = b.next.next;    }}复制代码
单项链表与双向链表
interface Node {    data: number;    prev: Node;    next: Node;}let head: Node = null;/*******给定值删除的单向链表、双向链表,时间复杂度为O(n)******/// 单向链表const oneWayRmove = (val: number) => {    let q: Node = head;    let p: Node = null; // 前驱节点    while(q != null && q.data != val) {        p = q;        q = q.next;    }    if (q != null) {        if (p == null) { // 尾节点            head = q.next;        } else {            p.next = q.next;        }    }}// 双向链表const twoWayRmove = (val: number) => {    let q: Node = head;    while(q != null && q.data != val) {        q = q.next;    }    if (q != null) {        if (q.prev == null) { // 尾节点            head = q.next;        } else {            q.prev.next = q.next;        }    }}/*******给定指针的删除的单向链表->时间复杂度为O(n)、双向链表->时间复杂度O(1)******/// 单向链表const oneWayPointerRmove = (q: Node) => {    if (q == null) { return; }    if (q == head) {        head = q.next;    }    let p: Node = head;    while (p != null && p.next != q) {        p = p.next;    }    if (p.next != null) {        p.next = q.next;    }}// 双向链表const twoWayPointerRmove = (q: Node) => {    if (q == null) return;    if (q.prev == null) {        head = q.next;    } else {        q.prev.next = q.next;    }}复制代码
反转链表

思路: 遍历链表, 暂存当前节点next指针, 改变当前节点next指向, 更新前驱节点prev, 赋值下一遍历节点

// 单链表反转const reverseList = (head) => {    let cur: Node = head;    let prev: Node = null;    while (cur != null) { // 遍历链表        const temp = cur.next; // 暂存当前节点next指针        cur.next = prev; // 改变当前节点next指向        prev = cur; // 更新前驱节点        cur = temp; // 赋值下一遍历节点    }}复制代码
获取链表中间节点
const middleNode = function(head) {    if (head == null) return;    const results = [];    let curNode = head;    while(curNode != null) {        results.push(curNode);        curNode = curNode.next;    }    if (results.length % 2 === 0) {        return [results[parseInt(results.length / 2 -1)], results[parseInt(results.length /2)]];    } else {        return results[parseInt(results.length /2)];    }};复制代码
查找倒数第k个节点

思路一: 得到链表长度,再遍历一次链表,第k个节点,其实就是第n-k个节点 思路二: 快慢指针

interface Node {    data: number;    next: Node;}// 第k个节点,其实就是第n-k个节点const lookupForK1 = (head: Node, k: number) => { let cur = head; let node = head; let n = 0; while (cur != null) {    cur = cur.next;    n++; } for (let i = 0; i < n-k; i++) {    node = node.next; } return node;}// 快慢指针const lookupForK2 = (head: Node, k: number) => {    let fast = head; let slow = head;    for (let i = 0; i < k; i++) {        fast = fast.next;    }        while (fast) {        [fast, slow] = [fast.next, slow.next];    }    return slow;}复制代码
基于链表的LRU缓存淘汰算法

思路:维护一个有序的单链表,越靠近链表尾部的节点存储的是越早访问的数据,当访问某个数据的时候,会从链表的表头节点开始遍历链表,

1)如果查找得到节点,将其从原来位置删除,插入到链表头部2)如果查找不到节点,对应会分两种情况: 缓存空间未满,将新的数据节点插入链表头部 缓存空间已满,删除链表尾部节点,将新的数据节点插入链表头部

// 基于链表的LRU缓存淘汰算法/* 实现思路,维护一个有序的单链表,越靠近链表尾部的节点存储的是越早访问的数据,当访问某个数据的时候,会从链表的表头节点开始遍历链表,1)如果查找得到节点,将其从原来位置删除,插入到链表头部2)如果查找不到节点,对应会分两种情况:   缓存空间未满,将新的数据节点插入链表头部   缓存空间已满,删除链表尾部节点,将新的数据节点插入链表头部*/interface Node {    data: number;    next: Node | null;}let head: Node = null; // 头节点let cacheSize = 10; // 最大缓存空间const lruLook = (val: number) => {  let q: Node = head;  let p: Node = null; // 前驱第一个节点  let e: Node = null; // 前驱第二个节点  let i = 0;   while (q !== null && q.data !== val) {      i++;      e = p;      p = q;      q = q.next;  }  if (q !== null) {    if (p === null) { // q为头部节点        return q;    } else {        // 将其从原来位置删除,插入到链表头部        p.next = q.next;        q.next = head;        head = q;        return q;    }  } else {      // 创建新节点      const n = {        data: val,        next: null      };      if (i === 0) { // 存储空间为空        head = n;      } else if (i < cacheSize) { // 存储空间未满        n.next = head;      } else { // 存储空间未满        e.next = null; // 此时p为尾节点,而e是倒数第二个节点        n.next = head;      }      return n;  }}复制代码
冒泡排序

思路: 对n个数进行排序,每次都是由前一个数跟后一个数比较,每循环一轮, 就可以将最大的数移到数组的最后, 总共循环n-1轮,完成对数组排序。

const bubbleSort  = (arr) => {    if (arr === null) { return; }    //i控制循环次数,长度为len的数组只需要循环len-1次,i的起始值为0所以i<len-1    for (let i = 0; i < arr.length - 1; i++) {        for (let j = 0; j < arr.length - i - 1; j++) {            // j控制比较次数,第i次循环内需要比较len-i次            // 但是由于是由arr[j]跟arr[j+1]进行比较,所以为了保证arr[j+1]不越界,j<len-i-1            if (arr[j] > arr[j + 1]) {                //如果前一个数比后一个数大,则交换位置将大的数往后放。                const temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;                            }                    }    }}复制代码
选择排序

思路: 冒泡排序的改良版,不再是前一个数跟后一个数相比较, 而是在每一次循环内都由一个数去跟 所有的数都比较一次,每次比较都选取相对较小的那个数来进行下一次的比较,并不断更新较小数的下标。

这样在一次循环结束时就能得到最小数的下标,再通过一次交换将最小的数放在最前面,通过n-1次循环之后完成排序

const selectSort  = (arr) => {    if (arr === null) { return; }    //i控制循环次数,长度为len的数组只需要循环len-1次,i的起始值为0所以i<len-1    for (let i = 0; i < arr.length - 1; i++) {        //minIndex 用来保存每次比较后较小数的下标。        let minPos = i;        //j控制比较次数,因为每次循环结束之后最小的数都已经放在了最前面,        //所以下一次循环的时候就可以跳过这个数,所以j的初始值为i+1而不需要每次循环都从0开始,并且j<len即可        for (let j = i + 1; j < arr.length; j++) {            //每比较一次都需要将较小数的下标记录下来            if (arr[minPos] > arr[j]) {                minPos = j;            }        }        //当完成一次循环时,就需要将本次循环选取的最小数移动到本次循环开始的位置。        if (minPos != i) {            const temp = arr[minPos];            arr[minPos] = arr[i];            arr[i] = temp;        }    }}复制代码
插入排序

思路:首先就默认数组中的第一个数的位置是正确的,即已经排序。 然后取下一个数,与已经排序的数按从后向前的顺序依次比较,如果该数比当前位置排好序的数小,则将排好序的数的位置向后移一位。 重复上一步骤,直到找到合适的位置。

找到位置后就结束比较的循环,将该数放到相应的位置。

const insertSort  = (arr) => {    if (arr === null) { return; }    //i控制循环次数,因为已经默认第一个数的位置是正确的,所以i的起始值为1,i<len,循环len-1次    for (let i = 1; i < arr.length; i++) {        let j = i; // 变量j用来记录即将要排序的数的位置即目标数的原位置        let target= arr[j];        //while循环用来为目标值在已经排好序的数中找到合适的位置,        //因为是从后向前比较,并且是与j-1位置的数比较,所以j>0        while (j > 0 && target < arr[j-1]) {            arr[j] = arr[j-1];            j--;        }        arr[j] = target;     }}复制代码
归并排序

思路: 分而治之的思想,递归实现,将数组每次递归切分成两个小数组,再分别递归,终止条件是小数组的起始下标大于等于结束小标,

递归公式: mergeSort(p,r) = merge(mergeSort(p,q), mergeSort(q+1,r))[p>=r]

合并方法merge:我们能获得两个小数组的下标,申请长度为r-p + 1的临时数组tempArr,同时遍历两个小数组,填充临时数组tempArr,计算哪个小数组有剩,则补到临时数组tempArr后面,最后把临时数组tempArr,整合到原数组arr中

const merge = (arr, start, center, afterCenter, end) => {    const tempArr = new Array(end - start + 1); // 申请一个大小为end - start + 1的临时数组    let i = start, j = afterCenter, k = 0, surplusStart, surplusEnd;    // 切分的小数组,前后下标我们都有,同时遍历,填充临时数组    while (i <= center && j <= end) {        if (arr[i] <= arr[j]) {            tempArr[k++] = arr[i++];        } else {            tempArr[k++] = arr[j++];        }    }    // 获得遍历完后剩下的数组    surplusStart = i;    surplusEnd = center;    if (j <= end) {        surplusStart = j;        surplusEnd = end;    }    while (surplusStart <= surplusEnd) {        tempArr[k++] = arr[surplusStart++];    }    for (let index = 0; index <= end - start; index++) {       arr[start + index] = tempArr[index];    }}const mergeSort_c = (arr, start, end) => {    // 终止条件    if (start >= end)  {        return;    }    const center = Math.floor((start + end) / 2);    // 分而治之,大问题切分成小问题,用递归    mergeSort_c(arr, start, center);    mergeSort_c(arr, center + 1, end);    // 归并    merge(arr, start, center, center + 1, end);}// 入参 arr => 待排序数组, n => 数组大小const mergeSort = (arr, n) => {  mergeSort_c(arr, 0, n-1);}// 运行结果:[1, 2, 3, 3, 7, 8, 9, 11]const handleArr = [11, 8, 3, 9, 7, 1, 2, 3];mergeSort(handleArr, 8);复制代码
快速排序

思路:分而治之的思想,递归实现,与归并的区别,没有空间换时间,核心就是找到分区临界点,把小于临界点的数值,通过数组交换。换至临界点前面,依次递归

递归公式: quicksort(p,r) = (q = partition = (A, p, r)) + quicksort(p,q-1) + quicksort(q+1,r) [p>=r]

分区方法partition:以该入参数组区间最后一个值为分区点,入参数组第一个数值为起始游标,遍历该区间数组,小于分区点qivot的,交换下标i,j的值, 游标i进一,最终得到的i之前的值都是小于分区点qivot值的,交换分区点与下标r的值,返回分区点下标,那么就分区成功了

// 核心:分区方法const partition = (A, p, r) => {    const qivot = A[r]; // 以该区间最后一个值为分区点    let i = p; // 起始游标    // 遍历该区间数组,小于分区点qivot的,交换下标i,j的值, 游标i进一,最终得到的i之前的值都是小于分区点qivot值的    for (let j = p; j < r; j++) {        if (A[j] < qivot) {            [A[i], A[j]] = [A[j], A[i]];            i++;        }    }    // 交换分区点与下标i的值,那么就分区成功了    [A[i], A[r]] = [A[r], A[i]];    return i; // 返回分区点下标}const quicksort_c = (A, start, end) => {    if (start >= end) { return; } // 终止条件    const qivot = partition(A, start, end); // 分区    // 数组会被分成[start...qivot-1]、qivot、 [qivot+1...end]    quicksort_c(A, start, qivot-1);    quicksort_c(A, qivot+1, end);}// 快速排序const quicksort = (A, n) => {    quicksort_c(A, 0, n-1);}// 运行结果:[1, 2, 3, 3, 7, 8, 9, 11]const handleArr = [11, 8, 3, 9, 7, 1, 2, 3];quicksort(handleArr, 8);复制代码
煎饼排序

思路:遍历数组(反向遍历)找到最大值的下标,如arr[0...k],做一次数组翻转, k会变成第一个下标,然后对整个数组arr[0, end]做一次数组翻转,那么数组最大值便会出现数组的尾部,依次遍历,得到排序好的数组。

// 反转数组const reverse = (arr, end) => {    for (let i = 0, j = end; i < j; i++,j--) {        let temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }}var pancakeSort = function(arr) {const ret = []; for (let n = arr.length; n > 1 ;n--) {    let index = 0;    for (let i = 1; i < n; i++) {        if (arr[index] <= arr[i]) {            index = i        }    }    if (index === n - 1) {        continue;    }    reverse(arr, index);    reverse(arr, n - 1);    ret.push(index+1);    ret.push(n);}    return ret;};

标签: #双向链表排序算法保证复杂度