C语言实现排序之冒泡排序算法

1.代码

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

// 函数声明
// 创建并生成一个包含随机数的数组，数组大小由参数size指定
int* create_and_generate_random_array(int size);
// 打印数组内容，参数array是数组指针，size是数组大小
void print_array(int *array, int size);
// 对数组进行冒泡排序，参数array是数组指针，size是数组大小
void bubble_sort(int *array, int size);

int main() {
    int size = 10000; // 数组大小设为10000
    int *array = create_and_generate_random_array(size); // 创建并生成随机数组

    if (array == NULL) {
        // 如果内存分配失败，打印错误信息并返回1
        printf("Memory allocation failed\n");
        return 1;
    }

    // 打印原始数组
    // printf("Original array:\n");
    // print_array(array, size);

    // 获取排序开始时间
    clock_t start_time = clock();

    // 对数组进行冒泡排序
    bubble_sort(array, size);

    // 获取排序结束时间
    clock_t end_time = clock();

    // 计算排序执行时间并转换为毫秒
    double execution_time = ((double)(end_time - start_time) / CLOCKS_PER_SEC) * 1000;

    // 打印排序后的数组
    // printf("Sorted array:\n");
    // print_array(array, size);

    // 打印执行时间
    printf("Execution time: %.2f ms\n", execution_time);

    // 释放分配的内存
    free(array);

    return 0;
}

// 创建并生成包含随机数的数组，返回指向该数组的指针
int* create_and_generate_random_array(int size) {
    // 使用malloc函数动态分配内存，sizeof(int)计算单个整型变量的字节数，
    // 乘以size得到整个数组需要的总字节数。
    // malloc返回一个void指针，这里通过类型转换(int *)来将其转换为int类型的指针。
    int *array = (int *)malloc(sizeof(int) * size);
    if (array == NULL) {
        // 如果内存分配失败，返回NULL
        return NULL;
    }

    // 使用当前时间作为随机数种子
    srand(time(NULL));
    // 生成随机数组，数组元素为0到999之间的随机数
    for (int i = 0; i < size; i++) {
        //rand()一个介于 0 和 RAND_MAX 之间的整数。RAND_MAX 是一个常量，通常定义为 32767。
        array[i] = rand() % 1000;
    }

    return array; // 返回数组指针
}

// 打印数组内容
void print_array(int *array, int size) {
    for (int i = 0; i < size; i++) {
        // 打印数组的每个元素
        printf("%d ", array[i]);
    }
    printf("\n");
}

// 冒泡排序算法
void bubble_sort(int *array, int size) {
    // 外层循环控制排序轮数，共size-1轮
    for (int i = 0; i < size - 1; i++) {
        // 内层循环进行相邻元素的比较和交换
        for (int j = 0; j < size - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                // 如果前一个元素大于后一个元素，交换它们的位置
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

2.分析

/*
 * 冒泡排序（Bubble Sort）的时间复杂度和稳定性如下：

### 时间复杂度

冒泡排序的时间复杂度可以分为以下几种情况：

1. **最佳情况（Best Case）**：
   - 当数组已经是有序的情况下，冒泡排序只需进行一次遍历即可。每次遍历时，没有元素交换，所以最佳情况时间复杂度为 O(n)。
   - 这个情况只有在算法中包含一个检测排序完毕的标志时才有效，即如果在某一趟中没有进行任何交换操作，则可以提前终止排序过程。

2. **最坏情况（Worst Case）**：
   - 当数组是反序的情况下，冒泡排序需要进行 n-1 趟完整的比较和交换。最坏情况时间复杂度为 O(n^2)。

3. **平均情况（Average Case）**：
   - 在所有可能的排列情况下，冒泡排序的时间复杂度是 O(n^2)。

### 空间复杂度

冒泡排序的空间复杂度为 O(1)，因为它是原地排序算法，不需要额外的存储空间。

### 稳定性

冒泡排序是**稳定**的排序算法。稳定性指的是在排序过程中，两个相等的元素的相对顺序不会改变。由于冒泡排序在交换时只涉及相邻元素，所以相同的元素不会被交换，从而保持了它们的相对顺序。

### 总结

- **时间复杂度**:
  - 最佳情况: O(n)
  - 最坏情况: O(n^2)
  - 平均情况: O(n^2)
- **空间复杂度**: O(1)
- **稳定性**: 稳定

冒泡排序虽然简单易懂，但由于其最坏和平均情况下的时间复杂度为 O(n^2)，在处理大规模数据时性能较差，因此在实际应用中较少使用，更多是用于教学和理解排序算法的基础概念。
 */