js 快排与冒泡

作者: blossom_绽放 | 来源:发表于2019-08-27 08:09 被阅读0次

js 快排与冒泡
算法修炼
排序
【数据结构-排序】交换排序
排序算法
冒泡快排堆排
快排，归并，冒泡
冒泡、快排、归并
各种排序算法代码
《数据结构与算法之美》笔记—快速排序

虽然说算法很复杂，但是在我的工作经验中，掌握这2个基本就够处理大部分前端业务工作（不要跟我抬杠哦，你要面试肯定不够用），所以总结一下~~

快排

const quickSort = l => {
    if (l.length < 2) {
        return l
    }
    // 我就把每次数组第一个元素当基点  这样理解简单
    let pivot = l[0]
    let left = []
    let right = []
    l.slice(1).forEach(e => {
        if (e >= pivot) {
            right.push(e)
        } else {
            left.push(e)
        }
    })
    return quickSort(left)
        .concat(pivot)
        .concat(quickSort(right))
}

冒泡

// 相邻元素两两对比，元素交换，大的元素交换到后面
const jsSort = l => {
    let len = l.length
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
            if (l[j] > l[j + 1]) {
                const e = l[j]
                l[j] = l[j + 1]
                l[j + 1] = e
            }
        }
    }
    return l
}

如果为了面试，你可能需要知道下面这些

class Node {
constructor(x) {
this.element = x
this.next = null
}
}

