算法（一）搜索排序

1. 定义

排序：把某个乱序的数组编程升序或者降序的数组

搜索：找出数组中某个元素的下标

JS中的排序：数组的sort方法

JS中的搜索：数组的indexOf方法

排序算法：

冒泡排序
选择排序
插入排序
归并排序
快速排序
…

搜索算法：

顺序搜索
二分搜索
…

2. 排序算法

2-1 冒泡排序 bubbleSort

最简单的一种排序算法，但性能不太好

冒泡排序

比较所有相邻元素，如果第一个比第二个大，则交换他们
一轮下来，可以保证最后一个数是最大的
执行n-1论，就可以完成排序

// this指代的是array
Array.prototype.bubbleSort = function() {
    for (let i =0; i < this.length - 1; i++) {
        for (let j = 0; j < this.length - 1; j++) {
            if (this[j] > this[j + 1]) {
                const temp = this[j];
                this[j] = this[j+1];
                this[j+1] = temp;
            }
        }
    }
}
const arr = [5,4,3,2,1];
arr.bubbleSort()

两个嵌套循环

时间复杂度：O(n^2)

时间复杂度：
- 最好情况：O(n)
- 平均情况：O(n^2)
- 最坏情况：O(n^2)
稳定性：稳定
额外的空间：O(1)

原地排序，不需要额外空间

2-2 选择排序 selectionSort

选择排序 vs 冒泡排序：

选择排序是记录这一轮遍历数组里的最小/最大值，遍历完成后将这个最值放在起始位置，只需要一次交换

冒泡排序是两两之间进行交换，需要交换很多次

选择排序

找到数组中得知最小值，选中它并将其放置在第一位
接着找到第二小的值，选中它并将其放置在第二位
以此类推，执行n-1轮

Array.prototype.selectionSort = function() {
    for (let i = 0; i < this.length - 1; i++) {
       let indexMin = i;
        for (let j = i; j < this.length; j++) {
            if(this[j] < this[indexMin]) {
                indexMin = j;
            }
        }
        // 当自身是最小值时，不需要交换
        if (indexMin !== i) {
            const temp = this[i];
            this[i] = this[indexMin];
            this[indexMin] = temp; 
        }
    }
}
const arr = [5,4,3,2,1];
arr.selectionSort()

两个嵌套循环

时间复杂度：O(n^2)

时间复杂度：
- 最好情况：O(n^2)
- 平均情况：O(n^2)
- 最坏情况：O(n^2)
稳定性：不稳定
额外的空间：O(1)

2-3 插入排序 insertionSort

从第二数开始往前比
比它大就往后排
依次类推进行到最后一个数

Array.prototype.insertionSort = function() {
    for (let i = 1; i < this.length; i++) {
        const temp = this[i];
        let j = i;
        while(j) {
            if(this[j-1] > temp) {
                this[j] = this[j-1];
            } else {
                break;
            }
            j--;
        }
        this[j] = temp;
    }
}
const arr = [5,4,3,2,1];
arr.insertionSort()

两个嵌套循环

时间复杂度：O(n^2)

2-4 归并排序 mergeSort

比前面几个排序性能都要好，其中火狐浏览器的sort就是使用的归并排序

归并排序

分：把数组劈成两半，再递归地对子数组进行“分”操作，直到分成一个个单独的数
合：把两个数合并为有序数组，再对有序数组进行合并，直到全部子树组合并为一个完整数组
- 新建一个空数组res，用于存放最终排序后的数组
- 比较两个有序数组的头部，较小者出队并推入res中
- 如果两个数组还有值，就重复第二步

Array.prototype.mergeSort = function() {
    // 使用一个递归
    const rec = (arr) => {
        if (arr.length === 1) return arr;
        const mid = Math.floor(ar.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] ? orderLeft.shift() : orderRight.shift())
            } else if (orderLeft.length) {
                // 当只剩下左边有元素的话，将左边的元素依次推入
                res.push(orderLeft.shift())
            } else if (orderRight.length) {
                // 右边同理
                res.push(orderRight.shift())
            }
        }
        return res;
    }
    const res = rec(this);
    // 将res拷贝到arr数组里
    res.forEach(n, i) => {
        this[i] = res;
    }
}
const arr = [5,4,3,2,1];
arr.mergeSort()

