关于leetcode:用javascript分类刷leetcode14排序算法图文视频讲解

常见排序算法复杂度

n^2 除 nlogn 在不同数据规模下的后果

常见排序算法

算法可视化起源：http://visualgo.net/

冒泡排序：工夫复杂度 O(n^2)

• 比拟相邻元素，如果第一个比第二个大，则替换他们
• 一轮下来，能够保障最初一个数是最大的
• 执行 n - 1 轮，就能够实现排序

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {for (var j = 0; j < len - 1 - i; j++) {if (arr[j] > arr[j+1]) {        // 相邻元素两两比照
                var temp = arr[j+1];        // 元素替换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

抉择排序：工夫复杂度 O(n^2)

• 找到数组中的最小值，将它放在第一位
• 接着找到第二小的值，将它放在第二位
• 顺次类推，执行 n - 1 轮

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保留
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

插入排序：工夫复杂度 O(n^2)

• 从第二个数开始往前比
• 比它大就往后排
• 以此类推直到最初一个数

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

归并排序：工夫复杂度 O(nlogn)，分的工夫复杂度O(logn)，合并的过程的复杂度是O(n)

• 分：把数组分成两半，递归子数组, 进行宰割操作，直到分成一个数
• 合：把两个字数组合并成一个有序数组，直到全副子数组合并结束，合并前先筹备一个空数组，寄存合并之后的后果，而后一直取出两个子数组的第一个元素，比拟他们的大小，小的先进入之前筹备的空数组中，而后持续遍历其余元素，直到子数组中的元素都实现遍历

function mergeSort(arr) {  // 采纳自上而下的递归办法
    var len = arr.length;
    if(len < 2) {return arr;}
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{var result = [];

    while (left.length && right.length) {if (left[0] <= right[0]) {result.push(left.shift());
        } else {result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

疾速排序：工夫复杂度 O(nlogn)，递归复杂度是O(logn), 分区复杂度O(n)

• 分区：从数组当选一个基准值，比基准值小的放在它的后面，比基准值大的放在它的前面
• 递归：递归对基准值前后的子数组进行第一步的操作

function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;

    if (left < right) {partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}

function partition(arr, left ,right) {     // 分区操作
      // 设定基准值地位（pivot）当然也能够抉择最左边的元素为基准 也能够随机抉择而后和最左或最右元素替换
    var pivot = left,                      
        index = pivot + 1;
    for (var i = index; i <= right; i++) {if (arr[i] < arr[pivot]) {swap(arr, i, index);
            index++;
        }        
    }
    swap(arr, pivot, index - 1);
    return index-1;
}

function swap(arr, i, j) {var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

148. 排序链表（medium）

给你链表的头结点 head，请将其按 升序 排列并返回 排序后的链表。

示例 1：

输出：head = [4,2,1,3]
输入：[1,2,3,4]
示例 2：

输出：head = [-1,5,3,4,0]
输入：[-1,0,3,4,5]
示例 3：

输出：head = []
输入：[]

提醒：

链表中节点的数目在范畴 [0, 5 * 104] 内
-105 <= Node.val <= 105

动画过大，点击查看

办法 1: 自顶向下

• 思路：用归并排序的思路，先一直宰割，晓得每个子区间只有一个节点地位，而后开始合并。
• 复杂度：工夫复杂度O(nlogn)，和归并排序的复杂度一样。空间复杂度O(logn)，递归的栈空间

js:

const merge = (head1, head2) => {const dummyHead = new ListNode(0);
    let temp = dummyHead, temp1 = head1, temp2 = head2;
    while (temp1 !== null && temp2 !== null) {// 合并子区间 小的节点先连
        if (temp1.val <= temp2.val) {
            temp.next = temp1;
            temp1 = temp1.next;
        } else {
            temp.next = temp2;
            temp2 = temp2.next;
        }
        temp = temp.next;
    }
    if (temp1 !== null) {// 两条链表还有节点没合并完，间接合并过去
        temp.next = temp1;
    } else if (temp2 !== null) {temp.next = temp2;}
    return dummyHead.next;
}

const toSortList = (head, tail) => {if (head === null) {// 极其状况
        return head;
    }
    if (head.next === tail) {// 宰割到只剩一个节点
        head.next = null;
        return head;
    }
    let slow = head, fast = head;
    while (fast !== tail) {// 的到两头节点
        slow = slow.next;
        fast = fast.next;
        if (fast !== tail) {fast = fast.next;}
    }
    const mid = slow;
    return merge(toSortList(head, mid), toSortList(mid, tail));// 宰割区间 递归合并
}

var sortList = function(head) {return toSortList(head, null);
};

办法 2: 自底向上

• 思路：间接进行循环合并操作。
• 复杂度：工夫复杂度O(nlogn)，空间复杂度O(1)

js:

const merge = (head1, head2) => {const dummyHead = new ListNode(0);
    let temp = dummyHead, temp1 = head1, temp2 = head2;
    while (temp1 !== null && temp2 !== null) {if (temp1.val <= temp2.val) {
            temp.next = temp1;
            temp1 = temp1.next;
        } else {
            temp.next = temp2;
            temp2 = temp2.next;
        }
        temp = temp.next;
    }
    if (temp1 !== null) {temp.next = temp1;} else if (temp2 !== null) {temp.next = temp2;}
    return dummyHead.next;
}

var sortList = function(head) {if (head === null) {return head;}
    let length = 0;
    let node = head;
    while (node !== null) {
        length++;
        node = node.next;
    }
    const dummyHead = new ListNode(0, head);
    for (let subLength = 1; subLength < length; subLength <<= 1) {
        let prev = dummyHead, curr = dummyHead.next;
        while (curr !== null) {
            let head1 = curr;
            for (let i = 1; i < subLength && curr.next !== null; i++) {curr = curr.next;}
            let head2 = curr.next;
            curr.next = null;
            curr = head2;
            for (let i = 1; i < subLength && curr != null && curr.next !== null; i++) {curr = curr.next;}
            let next = null;
            if (curr !== null) {
                next = curr.next;
                curr.next = null;
            }
            const merged = merge(head1, head2);
            prev.next = merged;
            while (prev.next !== null) {prev = prev.next;}
            curr = next;
        }
    }
    return dummyHead.next;
};

215. 数组中的第 K 个最大元素（medium）

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请留神，你须要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现工夫复杂度为 O(n) 的算法解决此问题。

示例 1:

输出: [3,2,1,5,6,4], k = 2
输入: 5
示例 2:

输出: [3,2,3,1,2,4,5,5,6], k = 4
输入: 4

提醒：

1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104

办法 1. 保护大小为 k 的小顶堆，当堆的元素个数小于等于 k 时，遍历数组，让数组的元素一直退出堆，当堆的大小大于 k 时，让堆顶元素出列，遍历完数组之后，小顶堆堆顶的元素就是第 k 大元素。

复杂度：工夫复杂度O(nlogk)，循环 n 次，每次堆的操作是O(logk)。空间复杂度O(k)，

js:

class Heap {constructor(comparator = (a, b) => a - b, data = []) {
        this.data = data;
        this.comparator = comparator;// 比拟器
        this.heapify();// 堆化}

    heapify() {if (this.size() < 2) return;
        for (let i = Math.floor(this.size() / 2) - 1; i >= 0; i--) {this.bubbleDown(i);//bubbleDown 操作
        }
    }

    peek() {if (this.size() === 0) return null;
        return this.data[0];// 查看堆顶
    }

    offer(value) {this.data.push(value);// 退出数组
        this.bubbleUp(this.size() - 1);// 调整退出的元素在小顶堆中的地位
    }

    poll() {if (this.size() === 0) {return null;}
        const result = this.data[0];
        const last = this.data.pop();
        if (this.size() !== 0) {this.data[0] = last;// 替换第一个元素和最初一个元素
            this.bubbleDown(0);//bubbleDown 操作
        }
        return result;
    }

    bubbleUp(index) {while (index > 0) {const parentIndex = (index - 1) >> 1;// 父节点的地位
            // 如果以后元素比父节点的元素小，就替换以后节点和父节点的地位
            if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {this.swap(index, parentIndex);// 替换本人和父节点的地位
                index = parentIndex;// 一直向上取父节点进行比拟
            } else {break;// 如果以后元素比父节点的元素大，不须要解决}
        }
    }

    bubbleDown(index) {const lastIndex = this.size() - 1;// 最初一个节点的地位
        while (true) {
            const leftIndex = index * 2 + 1;// 左节点的地位
            const rightIndex = index * 2 + 2;// 右节点的地位
            let findIndex = index;//bubbleDown 节点的地位
            // 找出左右节点中 value 小的节点
            if (
                leftIndex <= lastIndex &&
                this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
            ) {findIndex = leftIndex;}
            if (
                rightIndex <= lastIndex &&
                this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
            ) {findIndex = rightIndex;}
            if (index !== findIndex) {this.swap(index, findIndex);// 替换以后元素和左右节点中 value 小的
                index = findIndex;
            } else {break;}
        }
    }

    swap(index1, index2) {// 替换堆中两个元素的地位
        [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
    }

    size() {return this.data.length;}
}



var findKthLargest = function (nums, k) {const h = new Heap((a, b) => a - b);

    for (const num of nums) {h.offer(num);// 退出堆
        if (h.size() > k) {// 堆的 size 超过 k 时，出堆
            h.poll();}
    }

    return h.peek();};

办法 2: 堆排序

• 思路：利用原地堆排序的思维，将前 k - 1 大的元素退出队尾，最初队顶的元素就是第 k 大的元素
• 复杂度：工夫复杂度O(nlogn)，堆的创立复杂度是O(n)，挪动前 k - 1 大的元素而后堆化复杂度是O(klogn)，k<=n，最差的状况下是O(nlogn)，空间复杂度O(logn)，递归的栈空间

js:

var findKthLargest = function (nums, k) {
    let heapSize = nums.length;
    buildMaxHeap(nums, heapSize); // 构建大顶堆 大小为 heapSize
    // 大顶堆 前 k - 1 个堆顶元素一直和数组的开端元素替换 而后从新 heapify 堆顶元素
    // 这个操作就是之前小顶堆出堆顶的操作，只不过当初是原地排序
    for (let i = nums.length - 1; i >= nums.length - k + 1; i--) {swap(nums, 0, i);// 替换堆顶和数组开端元素
        --heapSize; // 堆大小减 1
        maxHeapify(nums, 0, heapSize);// 从新 heapify
    }
    return nums[0];// 返回堆顶元素，就是第 k 大的元素

    function buildMaxHeap(nums, heapSize) {for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {// 从第一个非叶子节点开始构建
            maxHeapify(nums, i, heapSize);
        }
    }
    // 从左向右，自上而下的调整节点
    function maxHeapify(nums, i, heapSize) {
        let l = i * 2 + 1;// 左节点
        let r = i * 2 + 2;// 右节点
        let largest = i;
        if (l < heapSize && nums[l] > nums[largest]) {largest = l;}
        if (r < heapSize && nums[r] > nums[largest]) {largest = r;}
        if (largest !== i) {swap(nums, i, largest); // 找到左右节点中大的元素替换
            // 递归替换前面的节点
            maxHeapify(nums, largest, heapSize);
        }
    }

    function swap(a, i, j) {// 替换函数
        let temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
};

办法 3: 疾速排序的分区办法

• 思路：借鉴快排的思路，一直随机抉择基准元素，看进行 partition 之后，该元素是不是在 n-k 的地位。

• 复杂度：

  1. 工夫复杂度O(nlogn)
  2. 空间复杂度O(logn)，递归的深度

js：

const findKthLargest = (nums, k) => {
    const n = nums.length;

    const quick = (l, r) => {if (l > r) return;// 递归终止条件
        let random = Math.floor(Math.random() * (r - l + 1)) + l; // 随机选取一个索引
        swap(nums, random, r); // 将它和地位 r 的元素替换，让 nums[r]作为基准元素

        // 对基准元素进行 partition
        let pivotIndex = partition(nums, l, r);
        // 进行 partition 之后，基准元素右边的元素都小于它 左边的元素都大于它
        // 如果 partition 之后，这个基准元素的地位 pivotIndex 正好是 n -k 则找大了第 k 大的数
        // 如果 n -k<pivotIndex, 则在 pivotIndex 的右边递归查找
        // 如果 n -k>pivotIndex，则在 pivotIndex 的左边递归查找
        if (n - k < pivotIndex) {quick(l, pivotIndex - 1);
        } else {quick(pivotIndex + 1, r);
        }
    };

    quick(0, n - 1);// 函数开始传入的 left=0，right= n - 1
    return nums[n - k]; // 最初找到了正确的地位 也就是 n - k 等于 pivotIndex 这个地位的元素就是第 k 大的数
};

function partition(nums, left, right) {let pivot = nums[right];                 // 最左边的元素为基准
    let pivotIndex = left;                   //pivotIndex 初始化为 left
    for (let i = left; i < right; i++) {     // 遍历 left 到 right- 1 的元素
        if (nums[i] < pivot) {                 // 如果以后元素比基准元素小
            swap(nums, i, pivotIndex);           // 把它替换到 pivotIndex 的地位
            pivotIndex++;                        //pivotIndex 往前挪动一步
        }
    }
    swap(nums, right, pivotIndex);           // 最初替换 pivotIndex 和 right
    return pivotIndex;                       // 返回 pivotIndex
}

function swap(nums, p, q) {// 替换数组中的两个元素
    const temp = nums[p];
    nums[p] = nums[q];
    nums[q] = temp;
}

视频解说：传送门