JavaScript 常用排序和搜索算法

发表于 2018-02-27 分类于前端笔记

对于一名软件工程师来说，数据结构和算法都是其需要掌握的核心知识。虽然业界对于前端工程师的算法能力要求比起其他方向的来说相对宽容，但是对于算法中最基本的排序算法和搜索算法还是需要掌握的。本文将以 JS 中最常见的数据结构：数组为主，介绍几种常见的排序算法和搜索算法，并通过 JS 实现。

排序算法

本文将介绍五种基本排序算法：冒泡排序、选择排序、插入排序、并归排序、快速排序。在学习过程中，可以参考日本程序员 norahiko 设计的排序算法动画演示，从而加深对各算法过程的理解。

冒泡排序

冒泡算法是所有排序算法中最简单的。然而，从运行时间的角度来说，它是最差的。

冒泡排序比较任何两个相邻的项，如果第一个比第二个大，则交换它们。元素项向上移动至正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。

function bubbleSort(array) {
    let len = array.length;
    
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                [array[j], array[j + 1]] = [array[j + 1], array[j]];
            }
        }
    }
}

平均时间复杂度：O(n²)

选择排序

选择排序是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。

function selectSort(array) {
    let len = array.len,
        indexMin;
    
    for (let i = 0; i < len; i++) {
        indexMin = i;
        
        for (let j = i; j < len; j++) {
            if (array[indexMin] > array[j]) {
                indexMin = j;
            }
        }
        
        if (i !== indexMin) {
            [array[i], array[indexMin]] = [array[indexMin], array[i]];
        }
    }
}

平均时间复杂度：O(n²)

插入排序

插入排序每次排一个数组项，以此方式构建最后的排序数组。

function insertionSort(array) {
    let len = array.length,
        j,
        temp;
    
    for (let i = 1; i < len; i++) {
        j = i;
        temp = array[i];
        while (j > 0 && array[j - 1] > temp) {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = temp;
    }
}

平均时间复杂度：O(n²)

并归排序

并归排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。

function mergeSort(array) {
    array = mergeSortRec(array);
    
    function mergeSortRec(array) {
        let len = array.length;
        
        if (len == 1) {
            return array;
        }
        
        let mid = Math.floor(len / 2),
            left = array.slice(0, mid),
            right = array.slice(mid, length);
        
        return merge(mergeSortRec(left), mergeSortRec(right));
    }
    
    function merge(left, right) {
        let result = [],
            il = 0,
            ir = 0;
        
        while (il < left.length && ir < right.length) {
            if (left[il] < right[ir]) {
                result.push(left[il++]);
            } else {
                result.push(right[ir++]);
            }
        }
        
        while (il < left.length) {
            result.push(left[il++]);
        }
        
        while (ir < right.length) {
            result.push(right[ir++]);
        }
        
        return result;
    }
}

平均时间复杂度：O(nlogⁿ)

快速排序

快速排序可以说是最常用的排序算法了。其排序过程只需要三步：

在数据集之中，选择一个元素作为“基准”（pivot）
所有小于“基准”的元素，都移到“基准”的左边；所有大于“基准”的元素，都移到“基准”的右边。
对“基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

function quickSort(array) {
    qucik(array, 0, array.length - 1);
}

function quick(array, left, right) {
    let index;
    
    if (array.length > 1) {
        index = partition(array, left, right);
        
        if (left < index - 1) {
            quick(array, left, index - 1);
        }
        
        if (index < right) {
            quick(array, index, right);
        }
    }
}

function partition(array, left, right) {
    let pivot = array[Math.floor((right + left) / 2)],
        i = left,
        j = right;
    
    while (i <= j) {
        while (array[i] < pivot) {
            i++;
        }
        while (array[j] > pivot) {
            j--;
        }
        if (i <= j) {
            [array[i], array[j]] = [array[j], array[i]];
            i++;
            j--;
        }
    }
    
    return i;
}

平均时间复杂度：O(nlogⁿ)

搜索算法

二分搜索

二分搜索算法要求被搜索的数据结构已排序。其设计的核心思路是：

选择数组的中间值
如果选中值是待搜索值，那么算法执行完毕
如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找
如果待搜索值比选中值要大，则返回步骤1并在选中值右边的子数组中寻找

代码实现如下：

// 默认数组已排序
function binarySearch(array, item) {
    let low = 0,
        high = array.length - 1,
        mid,
        element;
    
    while (low <= high) {
        mid = Math.floor((low + high) / 2);
        element = array[mid];
        
        if (element < item) {
            low = mid + 1;
        } else if (element > item) {
            hight = mid - 1;
        } else {
            return mid;
        }
    }
    
    // 未找到值时返回 -1
    return -1;
}

平均时间复杂度：O(log(n))

参考

《学习 JavaScript 数据结构和算法》