JS常见算法详解

前言

本文将给读者介绍JS中常见的算法，包括排序、查找等。算法是程序设计的基础，对于程序员来说，学好算法是非常重要的。相信通过学习本文，读者可以对算法有更加深入的理解。

排序算法

冒泡排序

冒泡排序算法采用交换方式，将待排序数组中相邻的两个数进行比较，较大的数后移一位，较小的数前移一位。经过一次遍历，最大的数就被交换到了最后。不断重复这个过程，直到所有数都排好序。

function bubbleSort(arr) {
    var len = arr.length;
    for(var i = 0; i < len - 1; i++) {
        for(var j = 0; j < len - 1 - i; j++) {
            if(arr[j] > arr[j + 1]) {  // 交换
                var temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

快速排序

快速排序算法采用分治法，将待排序数组分成两个子数组，将小于某个值的元素放到左边，将大于某个值的元素放到右边。然后对左右两个子数组递归执行同样的操作，最终形成有序数组。

function quickSort(arr) {
    if(arr.length <= 1) {  // 元素个数小于等于1，返回整个数组
        return arr;
    }
    var pivotIndex = Math.floor(arr.length / 2);  // 取中间元素作为基准值
    var pivot = arr.splice(pivotIndex, 1)[0];  // 将该元素从数组中移除，并取出该元素
    var left = [];
    var right = [];
    for(var i = 0; i < arr.length; i++) {
        if(arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([pivot], quickSort(right));  // 递归左右两个子数组，最终合并成有序数组
}

查找算法

二分查找

二分查找算法是针对有序列表的一种查找方式。原理是将待查找元素与列表中中间位置的元素进行比较，若相等，则返回该位置；若小于中间元素，就继续在左边查找；若大于中间元素，则继续在右边查找。重复此过程，直到查找到该元素，或者列表已遍历完毕。

function binarySearch(arr, value) {
    var low = 0;
    var high = arr.length - 1;
    while(low <= high) {
        var mid = Math.floor((low + high) / 2);
        if(arr[mid] == value) {
            return mid;  // 找到该元素，返回位置
        } else if(arr[mid] < value) {
            low = mid + 1;  // 在右边查找
        } else {
            high = mid - 1;  // 在左边查找
        }
    }
    return -1;  // 没有找到该元素
}

哈希查找

哈希查找算法是通过哈希表来实现查找的方式，原理是将待查找元素作为关键字，通过哈希函数计算出该元素在哈希表中的位置，然后进行查找。若该位置的元素与待查找元素相等，则返回该元素的值；若不相等，则根据哈希函数的定义找到下一个元素的位置，继续查找。如果遇到哈希表的某个位置的元素为null，则说明该元素不存在于哈希表中。

function hashSearch(arr, value) {
    var table = {};  // 哈希表
    for(var i = 0; i < arr.length; i++) {  // 将数组元素存入哈希表
        table[arr[i]] = arr[i];
    }
    var key = value % arr.length;  // 计算待查找元素的哈希值
    while(table[key]) {  // 若该位置不为空
        if(table[key] == value) {  // 找到该元素
            return key;
        } else {
            key = (key + 1) % arr.length;  // 继续查找下一个元素
        }
    }
    return -1;  // 没有找到该元素
}