常见排序算法详解

⭐
核心算法排序是编程面试必考内容，必须熟练掌握

算法概览

算法	平均时间	最坏时间	空间	稳定性
冒泡排序	O(n²)	O(n²)	O(1)	✅ 稳定
选择排序	O(n²)	O(n²)	O(1)	❌ 不稳定
插入排序	O(n²)	O(n²)	O(1)	✅ 稳定
快速排序	O(n log n)	O(n²)	O(log n)	❌ 不稳定

一、冒泡排序 (Bubble Sort)

📋 算法说明

通过相邻元素比较和交换，将最大（或最小）元素”冒泡”到数组末尾。

**核心思想：**相邻比较，大数下沉

难度：⭐ (入门)

基本实现

void bubbleSort(int arr[], int n) {
    // 外层循环：控制排序轮数
    for (int i = 0; i < n - 1; i++) {
        // 内层循环：相邻比较
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

优化版本

void bubbleSortOptimized(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;  // 标记本轮是否发生交换

        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }

        // 如果本轮没有交换，说明已经有序
        if (!swapped) break;
    }
}

🔍 算法解析

1. 为什么是 j < n - 1 - i？

// 第一轮：最大元素冒泡到 arr[n-1]
// 第二轮：次大元素冒泡到 arr[n-2]
// 第i轮：第i大元素冒泡到 arr[n-i]
// 所以内层循环只需要到 n-1-i

2. 执行过程示例

对 [5, 2, 8, 1, 9] 进行升序排序：

轮次	数组状态	说明
初始	[5, 2, 8, 1, 9]	-
第1轮	[2, 5, 1, 8, 9]	9冒泡到末尾
第2轮	[2, 1, 5, 8, 9]	8冒泡到位置3
第3轮	[1, 2, 5, 8, 9]	5冒泡到位置2
第4轮	[1, 2, 5, 8, 9]	2冒泡到位置1

3. 时间复杂度分析

**最好情况：**O(n) - 数组已经有序（优化版）
**最坏情况：**O(n²) - 数组逆序
**平均情况：**O(n²)

易错点

⚠️ 常见错误

内层循环写成 j < n - 1（应该是 j < n - 1 - i）
交换时忘记使用临时变量
数组越界：j + 1可能超出范围

二、选择排序 (Selection Sort)

📋 算法说明

每次从未排序部分选择最小元素，放到已排序部分的末尾。

**核心思想：**每次选最小，放到前面

难度：⭐ (入门)

基本实现

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // 假设当前元素是最小的
        int minIndex = i;

        // 在未排序部分找最小元素
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // 将最小元素放到正确位置
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

🔍 算法解析

1. 执行过程示例

对 [5, 2, 8, 1, 9] 进行排序：

轮次	最小值	数组状态
第1轮	1 (位置3)	[1, 5, 8, 2, 9]
第2轮	2 (位置3)	[1, 2, 8, 5, 9]
第3轮	5 (位置3)	[1, 2, 5, 8, 9]
第4轮	8 (位置3)	[1, 2, 5, 8, 9]

2. 关键点

minIndex初始化为i，不是0
内层循环从i + 1开始
找到最小元素后才交换，减少交换次数

3. 为什么不稳定？

// 示例：[5, 5, 2]
// 第一轮：选2，与第一个5交换
// 变成：[2, 5, 5]
// 两个5的相对位置改变了！

易错点

⚠️ 常见错误

minIndex初始化为0（应该是i）
内层循环从i开始（应该从i+1开始）
忘记检查minIndex != i导致不必要的交换

三、插入排序 (Insertion Sort)

📋 算法说明

将未排序元素插入到已排序部分的正确位置。

**核心思想：**像整理扑克牌一样

难度：⭐⭐ (较简单)

基本实现

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--;
        }

        // 插入key到正确位置
        arr[j + 1] = key;
    }
}

🔍 算法解析

1. 执行过程示例

对 [5, 2, 8, 1, 9] 进行排序：

轮次	待插入	过程	结果
初始	-	-	[5]
第1轮	2	2<5，5后移	[2, 5]
第2轮	8	8>5，直接插入	[2, 5, 8]
第3轮	1	1<2,5,8，全部后移	[1, 2, 5, 8]
第4轮	9	9>8，直接插入	[1, 2, 5, 8, 9]

