D15. 排序算法

5.1 低效排序算法：冒泡、选择、插入排序

目标：理解O(n²)排序的原理及适用场景。

5.1.1 冒泡排序（Bubble Sort） 原理：通过相邻元素比较交换，逐步将较大元素“沉底”。

function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n-1; i++) {
        let swapped = false;
        for (let j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
                swapped = true;
            }
        }
        if (!swapped) break; // 提前终止
    }
    return arr;
}

特性：

• 时间复杂度：O(n²)（平均/最坏），O(n)（最好，已排序时）。
• 稳定性：稳定（相等元素不交换位置）。
• 适用场景：小规模数据或教育场景。

5.1.2 选择排序（Selection Sort） 原理：每轮选择最小元素，与未排序区首元素交换。

function selectionSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n-1; i++) {
        let minIdx = i;
        for (let j = i+1; j < n; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
    return arr;
}

特性：

• 时间复杂度：O(n²)（无论数据状态）。
• 稳定性：不稳定（相等元素可能交换位置）。
• 优点：交换次数最少（O(n)）。

5.1.3 插入排序（Insertion Sort） 原理：将元素逐个插入已排序子数组的正确位置。

function insertionSort(arr) {
    const n = arr.length;
    for (let i = 1; i < n; i++) {
        const 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;
}

特性：

• 时间复杂度：O(n²)（平均/最坏），O(n)（最好，已排序时）。
• 稳定性：稳定。
• 适用场景：部分有序数据（如扑克牌整理）。

5.2 快速排序（Quick Sort）：分治法的高效实现

目标：掌握快速排序的分区策略与递归实现。

5.2.1 递归实现

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) {
    const pivot = arr[right]; // 选择最后一个元素为枢轴
    let i = left; // 标记小于枢轴的边界
    for (let j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
        }
    }
    [arr[i], arr[right]] = [arr[right], arr[i]];
    return i;
}

关键点：

• 时间复杂度：O(n log n)（平均），O(n²)（最坏，如完全有序数组）。
• 优化策略：
  • 三数取中法：选择首、中、尾的中位数作为枢轴。
  • 随机选择枢轴：减少最坏情况概率。
• 不稳定性：可能交换相等元素（如[4, 5, 3, 5]可能变为[3,4,5,5]或[3,4,5,5]，但需确保逻辑正确）。

5.3 归并排序（Merge Sort）：稳定且高效

目标：通过分治实现稳定排序，解决快速排序的不稳定性。

5.3.1 递归实现

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

function merge(left, right) {
    const result = [];
    let i = 0, j = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) { // ≤ 保证稳定性
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    return result.concat(left.slice(i)).concat(right.slice(j));
}

特性：

• 时间复杂度：O(n log n)（始终稳定）。
• 空间复杂度：O(n)（因递归调用栈和辅助数组）。
• 稳定性：通过left[i] <= right[j]的条件实现。

5.4 桶排序（Bucket Sort）与基数排序（Radix Sort）：特殊场景优化

目标：针对整数或基数结构数据的线性时间排序。

5.4.1 桶排序 适用场景：数据均匀分布于区间（如浮点数或范围已知的整数）。

function bucketSort(arr, bucketSize=5) {
    if (arr.length === 0) return arr;
    const min = Math.min(...arr);
    const max = Math.max(...arr);
    const bucketCount = Math.floor((max - min) / bucketSize) + 1;
    const buckets = Array.from({length: bucketCount}, () => []);
    // 分配到桶中
    arr.forEach(num => {
        const idx = Math.floor((num - min) / bucketSize);
        buckets[idx].push(num);
    });
    // 合并排序后的桶（桶内使用插入排序）
    const sorted = [];
    for (const bucket of buckets) {
        insertionSort(bucket); // 桶内排序
        sorted.push(...bucket);
    }
    return sorted;
}

特性：

• 时间复杂度：O(n + k)（k为桶数，均匀分布时）。
• 局限性：依赖数据分布，需预知范围或调整桶大小。

5.4.2 基数排序 适用场景：整数或字符串的基数结构（如十进制数、IP地址）。

function radixSort(arr) {
    const maxDigit = getMaxDigit(arr); // 获取最大位数
    for (let digit = 1; digit <= maxDigit; digit++) {
        const buckets = Array.from({length: 10}, () => []);
        arr.forEach(num => {
            const bucketIdx = getDigit(num, digit);
            buckets[bucketIdx].push(num);
        });
        arr = [].concat(...buckets);
    }
    return arr;
}

function getMaxDigit(arr) {
    let max = 0;
    arr.forEach(num => {
        const digits = num.toString().length;
        if (digits > max) max = digits;
    });
    return max;
}

function getDigit(num, digit) {
    return Math.floor((num / Math.pow(10, digit-1)) % 10);
}

特性：

• 时间复杂度：O(d*(n+k))（d为最大位数，k为基数范围）。
• 稳定性：稳定（按低位到高位依次排序）。

知识回顾

1. O(n²)排序：适用于小规模数据或教学，插入排序在部分有序时表现最优。
2. 快速排序：分治法经典应用，平均效率高但最坏情况差，需优化枢轴选择。
3. 归并排序：稳定且时间复杂度恒定，但需额外空间。
4. 桶与基数排序：针对特殊数据的线性时间排序，需满足分布或基数结构条件。

课后练习

1. 选择题：以下哪种排序算法在最坏情况下时间复杂度仍为O(n log n)？

   • A. 快速排序
   • B. 归并排序
   • C. 插入排序

2. 代码题：实现快速排序的三数取中法选择枢轴。

3. 分析题：比较归并排序和快速排序的内存使用差异，并解释原因。

扩展阅读

• 快速排序优化：
  • 双轴快速排序：减少递归调用次数。
  • Hybrid排序：小规模数据时切换为插入排序。
• 基数排序变体：
  • LSB优先与MSB优先：不同位数处理方式影响稳定性。
• 实际应用：
  • 数据库索引排序：常使用归并排序的合并特性。
  • 图像处理：桶排序用于颜色直方图优化。