C++ 插入排序与桶排序 - L33 算法基础

📚 排序算法概述

插入排序（Insertion Sort）

核心思想：将未排序的元素逐个插入到已排序部分的正确位置，就像打扑克牌时整理手牌一样。

// 插入排序可视化过程
// 原始数组：[5, 3, 8, 1, 2]
// [|5|, 3, 8, 1, 2] ← 第一个元素视为已排序

// 第1步：插入3
// [5, |3|, 8, 1, 2] → 3 < 5，将5右移
// [|3, 5|, 8, 1, 2] ← 3插入到正确位置

// 第2步：插入8
// [3, 5, |8|, 1, 2] → 8 > 5，不需要移动
// [|3, 5, 8|, 1, 2] ← 8已在正确位置

// 第3步：插入1
// [3, 5, 8, |1|, 2] → 1 < 8，将8右移
// [3, 5, |1|, 8, 2] → 1 < 5，将5右移
// [3, |1|, 5, 8, 2] → 1 < 3，将3右移
// [|1, 3, 5, 8|, 2] ← 1插入到最前面

// 第4步：插入2
// [1, 3, 5, 8, |2|] → 2 < 8，将8右移
// [1, 3, 5, |2|, 8] → 2 < 5，将5右移
// [1, 3, |2|, 5, 8] → 2 < 3，将3右移
// [1, |2|, 3, 5, 8] → 2 > 1，停止
// [|1, 2, 3, 5, 8|] ← 排序完成

桶排序（Bucket Sort）

核心思想：将数据分到有限数量的桶中，每个桶再分别排序（可以使用其他排序算法或递归使用桶排序），最后将各个桶中的数据合并。

// 桶排序可视化过程
// 原始数组：[0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]

// 第1步：创建10个桶（0-9）
// Bucket 0: []
// Bucket 1: [0.17, 0.12]
// Bucket 2: [0.26, 0.21, 0.23]
// Bucket 3: [0.39]
// Bucket 4: []
// Bucket 5: []
// Bucket 6: [0.68]
// Bucket 7: [0.78, 0.72]
// Bucket 8: []
// Bucket 9: [0.94]

// 第2步：对每个桶内部排序（使用插入排序）
// Bucket 1: [0.12, 0.17]
// Bucket 2: [0.21, 0.23, 0.26]
// Bucket 7: [0.72, 0.78]

// 第3步：按顺序合并所有桶
// [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

💡 桶排序的关键：
• 适用于均匀分布的数据
• 桶的数量影响性能
• 通常用于浮点数排序
• 时间复杂度可达O(n)（理想情况）

⚙️ 算法实现

插入排序完整实现

#include <iostream>
using namespace std;

// 插入排序函数
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {       // 从第二个元素开始
        int key = arr[i];                 // 当前要插入的元素
        int j = i - 1;                   // 已排序部分的最后一个索引
        
        // 将比key大的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];        // 元素后移
            j--;
        }
        
        arr[j + 1] = key;                // 插入到正确位置
    }
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "排序前：";
    printArray(arr, n);
    
    insertionSort(arr, n);
    
    cout << "排序后：";
    printArray(arr, n);
    
    return 0;
}