class LinkedList {
constructor() {
this.head = null
}

length() {
    let index = 0
    let node = this.head
    while (node != null) {
        index += 1
        node = node.next
    }
    return index
}

lastNode() {
    // 2, 返回单链表的最后一个节点
    // 找到最后一个 Node
    let n = this.head
    while (n != null) {
        if (n.next === null) {
            return n
        }
        n = n.next
    }
    return n
}

kthNode(i) {
    // 3, 返回单链表第 i 个节点
    let n = this.head
    let index = 0
    while (n != null) {
        if (index + 1 == i) {
            return n
        }
        n = n.next
        index++
    }
    return n
}

nLast(x) {
    // 4, 返回单链表倒数第 n 个节点
    let len = this.length()
    let index = len - x
    return this.kthNode(index)
}

hasX(x) {
    // 5, 判断单链表中是否有值为 x 的节点
    let n = this.head
    while (n != null) {
        if (n.element == x) {
            return true
        }
        n = n.next
    }
    return false
}

middle() {
    // 6, 查找单链表的中间节点
    if (this.length() % 2 === 0) {
        return null
    } else {
        let index = Math.floor(this.length() / 2)
        return this.kthNode(index)
    }
}

append(e) {
    // 7, 给单链表末尾插入一个节点
    let node = new Node(e)
    // 找到最后一个 Node
    let n = this.head
    if (n == null) {
        this.head = node
    } else {
        while (n.next != null) {
            n = n.next
        }
        n.next = node
    }
    return this
}

prepend(x) {
    // 8, 给单链表头部插入一个元素
    let node = new Node(x)
    node.next = this.head
    this.head = node
    return this
}

insertAfter(n, x) {
    // 9, 给单链表第 n 个节点后插入一个元素
    let node = new Node(x)
    let index = 0
    let node2 = this.head
    while (n != null) {
        if (index == n) {
            break
        }
        node2 = node2.next
        index++
    }
    node.next = node2.next
    node2.next = node
    return this
}

insertLastN(n, x) {
    // 10, 给单链表倒数第 n 个节点前插入一个元素
    let nn = this.nLast(n)
    if (nn != null) {
        if (nn == this.head) {
            this.prepend(x)
        } else {
            let node = new Node(x)
            let nn = this.nLast(n + 1)
            node.next = nn.next
            nn.next = node
        }
    }
    return this
}

deleteN(n) {
    // 11, 删除单链表第 n 个节点
    if (n == 0) {
        let node = this.head
        this.head = this.head.next
        return node.element
    } else {
        let node = this.kthNode(n - 1)
        if (node != null && node.next) {
            let dlete_node = node.next
            node.next = node.next.next
            return dlete_node.element
        }
    }
}

deleteX(x) {
    // 12, 删除单链表中值为 x 的节点
    let n = this.head
    if (n && n.element == x) {
        return this.deleteN(0)
    }
    while (n != null) {
        if (n.next && n.next.element == x) {
            n.next = n.next.next
            break
        }
        n = n.next
    }
    return this
}

deleteLastN(n) {
    // 13, 删除单链表倒数第 n 个节点
    let index = this.length() - n
    return this.deleteN(index)
}

// 返回反转后的单链表
reverse() {
    let node = this.head
    let new_node = null
    while (node != null && node.next != null) {
        new_node = node.next
        node.next = new_node.next
        new_node.next = this.head
        this.head = new_node
    }
    return this
}

isPalindrome() {
    // 15, 判断一个链表是否是回文链表 回文链表自己查加深印象
    let new_linked_list = this.reverse()
    return JSON.stringify(new_linked_list) == JSON.stringify(this)
}

isCircle() {
    // 16, 判断一个链表是否是环形链表 不懂自己查加深印象
    // 本题用双指针, a 一次走一格 b 一次走两格，如果相遇说明有环形 这个方法时间空间复杂度是最优解
    let slow = this.head
    let fast = this.head.next
    while (fast && fast.next) {
        if (slow == fast) {
            return true
        }
        slow = slow.next
        fast = fast.next.next
    }
    return false
}

copy() {
    // 17, 返回一个单链表的复制
    let new_linked_list = new LinkedList()
    let n = this.head
    while (n != null) {
        new_linked_list.append(n.element)
        n = n.next
    }
    return new_linked_list
}

powerCopy() {
    // 18, 返回一个环形链表的复制
    let map = new Map()
    let n = this.head
    let new_linked_list = new LinkedList()
    let index = 0
    while (n != null) {
        if (map.get(n)) {
            break
        }
        map.set(n, true)
        new_linked_list.append(n.element)
        n = n.next
        index++
    }
    return new_linked_list
}

_mergeNodeList(l1, l2) {
    if (l1 == null) {
        return l2
    }
    if (l2 == null) {
        return l1
    }
    let node
    if (l1.element < l2.element) {
        node = l1
        node.next = this._mergeNodeList(l1.next, l2)
    } else {
        node = l2
        node.next = this._mergeNodeList(l1, l2.next)
    }

    return node
}

mergeList(linkedList) {
    // 19, 合并两个有序链表并保持有序 返回一个新链表
    let n1 = this.head
    let n2 = linkedList.head

    let new_linked_list = new LinkedList()
    let nodeList = this._mergeNodeList(n1, n2)
    new_linked_list.head = nodeList
    return new_linked_list
}

josephList(m) {
    // 20, 本题是约瑟夫环问题
    // 1, 2, 3 ..., n 这 n 个数字排成一个圆圈 (首尾相连)
    // 从数字 1 开始每次从这个圆圈里删除第 m 个数字, 删除后从下一位继续从1开始删除第 m 个数字
    // 求出这个圆圈里剩下的最后一个数字
    let n = this.head
    let index = 1
    while (n !== null) {
        if (this.head == this.head.next) {
            console.log('game over', this)
            break
        }
        if (index == m - 1) {
            if (this.head == n.next) {
                this.head = n.next.next
            }
            n.next = n.next.next
            n = n.next
            index = 1
        } else {
            n = n.next
            index++
        }
    }
}

rearrange(x) {
    // 1 给一个单链表和一个值 x, 对它进行分割, 所有小于x的结点排在大于或等于x的结点之前
    let before = new LinkedList()
    let after = new LinkedList()
    let n = this.head
    while (n != null) {
        if (n.element < x) {
            before.append(n.element)
        } else {
            after.append(n.element)
        }
        n = n.next
    }
    let nn = after.head
    while (nn != null) {
        before.append(nn.element)
        nn = nn.next
    }
    return before
}

circleHead() {
    // 2 给一个链表, 返回环形链表中环形开始的节点, 如果没有环形, 返回 null
    let slow = this.head
    let fast = this.head.next
    while (fast && fast.next) {
        if (slow == fast) {
            return slow
        }
        slow = slow.next
        fast = fast.next.next
    }
    return null
}

_findmiddleList(left) {
    let n = left
    if (n == null || n.next == null) {
        return n
    }
    let slow = left
    let fast = left
    let slow_next = left
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next
        fast = fast.next.next
        slow_next = slow.next
    }
    slow.next = null
    return slow_next
}

