C语言中冒泡排序和选择排序详细讲解。

晚霞的不甘

发布于 2025-12-23 10:18:52

5870

1. 冒泡排序 (Bubble Sort)

算法原理

冒泡排序通过重复遍历要排序的列表，比较相邻元素并交换位置，使较大的元素逐渐"浮"到列表末尾。

算法步骤

1. 比较相邻的两个元素 2. 如果前一个比后一个大，交换它们 3. 对每一对相邻元素重复上述操作 4. 重复上述步骤，直到不需要交换为止

C语言实现

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        // 每次遍历将最大的元素冒泡到最后
        for (j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 优化版本：如果某次遍历没有发生交换，说明已经有序
void bubbleSortOptimized(int arr[], int n) {
    int i, j, temp;
    int swapped; // 标记是否发生交换
    
    for (i = 0; i < n - 1; i++) {
        swapped = 0;
        for (j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        // 如果没有发生交换，说明已经排序完成
        if (!swapped) break;
    }
}

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

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原数组: ");
    printArray(arr, n);
    
    bubbleSort(arr, n);
    
    printf("排序后: ");
    printArray(arr, n);
    
    return 0;
}

时间复杂度

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

2. 选择排序 (Selection Sort)

算法原理

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

算法步骤

1. 在未排序序列中找到最小元素 2. 将其放到已排序序列的末尾 3. 重复上述过程，直到所有元素排序完成

C语言实现

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, min_idx, temp;
    
    for (i = 0; i < n - 1; i++) {
        // 找到未排序部分的最小元素
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        
        // 将找到的最小元素与第i个位置交换
        if (min_idx != i) {
            temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

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

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原数组: ");
    printArray(arr, n);
    
    selectionSort(arr, n);
    
    printf("排序后: ");
    printArray(arr, n);
    
    return 0;
}

时间复杂度

· 所有情况：O(n²)

3. 综合例题

例题1：学生成绩排序

#include <stdio.h>

// 学生结构体
struct Student {
    char name[50];
    int score;
};

// 按成绩冒泡排序
void bubbleSortStudents(struct Student students[], int n) {
    int i, j;
    struct Student temp;
    
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (students[j].score < students[j + 1].score) {
                // 交换学生信息
                temp = students[j];
                students[j] = students[j + 1];
                students[j + 1] = temp;
            }
        }
    }
}

// 按成绩选择排序
void selectionSortStudents(struct Student students[], int n) {
    int i, j, max_idx;
    struct Student temp;
    
    for (i = 0; i < n - 1; i++) {
        max_idx = i;
        for (j = i + 1; j < n; j++) {
            if (students[j].score > students[max_idx].score) {
                max_idx = j;
            }
        }
        
        if (max_idx != i) {
            temp = students[i];
            students[i] = students[max_idx];
            students[max_idx] = temp;
        }
    }
}

void printStudents(struct Student students[], int n) {
    int i;
    printf("姓名\t成绩\n");
    printf("--------------\n");
    for (i = 0; i < n; i++) {
        printf("%s\t%d\n", students[i].name, students[i].score);
    }
}

int main() {
    struct Student students[] = {
        {"张三", 85},
        {"李四", 92},
        {"王五", 78},
        {"赵六", 96},
        {"钱七", 88}
    };
    int n = sizeof(students) / sizeof(students[0]);
    
    printf("原学生列表:\n");
    printStudents(students, n);
    
    // 使用冒泡排序按成绩降序排列
    bubbleSortStudents(students, n);
    
    printf("\n按成绩排序后(冒泡排序):\n");
    printStudents(students, n);
    
    return 0;
}

例题2：字符串数组排序

#include <stdio.h>
#include <string.h>

// 使用选择排序对字符串数组进行排序
void selectionSortStrings(char *arr[], int n) {
    int i, j, min_idx;
    char *temp;
    
    for (i = 0; i < n - 1; i++) {
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            if (strcmp(arr[j], arr[min_idx]) < 0) {
                min_idx = j;
            }
        }
        
        if (min_idx != i) {
            // 交换指针
            temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

void printStringArray(char *arr[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%s\n", arr[i]);
    }
}

int main() {
    char *names[] = {
        "orange", "apple", "banana", "grape", "cherry"
    };
    int n = sizeof(names) / sizeof(names[0]);
    
    printf("原字符串数组:\n");
    printStringArray(names, n);
    
    selectionSortStrings(names, n);
    
    printf("\n排序后的字符串数组:\n");
    printStringArray(names, n);
    
    return 0;
}

4. 两种排序算法的比较

特性冒泡排序选择排序 时间复杂度 O(n²) O(n²) 空间复杂度 O(1) O(1) 稳定性稳定不稳定 交换次数较多较少 适用场景小数据集、基本有序小数据集、交换成本高

5. 练习题目

1. 基础练习：编写程序对10个随机整数分别用冒泡排序和选择排序进行排序 2. 进阶练习：统计两种排序算法在排序过程中的比较次数和交换次数 3. 应用练习：对学生信息按多个字段（先按成绩，成绩相同按姓名）排序

这两种排序算法虽然效率不高，但它们是理解排序算法思想的基础，对于学习更高效的排序算法非常重要。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-09，如有侵权请联系 cloudcommunity@tencent.com 删除

int