分的时间复杂度是O(logN)

合的时间复杂度是O(n)

∴ 时间复杂度为 O(n * logN）

时间复杂度：
- 最好情况：O(nlogn)
- 平均情况：O(nlogn)
- 最坏情况：O(nlogn)
稳定性：稳定
额外的空间：O(n)

2-5 快速排序 quickSort

比前三种排序性能都要好

快速排序

分区：从数组中任意选择一个“基准”，所有比基准小的元素放在基准前面，比基准大的元素放在基准的后面
递归：递归地对基准前后的子数组进行分区

第一轮之后的效果：

Array.prototype.quickSort = function() {
    const rec = () => {
        if (arr.length === 1) return arr;
        const left = [];
        const right = [];
        const mid = arr[0];
        for (let i = 1; i < arr.length; i++) {
            if (arr[i] < mid) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        return [...rec[left], mid, ...rec(right)];
    }
    const res = rec(this);
    // 将res拷贝到arr数组里
    res.forEach(n, i) => {
        this[i] = res;
    }
}
const arr = [5,4,3,2,1];
arr.quickSort()

递归的时间复杂度是 O(logN)

分区操作的时间复杂度是 O(n)

∴ 时间复杂度为 O(n*logN)

时间复杂度：
- 最好情况：O(nlogn)
- 平均情况：O(nlogn)
- 最坏情况：O(n^2)
稳定性：不稳定
额外的空间：O(logn)~O(n)

递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度

3. 搜索算法

3-1 顺序算法 sequentialSearch

性能很差

遍历数组
找到跟目标值相等的元素，就返回其下标
遍历结束后，如果没有搜索到目标值，就返回-1

Arrary.prototype.sequentialSearch = function(item) {
    for (let i = 0; i < this.length; i++) {
        if (this[i] === item) {
            return i;
        }
    }
    return -1;
}
const res = [1, 2, 3, 4, 5].sequentialSearch(3)

遍历数组是一个循环操作

时间复杂度：O(n)

3-2 二分搜索 binarySearch

在==有序==排序的数组中搜索

从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束
如果目标值大于或小于中间元素，则在大于或小于中间元素的那一般数组中搜索
否则返回-1

// 默认arr已排序好
Arrary.prototype.binarySearch = function(item) {
    let low = 0;
    let hight = this.length - 1;
    while (low <= hight) {
        const mid = Math.floor((low + hight) / 2);
        const element = this[mid];
        if (element < item) {
            low = mid + 1;
        } else if (element > item) {
            hight = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}
const res = [1, 2, 3, 4, 5].binarySearch(3)

每一次比较都使搜索范围缩小一般

时间复杂度：O(logN)

4. LeetCode题

21. 合并两个有序链表

解题思路：

与归并排序中的合并有序数组很相似
将数组替换成链表

解题步骤：

新建一个新链表，作为返回结果
用指针遍历两个有序链表，并比较两个链表的当前节点，较小者先接入新链表，并将指针后移一步
链表遍历结束，返回新链表

var mergeTwoLists = function(list1, list2) {
    const res = new ListNode();
    let p = res;
    let p1 = list1;
    let p2 = list2;
    while (p1 && p2) {
        if (p1.val < p2.val) {
            p.next = p1;
            p1 = p1.next;
        } else {
            p.next = p2;
            p2 = p2.next;
        }
        p = p.next;
    }
    if (p1) {
        p.next = p1;
    }
    if (p2) {
        p.next = p2;
    }
    return res.next;
};

374. 猜数字大小

解题思路：

二分搜索
调用guess函数，来判断中间元素是否是目标值

解题步骤：

从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束
如果目标值大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找

var guessNumber = function (n) {
    let low = 1;
    let high = n;
    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const res = guess(mid);
        if (res === 0) {
            return mid;
        } else if (res === 1) {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
};

数据结构与算法

js LeetCode 算法排序算法搜索算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

随便写写上一篇

数据结构（九）堆下一篇