_reverse(node) {
    // 没有头结点的链表翻转
    if (node == null || node.next == null) {
        return node
    }
    let pre = node
    let cur = node.next
    pre.next = null
    while (cur != null) {
        let tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    }
    return pre
}

reorder() {
    // 3
    // 给一个链表, 将原链表 L0 -> L1 -> L2 -> ... -> Ln-1 -> ln 排序为
    // L0 -> L1 -> Ln -> L2 -> Ln-1 -> ...
    // 要求: 不能修改节点的值

    let n = this.head
    if (n == null || n.next == null) {
        return
    }
    let left = this.head.next

    let right = this._findmiddleList(left)
    right = this._reverse(right)

    // 交替合并
    let tmp
    while (left != null || right != null) {
        if (left != null) {
            tmp = left.next
            n.next = left
            left = tmp
            n = n.next
        }
        if (right != null) {
            tmp = right.next
            n.next = right
            right = tmp
            n = n.next
        }
    }

    return this
}

rotateList(k) {
    // 4
    // 给一个链表, 将列表向右旋转 k 个下标, 其中 k 是非负数
    // 例子:
    //     Input: 1->2->3->4->5->NULL, k = 2
    //     Output: 4->5->1->2->3->NULL
    //     Input: 0->1->2->NULL, k = 4
    //     Output: 2->0->1->NULL
    // 其实就是移动
    let len = this.length()
    let step = k % len
    let node = this.nLast(step + 1)
    if (node == null) {
        return node
    }
    let n = node.next
    node.next = null
    let head = this.head
    this.head = n
    while (n != null && n.next != null) {
        n = n.next
    }
    n.next = head
    return this
}
static quickSort(list) {
    if (list.length < 2) {
        return list
    }
    let left = []
    let right = []
    let p = list[0]
    for (let i = 1; i < list.length; i++) {
        const e = list[i]
        if (e < p) {
            left.push(e)
        } else {
            right.push(e)
        }
    }
    return LinkedList.quickSort(left).concat([p]).concat(LinkedList.quickSort(right))
}

_sortmerge(l1, l2) {
    let node = new Node(-1)
    let n = node
    while (l1 != null && l2 != null) {
        if (l1.element < l2.element) {
            n.next = l1
            l1 = l1.next
        } else {
            n.next = l2
            l2 = l2.next
        }
        n = n.next
    }
    if (l1) {
        n.next = l1
    }
    if (l2) {
        n.next = l2
    }

    return node.next
}

_sortNodeList(nodeList) {
    let head = nodeList
    if (head == null || head.next == null) {
        return head
    }
    let pre = head
    let slow = head
    let fast = head
    while (fast && fast.next) {
        pre = slow
        slow = slow.next
        fast = fast.next.next
    }
    pre.next = null
    return this._sortmerge(this._sortNodeList(head), this._sortNodeList(slow))
}

sortList() {
    //     给一个链表, 将链表排序
    //     要求: 时间复杂度为 O(nlogn)
    let n = this.head
    let nodeList = this._sortNodeList(n)
    this.head = nodeList
    return this
}

reverseMn(m, n) {
    // 6
    // 给一个单链表和正整数 m, n(m < n), 从 m 到 n 开始反转
    let start = this.kthNode(m - 1)
    let len = n - m
    while (len > 0) {
        let node = this.kthNode(n - 1)
        let end = node.next
        node.next = node.next.next
        end.next = start.next
        start.next = end
        start = start.next
        len--
    }
    return this
}

deduplication() {
    // 7
    // 给一个有序的单链表, 删除所有有重复 value 的节点, 只留下原始列表中不同的 value
    let n = this.head
    if (n == null || n.next == null) {
        return this
    }
    let value = this.head.element
    while (n != null && n.next != null) {
        // 重复
        if (n.next.element == value) {
            n.next = n.next.next
        } else {
            n = n.next
            value = n.element
        }
    }
    return this
}

