面试题：C语言冒泡排序与其他排序算法的性能对比及应用场景分析

冒泡排序与快速排序性能对比

时间复杂度
- 冒泡排序：
  - 最好情况（数据有序）：$O(n)$。因为只需遍历一次数组，没有元素交换。
  - 平均情况和最坏情况（逆序或随机）：$O(n^2)$。每次比较都可能进行元素交换，需要进行$n(n - 1)/2$次比较。
- 快速排序：
  - 最好情况（每次划分都均匀）：$O(nlogn)$。递归深度为$logn$，每层操作次数为$n$。
  - 平均情况：$O(nlogn)$。
  - 最坏情况（数据有序且每次选择的基准为最大或最小元素）：$O(n^2)$。递归深度变为$n$，每层操作次数为$n$。
空间复杂度
- 冒泡排序：$O(1)$。只需几个临时变量，不随数据规模增长。
- 快速排序：
  - 最好和平均情况：$O(logn)$。递归调用栈的深度。
  - 最坏情况：$O(n)$。递归调用栈深度达到$n$。
适用场景
- 冒泡排序：适用于小规模数据或数据基本有序的情况。代码简单，实现容易。
- 快速排序：适用于一般情况下的大规模数据排序，平均性能最优。但在最坏情况下性能退化，需注意选择合适的基准元素。

性能测试C语言代码示例

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

// 冒泡排序
void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 快速排序分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    int j;
    for (j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            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);
    }
}

// 生成随机数组
void generateRandomArray(int arr[], int n, int min, int max) {
    int i;
    for (i = 0; i < n; i++) {
        arr[i] = rand() % (max - min + 1) + min;
    }
}

// 生成有序数组
void generateSortedArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        arr[i] = i;
    }
}

// 生成逆序数组
void generateReverseSortedArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        arr[i] = n - i;
    }
}

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

int main() {
    int n = 10000;
    int *arr1 = (int *)malloc(n * sizeof(int));
    int *arr2 = (int *)malloc(n * sizeof(int));
    clock_t start, end;
    double cpu_time_used;

    // 测试随机数据
    generateRandomArray(arr1, n, 1, 10000);
    for (int i = 0; i < n; i++) arr2[i] = arr1[i];

    start = clock();
    bubbleSort(arr1, n);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Bubble Sort (Random) Time: %f seconds\n", cpu_time_used);

    start = clock();
    quickSort(arr2, 0, n - 1);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Quick Sort (Random) Time: %f seconds\n", cpu_time_used);

    // 测试有序数据
    generateSortedArray(arr1, n);
    for (int i = 0; i < n; i++) arr2[i] = arr1[i];

    start = clock();
    bubbleSort(arr1, n);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Bubble Sort (Sorted) Time: %f seconds\n", cpu_time_used);

    start = clock();
    quickSort(arr2, 0, n - 1);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Quick Sort (Sorted) Time: %f seconds\n", cpu_time_used);

    // 测试逆序数据
    generateReverseSortedArray(arr1, n);
    for (int i = 0; i < n; i++) arr2[i] = arr1[i];

    start = clock();
    bubbleSort(arr1, n);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Bubble Sort (Reverse Sorted) Time: %f seconds\n", cpu_time_used);

    start = clock();
    quickSort(arr2, 0, n - 1);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Quick Sort (Reverse Sorted) Time: %f seconds\n", cpu_time_used);

    free(arr1);
    free(arr2);
    return 0;
}

此代码生成不同分布的数据（随机、有序、逆序），分别用冒泡排序和快速排序进行排序，并记录排序时间，以对比两种算法在不同情况下的性能。

星途面试题库

面试题：C语言冒泡排序与其他排序算法的性能对比及应用场景分析

知识考点

面试题答案

冒泡排序与快速排序性能对比

性能测试C语言代码示例