数据结构与算法

[george-wq]

介绍一下快排原理以及时间复杂度，并实现一个快排

快排使用了分治策略的思想，所谓分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。

快排的过程简单的说只有三步：

首先从序列中选取一个数作为基准数
将比这个数大的数全部放到它的右边，把小于或者等于它的数全部放到它的左边 （一次快排 partition）
然后分别对基准的左右两边重复以上的操作，直到数组完全排序
具体按以下步骤实现：

1，创建两个指针分别指向数组的最左端以及最右端
2，在数组中任意取出一个元素作为基准
3，左指针开始向右移动，遇到比基准大的停止
4，右指针开始向左移动，遇到比基准小的元素停止，交换左右指针所指向的元素
5，重复3，4，直到左指针超过右指针，此时，比基准小的值就都会放在基准的左边，比基准大的值会出现在基准的右边
6，然后分别对基准的左右两边重复以上的操作，直到数组完全排序

let quickSort = (arr) => {
  quick(arr, 0 , arr.length - 1)
}

let quick = (arr, left, right) => {
  let index
  if(left < right) {
    // 划分数组
    index = partition(arr, left, right)
    if(left < index - 1) {
      quick(arr, left, index - 1)
    }
    if(index < right) {
      quick(arr, index, right)
    }
  }
}

// 一次快排
let partition = (arr, left, right) => {
  // 取中间项为基准
  var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
      i = left,
      j = right
  // 开始调整
  while(i <= j) {
    
    // 左指针右移
    while(arr[i] < datum) {
      i++
    }
    
    // 右指针左移
    while(arr[j] > datum) {
      j--
    }
    
    // 交换
    if(i <= j) {
      swap(arr, i, j)
      i += 1
      j -= 1
    }
  }
  return i
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

// 测试
let arr = [1, 3, 2, 5, 4]
quickSort(arr)
console.log(arr) // [1, 2, 3, 4, 5]
// 第 2 个最大值
console.log(arr[arr.length - 2])  // 4

快排是从小到大排序，所以第 k 个最大值在 n-k 位置上

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(nlogn)

参考: sisterAn/JavaScript-Algorithms#70

洗牌算法

let Solution = function(nums) {
    this.nums = nums
};

Solution.prototype.reset = function() {
    return this.nums
};

Solution.prototype.shuffle = function() {
    let res = [...this.nums]
    let n = res.length
    for(let i = n-1; i >= 0; i--) {
        // Math.floor(Math.random() * (max - min + 1) + 1) => Math.floor(Math.random() * (i - 0 + 1) + 0)
        let randIndex = Math.floor(Math.random() * (i + 1))
        swap(res, randIndex, i)
    }
    return res
};

let swap = function(arr, i, j) {
    const temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

复杂度分析：

• 时间复杂度： O(n)
• 空间复杂度：O(n)，需要实现 reset 功能，原始数组必须得保存一份

参考: sisterAn/JavaScript-Algorithms#70

插入排序

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

function insertionSort(arr) {
    let n = arr.length;
    let preIndex, current;
    for (let i = 1; i < n; 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(n^2^)
• 空间复杂度：O(1)

参考: sisterAn/JavaScript-Algorithms#75

希尔排序

希尔排序又叫缩小增量排序，就是把数列进行分组(组内不停使用插入排序)，直至从宏观上看起来有序，最后插入排序起来就容易了(无须多次移位或交换)。

其中组的数量称为 增量 ，显然的是，增量是不断递减的(直到增量为1)

function shellSort(arr) {
    let n = arr.length;
    for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (let i = gap; i < n; i++) {
            let j = i;
            let current = arr[i];
            while (j - gap >= 0 && current < arr[j - gap]) {
                 arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}

复杂度分析：

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)

参考: sisterAn/JavaScript-Algorithms#75

归并排序

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

归并排序采用了分治策略，将数组分成2个较小的数组，然后每个数组再分成两个更小的数组，直至每个数组里只包含一个元素，然后将小数组不断的合并成较大的数组，直至只剩下一个数组，就是排序完成后的数组序列。

第一步：分割

• 使用快慢指针（双指针法），获取链表的中间节点
• 根据中间节点，分割成两个小链表
• 递归执行上一步，直到小链表中只有一个节点

第二步：归并（合并有序链表）

let sortList = function(head) {
    return mergeSortRec(head)
}

// 归并排序
// 若分裂后的两个链表长度不为 1，则继续分裂
// 直到分裂后的链表长度都为 1，
// 然后合并小链表
let mergeSortRec = function (head) {
    if(!head || !head.next) {
        return head
    }
    // 获取中间节点
    let middle = middleNode(head)
    // 分裂成两个链表
    let temp = middle.next
    middle.next = null
    let left = head, right = temp
    // 继续分裂（递归分裂）
    left = mergeSortRec(left)
    right = mergeSortRec(right)
    // 合并两个有序链表
    return mergeTwoLists(left, right)
}

// 获取中间节点
// - 如果链表长度为奇数，则返回中间节点
// - 如果链表长度为偶数，则有两个中间节点，这里返回第一个
let middleNode = function(head) {
    let fast = head, slow = head
    while(fast && fast.next && fast.next.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
}

// 合并两个有序链表
let mergeTwoLists = function(l1, l2) {
    let preHead = new ListNode(-1);
    let cur = preHead;
    while(l1 && l2){
        if(l1.val < l2.val){
            cur.next = l1;
            l1 = l1.next;
        }else{
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    cur.next = l1 || l2;
    return preHead.next;
}

引入递归算法的复杂度分析:

• 递归算法的时间复杂度：递归的总次数 * 每次递归的数量
• 递归算法的空间复杂度：递归的深度 * 每次递归创建变量的个数

复杂度分析

• 时间复杂度：递归的总次数为 T(logn) ，每次递归的数量为 T(n) ，时间复杂度为 O(nlogn)
• 空间复杂度：递归的深度为 T(logn) ，每次递归创建变量的个数为 T(c) （c为常数），空间复杂度为 O(logn)

参考: sisterAn/JavaScript-Algorithms#79

二分查找算法与时间复杂度

二分查找也称折半查找算法，它是一种简单易懂的快速查找算法。例如我随机写0-100之间的一个数字，让你猜我写的是什么？你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为止。

function binarySearch(items, item) {
    var low = 0,
        high = items.length - 1,
        mid, elem
    while(low <= high) {
        mid = Math.floor((low+high)/2)
        elem = items[mid]
        if(elem < item) {
            low = mid + 1
        } else if(elem > item) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

// 测试
var arr = [2,3,1,4]
// 快排
quickSort(arr)

binarySearch(arr, 3)
// 2

binarySearch(arr, 5)
// -1

测试成功

二分查找易错点:

• 循环退出条件是low <= high ，注意是 <=
• mid 的取值是 Math.floor((low+high)/2)
• low high 每次更新的时候，low = mid + 1 high = mid - 1

二分查找局限性:

• 针对的对象是数组结构，因为是通过下标来随机访问元素
• 数组必须有序
• 数组太小不合适，直接使用顺序查找即可
• 数组太长不合适，数组要求连续的内存空间，数组太长不利于存储

时间复杂度： O(logn)
空间复杂度：O(1)