面试题：JavaScript 中如何优化数组排序算法

Question

在 JavaScript 里，有一个包含大量数字的数组，例如 `const largeArray = Array.from({ length: 10000 }, () => Math.floor(Math.random() * 10000));`，请使用合适的排序算法对其进行排序，并说明为什么选择该算法以及如何对其进行优化以提高性能。

Answer 1

排序算法选择

可以选择快速排序（Quick Sort）。

原因：快速排序平均情况下时间复杂度为 O(n log n)，在处理大数据集时表现良好。它采用分治思想，通过选择一个基准元素，将数组分为两部分，使得左边部分的元素小于基准元素，右边部分的元素大于基准元素，然后分别对左右两部分递归进行排序。对于随机分布的数组，快速排序通常能达到接近平均时间复杂度的性能。

优化方法

1. 随机化基准元素：为了避免在某些特殊情况下（如数组已经有序）快速排序退化为 O(n²) 的时间复杂度，可以随机选择基准元素，而不是固定选择第一个或最后一个元素。

function randomizedQuickSort(arr, left, right) {
    if (left >= right) {
        return;
    }
    let randomIndex = left + Math.floor(Math.random() * (right - left + 1));
    [arr[left], arr[randomIndex]] = [arr[randomIndex], arr[left]];
    let pivot = arr[left];
    let i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        arr[i] = arr[j];
        while (i < j && arr[i] < pivot) {
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = pivot;
    randomizedQuickSort(arr, left, i - 1);
    randomizedQuickSort(arr, i + 1, right);
}
function sortLargeArray(largeArray) {
    randomizedQuickSort(largeArray, 0, largeArray.length - 1);
    return largeArray;
}

2. 切换到插入排序：对于小数组，插入排序在局部有序的情况下性能较好，时间复杂度接近 O(n)。当子数组的长度小于某个阈值（如16）时，可以切换到插入排序。

function insertionSort(arr, left, right) {
    for (let i = left + 1; i <= right; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
function optimizedQuickSort(arr, left, right) {
    if (left >= right) {
        return;
    }
    if (right - left + 1 <= 16) {
        insertionSort(arr, left, right);
        return;
    }
    let randomIndex = left + Math.floor(Math.random() * (right - left + 1));
    [arr[left], arr[randomIndex]] = [arr[randomIndex], arr[left]];
    let pivot = arr[left];
    let i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        arr[i] = arr[j];
        while (i < j && arr[i] < pivot) {
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = pivot;
    optimizedQuickSort(arr, left, i - 1);
    optimizedQuickSort(arr, i + 1, right);
}
function sortLargeArrayOptimized(largeArray) {
    optimizedQuickSort(largeArray, 0, largeArray.length - 1);
    return largeArray;
}

示例代码调用

const largeArray = Array.from({ length: 10000 }, () => Math.floor(Math.random() * 10000));
const sortedArray = sortLargeArrayOptimized(largeArray);
console.log(sortedArray);

这样通过随机化基准元素和结合插入排序的优化策略，可以提高快速排序在处理大数据集时的性能。