桶排序完整实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 桶排序函数
void bucketSort(float arr[], int n) {
    // 第1步：创建n个空桶
    vector<vector<float>> buckets(n);
    
    // 第2步：将元素放入对应的桶
    for (int i = 0; i < n; i++) {
        int bucketIndex = n * arr[i];  // 计算桶索引
        buckets[bucketIndex].push_back(arr[i]);
    }
    
    // 第3步：对每个桶进行排序（使用插入排序）
    for (int i = 0; i < n; i++) {
        sort(buckets[i].begin(), buckets[i].end());
    }
    
    // 第4步：合并所有桶
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (size_t j = 0; j < buckets[i].size(); j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

// 打印数组
void printArray(float arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    float arr[] = {0.78, 0.17, 0.39, 0.26, 0.72, 
                  0.94, 0.21, 0.12, 0.23, 0.68};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "排序前：";
    printArray(arr, n);
    
    bucketSort(arr, n);
    
    cout << "排序后：";
    printArray(arr, n);
    
    return 0;
}

🎮 互动实验：排序演示

输入数组元素，查看两种排序的过程

数组元素（用逗号分隔）：

输入数组后点击按钮...

🛠️ 算法比较

两种排序的对比

特性	插入排序	桶排序
最好时间复杂度	O(n)（已有序）	O(n+k)
平均时间复杂度	O(n²)	O(n+k)
最坏时间复杂度	O(n²)	O(n²)
空间复杂度	O(1)	O(n+k)
稳定性	稳定	稳定
数据类型	整数、浮点数	主要用于浮点数
适用场景	小数据、近乎有序	均匀分布的数据

💡 关键区别：
• 插入排序：原地排序，适合小规模数据，几乎有序时效率极高
• 桶排序：需要额外空间，适合均匀分布的浮点数，理想情况下O(n)
• k表示桶的数量，通常k≈n时性能最佳

插入排序的优势场景

// 场景1：数据几乎有序
// 插入排序在最好情况下只需O(n)时间
int arr1[] = {1, 2, 3, 5, 4};  // 只有一个元素位置错误

// 场景2：小规模数据
// 插入排序常数因子小，实际运行速度快
int arr2[] = {5, 3, 8, 1};  // 只有4个元素

// 场景3：在线排序（数据逐个到达）
// 每来一个新元素，直接插入到正确位置
// 不需要等待所有数据到达

桶排序的优势场景

// 场景1：均匀分布的浮点数
float arr[] = {0.12, 0.34, 0.56, 0.78, 0.91};

// 场景2：已知数据范围
// 可以合理设置桶的数量和范围

// 场景3：需要线性时间复杂度
// 当数据均匀分布时，桶排序接近O(n)

// 注意：桶排序不适合以下情况
// × 数据分布不均匀（某些桶很多元素，某些桶很少）
// × 数据范围未知或很大
// × 内存受限（需要额外空间存储桶）

实际应用：考试成绩排序

#include <iostream>
#include <vector>
using namespace std;

// 使用插入排序对学生成绩排序
void sortScores(double scores[], int n) {
    for (int i = 1; i < n; i++) {
        double key = scores[i];
        int j = i - 1;
        
        while (j >= 0 && scores[j] < key) {  // 降序排序
            scores[j + 1] = scores[j];
            j--;
        }
        
        scores[j + 1] = key;
    }
}

int main() {
    double scores[] = {85.5, 92.0, 78.5, 95.0, 88.0};
    int n = 5;
    
    cout << "=== 成绩排名（从高到低）===" << endl;
    sortScores(scores, n);
    
    for (int i = 0; i < n; i++) {
        cout << (i+1) << ". " << scores[i] << "分" << endl;
    }
    
    return 0;
}

🚀 性能分析与优化

插入排序的时间复杂度分析

// 最好情况：数组已经有序
// 每次只需要比较1次，不需要移动
// 总比较次数 = n-1
// 时间复杂度 = O(n)

// 最坏情况：数组逆序
// 第1个元素：比较0次
// 第2个元素：比较1次，移动1次
// 第3个元素：比较2次，移动2次
// ...
// 第n个元素：比较n-1次，移动n-1次

// 总比较次数 = 1 + 2 + ... + (n-1) = n(n-1)/2
// 总移动次数 = 1 + 2 + ... + (n-1) = n(n-1)/2
// 时间复杂度 = O(n²)

// 平均情况：随机排列
// 平均比较次数 ≈ n²/4
// 时间复杂度 = O(n²)

情况	比较次数	移动次数	时间复杂度
最好（已有序）	n-1	0	O(n)
最坏（逆序）	n(n-1)/2	n(n-1)/2	O(n²)
平均（随机）	n²/4	n²/4	O(n²)

桶排序的时间复杂度分析

// 假设：n个元素，k个桶

// 第1步：分配元素到桶 - O(n)
// 第2步：对每个桶排序 - 取决于桶内排序算法
// 第3步：合并桶 - O(n)

// 理想情况：数据均匀分布
// 每个桶有 n/k 个元素
// 使用插入排序：O((n/k)²) per bucket
// 总时间：k × O((n/k)²) = O(n²/k)
// 当 k ≈ n 时：O(n²/n) = O(n)

// 最坏情况：所有元素在一个桶中
// 退化为插入排序：O(n²)

// 空间复杂度：O(n + k)
// n个元素 + k个桶

💡 桶排序性能关键：
• 桶的数量k应该接近n
• 数据应该均匀分布
• 桶内排序算法的选择影响性能
• 理想情况下可以达到O(n)

插入排序的优化：二分插入

#include <iostream>
using namespace std;

// 二分查找插入位置
int binarySearch(int arr[], int left, int right, int key) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key) {
            return mid + 1;
        } else if (arr[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

// 二分插入排序
void binaryInsertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        
        // 使用二分查找找到插入位置
        int pos = binarySearch(arr, 0, i - 1, key);
        
        // 移动元素
        for (int j = i - 1; j >= pos; j--) {
            arr[j + 1] = arr[j];
        }
        
        arr[pos] = key;
    }
}

// 优点：减少比较次数从O(n)到O(log n)
// 缺点：移动次数仍然是O(n)，总体仍是O(n²)
// 但实际运行速度更快（比较操作通常比移动快）

📝 实战练习

📝 理解测试

对于近乎有序的数组 [1, 2, 3, 5, 4]，哪种排序算法最快？

选择答案查看解析...

💻 综合挑战

题目：实现一个完整的排序比较程序：
1. 生成随机数组
2. 分别用插入排序和桶排序进行排序
3. 统计两种排序的执行时间
4. 验证排序结果是否正确
5. 分析两种算法的性能差异

点击"生成代码框架"查看提示...