快速稳定排序算法在javascript中的实现

快速稳定排序算法在JavaScript中的实现主要依赖于一种称为“快速排序”（Quick Sort）的算法。快速排序是一种高效的排序算法，采用分治法策略来对一个序列进行排序。它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

基础概念

快速排序的核心是分区（partition）操作，它选择一个元素作为“基准”（pivot），然后将数组分为两部分：一部分包含所有小于基准的元素，另一部分包含所有大于或等于基准的元素。这个过程称为分区。然后递归地对这两部分进行快速排序。

优势

效率高：平均时间复杂度为O(n log n)，在大多数实际情况下都非常快。
原地排序：不需要额外的存储空间，只需要O(log n)的栈空间用于递归。
适用性广：适用于各种不同的输入数据，并且在实际应用中表现良好。

类型

快速排序有多种变体，包括：

Lomuto分区方案：简单直观，但在某些情况下性能较差。
Hoare分区方案：效率较高，是快速排序的首选分区方案。

应用场景

快速排序广泛应用于各种需要排序的场景，如数据库排序、数据分析、搜索引擎等。

JavaScript实现

以下是使用Hoare分区方案的快速排序算法的JavaScript实现：

function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left < right) {
        const pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
    return arr;
}

function partition(arr, left, right) {
    let i = left;
    let j = right;
    const pivot = arr[left];

    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        if (i < j) arr[i++] = arr[j];

        while (i < j && arr[i] <= pivot) i++;
        if (i < j) arr[j--] = arr[i];
    }

    arr[i] = pivot;
    return i;
}

// 示例
const arr = [3, 6, 8, 10, 1, 2, 1];
console.log(quickSort(arr)); // 输出: [1, 1, 2, 3, 6, 8, 10]