2. 关键点

key必须单独保存，否则在移动元素时丢失
j从i-1开始，向前扫描
循环条件j >= 0 && arr[j] > key防止越界

3. 为什么稳定？

1
2
3

// 只在 arr[j] > key 时才移动
// 相等的元素不移动，保持相对位置
// 所以是稳定的

4. 时间复杂度特点

**最好情况：**O(n) - 数组已经有序
**最坏情况：**O(n²) - 数组逆序
**平均情况：**O(n²)

易错点

⚠️ 常见错误

忘记保存key，导致数据丢失
j从i开始（应该从i-1开始）
while循环条件缺少j >= 0导致越界
插入位置写成arr[j]（应该是arr[j+1]）

四、快速排序 (Quick Sort)

📋 算法说明

选择基准元素，将数组分为两部分，左边小于基准，右边大于基准，递归排序。

**核心思想：**分而治之

难度：⭐⭐⭐⭐ (较难)

基本实现

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = low - 1;        // i是小于基准元素的边界

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            // 交换arr[i]和arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 将基准放到正确位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}

// 快速排序主函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 分区
        int pi = partition(arr, low, high);

        // 递归排序左半部分
        quickSort(arr, low, pi - 1);

        // 递归排序右半部分
        quickSort(arr, pi + 1, high);
    }
}

🔍 算法解析

1. 执行过程示例

对 [5, 2, 8, 1, 9] 排序，选择9为基准：

初始: [5, 2, 8, 1, 9]
      基准=9

分区后: [5, 2, 8, 1] 9
       左边都小于9

递归左半部分: [5, 2, 8, 1]
选择基准=1

分区后: 1 [5, 2, 8]
       1是基准

继续分区...直到完全有序

2. 关键点

i从low-1开始，便于第一次i++
基准选择影响效率，一般选最后一个元素
递归终止条件：low < high

3. 时间复杂度

**最好情况：**O(n log n) - 每次基准恰好将数组平分
**最坏情况：**O(n²) - 每次基准是最小或最大元素
**平均情况：**O(n log n)

4. 空间复杂度

O(log n) - 递归调用栈的深度

优化建议

💡 快速排序优化

随机选择基准 - 避免最坏情况
三数取中法 - 选择首、中、尾的中位数作为基准
小数组改用插入排序 - 当n<10时用插入排序
三路划分 - 处理大量重复元素的情况

五、排序算法对比与应用

算法选择建议

场景	推荐算法	原因
小规模数据 (n<50)	插入排序	常数因子小，实现简单
基本有序	插入排序	时间复杂度接近O(n)
大规模数据	快速排序	平均性能最优
要求稳定	归并排序	稳定且O(n log n)
内存受限	堆排序	空间复杂度O(1)

实际应用示例

#include 
#include 
#include 

// 生成随机数组
void generateRandomArray(int arr[], int n) {
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % 100;
    }
}

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

// 测试各种排序算法
int main() {
    int arr1[10], arr2[10], arr3[10];

    generateRandomArray(arr1, 10);

    // 复制数组
    for (int i = 0; i < 10; i++) {
        arr2[i] = arr3[i] = arr1[i];
    }

    printf("原数组：");
    printArray(arr1, 10);

    // 测试冒泡排序
    bubbleSort(arr1, 10);
    printf("冒泡排序：");
    printArray(arr1, 10);

    // 测试选择排序
    selectionSort(arr2, 10);
    printf("选择排序：");
    printArray(arr2, 10);

    // 测试插入排序
    insertionSort(arr3, 10);
    printf("插入排序：");
    printArray(arr3, 10);

    return 0;
}

练习题

📝 基础练习

实现降序排序的冒泡排序
实现双向冒泡排序（鸡尾酒排序）
实现二分插入排序

📝 进阶练习

实现归并排序
实现堆排序
优化快速排序（三数取中）

📝 挑战练习

实现多路归并排序
实现带有计数功能的排序算法
对二维数组按某列排序

总结

记忆口诀

冒泡排序：相邻比较，大数下沉
选择排序：每次选小，放到前面
插入排序：像理扑克，插入到位
快速排序：选定基准，分而治之

时间复杂度记忆

冒泡、选择、插入都是O(n²)
快速、归并、堆都是O(n log n)
插入排序对基本有序的数据效率高