static addNumber(a, b) {
    // 8
    // 给两个非空且长度不一定相同的单链表, 表示两个非负整数
    // 数字以相反的顺序存储(个位在前), 每个节点都包含一个 value, 将两个 value 相加并返回链表
    // 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    // 输出：7 -> 0 -> 8
    // 原因：342 + 465 = 807

    let num1 = []
    let head_a = a.head
    while (head_a != null) {
        num1.unshift(head_a.element)
        head_a = head_a.next
    }

    let num2 = []
    let head_b = b.head
    while (head_b != null) {
        num2.unshift(head_b.element)
        head_b = head_b.next
    }

    num1 = Number(num1.join(''))
    num2 = Number(num2.join(''))
    let num = num1 + num2 + ''
    num = num.split('')

    let new_linked_list = new LinkedList()
    let head = new_linked_list.head

    num.forEach((i) => {
        let tmp = head
        head = new Node(Number(i))
        head.next = tmp
    })
    new_linked_list.head = head
    return new_linked_list
}

static mergeListK(...args) {
    // 9
    // 合并 k 个有序链表并保证有序，要求时间复杂度最优，不会就讨论，乱写没价值
    // args 是一个包含 k 个链表的数组

    if (args.length == 0) {
        return null
    }
    if (args.length == 1) {
        return args[0]
    }
    if (args.length == 2) {
        return args[0].mergeList(args[1])
    }
    let middle = Math.floor(args.length / 2)
    let left = args.slice(0, middle)
    let right = args.slice(middle)
    let l1 = LinkedList.mergeListK(...left)
    let l2 = LinkedList.mergeListK(...right)
    return l1.mergeList(l2)
}

reverseListK(k) {
    // 10
    // k 个一组反转链表(25)
    //     给一个链表, 以每 k 个为一组来翻转链表
    //     例子:
    //         Given this linked list: 1->2->3->4->5
    //
    //         k = 2, return: 2->1->4->3->5
    //
    //         k = 3, return: 3->2->1->4->5
    let head = this.head
    if (head == null) {
        return this
    }
    let new_node = new Node(-1)
    new_node.next = head
    let cur = head
    let pre = new_node
    let len = this.length()
    let num = 0
    while (len >= k) {
        while (num < k - 1) {
            let temp = cur.next
            cur.next = temp.next
            temp.next = pre.next
            pre.next = temp
            num++
        }

        num = 0
        pre = cur
        cur = cur.next
        len -= k
    }

    this.head = new_node.next
    return this
}

}

链表（栈和队列是链表的改良型）

队列（先进先出）

栈（先进后出）

哈希表（Hash table）

二叉树（Binary Tree）

js 快排与冒泡
虽然说算法很复杂，但是在我的工作经验中，掌握这2个基本就够处理大部分前端业务工作（不要跟我抬杠哦，你要面试肯定不够...
算法修炼
冒泡与快排(更新中)
排序
快排冒泡
【数据结构-排序】交换排序
冒泡排序略快排
排序算法
冒泡选择插入快排
冒泡快排堆排
冒泡排序原理：一遍循环与旁边的比较找到最大（最小）放到后面，多趟排序之后就成为一个有序的队列。冒泡循环中有嵌套...
快排，归并，冒泡
快排代码归并代码冒泡排序
冒泡、快排、归并
冒泡排序排序原理：设置i代表交换趟数，设置j代表交换元素，设置交换标志done 将初始趟数i=1，交换标志do...
各种排序算法代码
冒泡插入选择（基本没用）归并快排
《数据结构与算法之美》笔记—快速排序
快排相对快排，大家可能更熟悉冒泡排序，冒泡排序是比较相邻的两个元素。但是在数据量大的情况下，耗时却比快排多很多。...

js 快排与冒泡

快排

冒泡

链表（栈和队列是链表的改良型）

队列（先进先出）

栈（先进后出）

哈希表（Hash table）

二叉树（Binary Tree）

相关文章

js 快排与冒泡

算法修炼

排序

【数据结构-排序】交换排序

排序算法

冒泡快排堆排

快排，归并，冒泡

冒泡、快排、归并

各种排序算法代码

《数据结构与算法之美》笔记—快速排序

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

js 快排与冒泡

快排

冒泡

链表 （栈和队列是链表的改良型）

队列 （先进先出）

栈 （先进后出）

哈希表 （Hash table）

二叉树 （Binary Tree）

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

链表（栈和队列是链表的改良型）

队列（先进先出）

栈（先进后出）

哈希表（Hash table）

二叉树（Binary Tree）