JavaScript中的稳定排序算法

在计算机科学中，排序算法是一种将数据集按照特定顺序排列的过程。在JavaScript中，实现高效且稳定的排序对于处理各种数据集是至关重要的。稳定性指的是在两个具有相同排序值的元素之间，原始顺序不会改变。本文将介绍几种在JavaScript中常用的稳定排序算法，并提供相应的代码示例。

1. 冒泡排序（Bubble Sort）

冒泡排序是一种简单的比较型排序算法，通过重复遍历要排序的列表，比较每对相邻元素并在必要时交换它们，直到没有更多的交换需要进行为止。

示例代码：

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

2. 插入排序（Insertion Sort）

插入排序是一种简单直观的排序算法，它通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。

示例代码：

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

3. 归并排序（Merge Sort）

归并排序是一种分治策略的排序算法，它将数组分成两半，递归地排序两边，然后合并结果。

示例代码：

function mergeSort(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);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    let result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] <= right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

4. 快速排序（Quick Sort）

快速排序是一种高效的排序算法，采用分治策略来将一个数组分为较小和较大的两个子数组，然后再递归地排序这两个子数组。

示例代码：

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    const pivot = arr[Math.floor(arr.length / 2)];
    const left = arr.filter(x => x < pivot);
    const middle = arr.filter(x => x === pivot);
    const right = arr.filter(x => x > pivot);

    return [...quickSort(left), ...middle, ...quickSort(right)];
}

结论

在JavaScript中选择合适的排序算法取决于具体的应用场景。例如，对于小规模的数据集或需要保持数据相对顺序的场景，冒泡排序或插入排序可能是更好的选择。而对于大规模数据集或性能要求较高的应用，归并排序或快速排序通常更优。理解不同算法的时间复杂度、空间复杂度以及稳定性特性，可以帮助开发者做出更合适的选择。