算法 - 搜索排序

算法 - 搜索排序

Introduction
工作中常用的排序及搜索算法
Category
Algorithm
CreateTime
Dec 17, 2021
在工作中,排序搜索是每天都会用到的。我们经常会直接使用数组、字符串自带的 API 进行使用,这没有什么问题,但是还要知其所以然。
下面会介绍一些常见或常用的排序算法

排序

冒泡排序

  1. 比较所有的相邻元素,如果第一个比第二个大,则交换他们
  1. 一轮下来,可以保证最后一个数是最大的数
const bubbleSort = (array) => {
    for (let i = 0; i < array.length - 1; i++) {
        for (let j = i + 1; j < array.length; j++) {
            // 从小到大排序
            if (array[i] > array[j]) {
                let temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
    return array;
};
const array = [0, -1, 10, 20, 4, 7]
console.log('result', bubbleSort(array)) // [ -1, 0, 4, 7, 10, 20 ]

选择排序

  1. 找到数组中的最小值,选中它并放置在第一位
  1. 接着找到第二小的值,选中它并放在第二位
  1. 以此类推,执行 n - 1
const selectionSort = (array) => {
    for (let i = 0; i < array.length - 1; i++) {
        let minIndex = i;
        for (let j = i; j < array.length; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        const temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
    return array;
};

const array = [-1, -2, 10, 4, 2, -9];
console.log('result', selectionSort(array)); // [ -9, -2, -1, 2, 4, 10 ]

插入排序

  1. 从第二个数开始往前比
  1. 比它大就往后排
  1. 以此类推进行到最后一个数
const insertionSort = (array) => {
    for (let i = 1; i < array.length; i++) {
        let temp = array[i];
        let j = i;
        while (j > 0) {
            if (array[j - 1] > temp) {
                array[j] = array[j - 1]
            } else {
                break;
            }
            j--;
        }
        array[j] = temp;
    }
    return array;
}

const array = [-1, -2, 10, 4, 2, -9];
console.log('result', insertionSort(array)); // [ -9, -2, -1, 2, 4, 10 ]

归并排序

  1. 分:把数组劈成两半,再递归地对子数组进行 ”分“ 操作,直到分成一个个单独的数
  1. 合:把两个数合并为有序数组,再对有序数组进行合并,直到全部子数组合并为一个完整数组
const mergeSort = (array) => {
    if (array.length === 1) {
        return array;
    }
    const mid = Math.floor(array.length / 2);
    const left = array.slice(0, mid)
    const right = array.slice(mid, array.length);
    const orderLeft = mergeSort(left);
    const orderRight = mergeSort(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 {
            res.push(orderRight.shift())
        }
    }
    return res;
}

搜索

顺序搜索

  1. 遍历数组
  1. 找到跟目标值相等的元素,就返回它的下标

二分搜索

  1. 从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束
  1. 如果目标值大于或者小于中间元素,则在大于或者小于中间元素的那一半数组中再进行搜索
const binarySearch = (array, item) => {
    let low = 0;
    let high = array.length - 1;
    while (low <= high) {
        const mid = low + Math.floor((high - low) / 2)
        if (array[mid] < item) {
            low = mid + 1
        } else if (array[mid] > item) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1;
}

Loading Comments...