排序与搜索

排序：

• 对于排序这一节我们我们需要掌握五种最基本的排序方法以及其时间空间复杂度

冒泡排序：

排序思路：

• 我们需要遍历我们的数组，将第一个元素与其后面的元素进行比较，如果前面的元素大于后面的元素那么我们交换两两者的位置
• 因为我们是让当前元素与其后面的元素进行比较，那么判断的截止应该在length-1
• 我们需要让每一个位置的元素进行上述操作，等到达最后一个元素其自然而然的为最小的元素不需要判断，所以循环的次数为length-1
• 由于在循环判断中最大的元素在前几次循环中已经放到了最后面，所以我们最终的每次循环判断只需要到length-1-i

时间空间复杂度：

• 因为我们需要对每一个位置进行循环判断来遍历数组，所以时间复杂度为O(n)

代码：

Array.prototype.bubbleSort = function () {
    for (let i = 0; i < this.length - 1; i++) {
        for (let j = 0; j < this.length - 1 - i; j++) {
            if (this[j] > this[j + 1]) {
                let tmp = this[j];
                this[j] = this[j + 1];
                this[j + 1] = tmp;
            }
        }
    }
}
const arr = [5, 4, 3, 2, 1];
arr.bubbleSort();
console.log(arr);

选择排序：

排序思路：

• 循环遍历数组，找到最小元素的索引，将第0位元素与其交换。
• 重复以上操作，与第1位元素交换
• 最后一位不用判断，默认为最大的元素

时间空间复杂度：

• 因为我们需要对每一个位置进行循环判断来遍历数组，所以时间复杂度为O(n)

代码：

Array.prototype.selectionSort = function () {
    for (let i = 0; i < this.length - 1; i++) {
        let minIndex = i;
        for (let j = i; j < this.length; j++) {
            if (this[j] < this[minIndex]) {
                minIndex = j;
            }
        }
        if (i !== minIndex) {
            let tmp = this[minIndex];
            this[minIndex] = this[i];
            this[i] = tmp;
        }
    }
}

插入排序：

排序思路：

• 从第一位开始，挨个和后面的元素比较如果比他大则往后移，直到找到比他小的元素，插入其之后
• 重复以上操作直到最后一个元素

时间空间复杂度：

• 因为我们需要对每一个位置进行循环判断来遍历数组，所以时间复杂度为O(n)

代码：

Array.prototype.insertionSort = function () {
    for (let i = 1; i < this.length; i++) {
        // 往后挪之后this[i]会被修改，所以我们需要用一个临时变量来存储
        let temp = this[i];
        let tempIndex = i;
        while (tempIndex > 0) {
            if (temp < this[tempIndex - 1]) { // 注意这里是和tempIndex - 1进行比较
                this[tempIndex] = this[tempIndex - 1]
            } else {
                break;
            }
            tempIndex--;
        }
        this[tempIndex] = temp;
    }
}
const arr = [3, 5, 4, 2, 1];
arr.insertionSort();
console.log(arr);

归并排序：

排序思路：

• 使用递归不断的将数组划分，直到划分为只有一个元素
• 通过while循环将数组进行合并

时间空间复杂度：

• 分的时间复杂度为O(log(n))和的时间复杂度为O(n)，所以最终的时间复杂度为O(nlogn)

代码：

rray.prototype.mergeSort = function () {
    const rec = (arr) => {
        if (arr.length === 1) return arr;
        const mid = Math.floor(arr.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] ? orderRight.shift() : orderLeft.shift());
            } else if (orderLeft.length) {
                res.push(orderLeft.shift());
            } else if (orderRight.length) {
                res.push(orderRight.shift());
            }
        }
        return res;
    }
    rec(this).forEach((v, i) => {
        this[i] = v;
    });
}

快速排序：

排序思路：

• 选择一个元素作为标记，创建两个数组，比他小的放在一个数组，比其大的放在一个数组
• 直到划分为数组中只有一个元素，或者为空

时间空间复杂度：

• 递归合并的时间复杂度为logn，将数组遍历分区的时间复杂度为n，所以最终的时间复杂度为O(nlogn)
• 注意：对于js的sort方法，在数据量小于等于9的时候采用插入排序，大于9以后采用快速排序

代码：

Array.prototype.quickSort = function () {
    const rec = (arr) => {
        if (arr.length <= 1) return arr;
        let mid = arr.shift();
        let left = [];
        let right = [];
        for (let i = 0; i < arr.length; i++) {
            if (arr[i] > mid) {
                right.push(arr[i])
            } else {
                left.push(arr[i])
            }
        }
        return [...rec(left), mid, ...rec(right)];
    }
    rec(this).forEach((v,i) => {
        this[i] = v;
    });
}

搜索：

• 主要说两种，一种是顺序搜索，一种是二分搜索，注意二分搜索只能用于有序数组

顺序搜索：

• 就是遍历整个数组，时间复杂度为O(n)

  Array.prototype.sequentialSearch = function (item) {
    for (let i = 0; i < this.length; i++){
        if (this[i] === item) {
            return i;
        }
    }
    return -1;
  }
  

二分搜索：

• 二分搜索在题目中的应用还是比较多的，要重点掌握
• 其时间复杂度为O(logn)

思路：

• 我们创建两个指针，一个指向第一个元素，一个指向最后一个元素
• 通过这两个指针找到中间的元素，用中间的元素与目标元素进行比较

代码：

Array.prototype.binarySearch = function (item) {
    let left = 0;
    let right = this.length - 1;
    while (left <= right) { // 注意这里必须要有等于才可以达到找到的目的
        let mid = (left + right) >> 1;
        if (item > this[mid]) {
            left = mid + 1;
        } else if(item < this[mid]){
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

总结：

• 对于冒泡排序，选择排序，插入排序这三种排序的时间复杂度均为O(n)，插入排序在数据较少的时候比较好用
• 归并排序，与快速排序的时间复杂度为O(nlogn)，对于归并排序其递归分的时间复杂度为O(logn)，和的时间复杂度为O(n)，对于快速排序我们将数组分为左右两数组的时间复杂度为O(n)，递归合并的时间复杂度为O(logn)

几个排序的基本结构：

• 冒泡排序是两个for循环，第一个循环的判断条件是length - 1，第二个for循环的判断条件为length - 1 - i
• 选择排序也是两个for循环，第一个判断条件为length - 1，注意要创建minIndex临时变量
• 插入排序是一个for循环，一个while循环，for循环从1开始，创建一个temp，一个tempIndex
• 对于归并排序我们首先找到中间元素，对于快速排序我们创建左右两个数组，找到基准
• 对于二分搜索我们我们创建左右两个指针