当前位置：首页 > article >正文

JS 常见的排序算法及比较

article 2024/9/20 9:36:12

在JavaScript中，排序是常见的操作之一，可以通过内置的.sort()方法实现，但了解各种排序算法的原理和优缺点对于处理大数据集或需要高效排序的场景至关重要。下面我将介绍几种常见的排序算法，包括它们的基本思想、示例代码以及优缺点。

1. 冒泡排序（Bubble Sort）

基本思想：通过重复遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换的元素为止。

示例代码：

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

优缺点：

优点：简单易懂。
缺点：效率低，时间复杂度为O(n^2)，不适合大数据集。

2. 选择排序（Selection Sort）

基本思想：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。

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

优缺点：

优点：实现简单。
缺点：时间复杂度为O(n^2)，效率不高。

3. 插入排序（Insertion Sort）

基本思想：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

示例代码：

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

优缺点：

优点：实现简单直观，对少量数据效率高。
缺点：在数据量大时效率较低，时间复杂度为O(n^2)。

4. 快速排序（Quick Sort）

基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

示例代码（简单实现，不包括递归基和分区优化）：

function quickSort(arr, left = 0, right = arr.length - 1) {  
    if (left < right) {  
        let pivotIndex = partition(arr, left, right);  
        quickSort(arr, left, pivotIndex - 1);  
        quickSort(arr, pivotIndex + 1, right);  
    }  
    return arr;  
}  
  
function partition(arr, left, right) {  
    let pivot = arr[right];  
    let i = left - 1;  
    for (let j = left; j < right; j++) {  
        if (arr[j] < pivot) {  
            i++;  
            [arr[i], arr[j]] = [arr[j], arr[i]];  
        }  
    }  
    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];  
    return i + 1;  
}

优缺点：

优点：平均情况下时间复杂度为O(n log n)，效率高。
缺点：最坏情况下时间复杂度为O(n^2)，如数组已经有序或接近有序。

5. 归并排序（Merge Sort）

基本思想：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

示例代码（简化版）：

function mergeSort(arr) {  
    if (arr.length < 2) {  
        return arr;  
    }  
    const middle = Math.floor(arr.length / 2);  
    const left = arr.slice(0, middle);  
    const right = arr.slice(middle);  
  
    return merge(mergeSort(left), mergeSort(right));  
}  
  
function merge(left, right) {  
    let result = [], indexLeft = 0, indexRight = 0;  
  
    while (indexLeft < left.length && indexRight < right.length) {  
        if (left[indexLeft] < right[indexRight]) {  
            result.push(left[indexLeft]);  
            indexLeft++;  
        } else {  
            result.push(right[indexRight]);  
            indexRight++;  
        }  
    }  
  
    return result.concat(left.slice(indexLeft)).concat(right.slice(indexRight));  
}

优缺点：