冒泡排序

冒泡排序：这是一种交换排序，基本思想是：两两比较相邻记录的关键字，如果前面的元素比后面元素大（反序），则进行交换，直到没有反序的元素为止。

冒泡排序的平均时间复杂度为O(n^2)。

// 冒泡排序
#include <stdio.h>

#define TRUE 1 // 真
#define FALSE 0 // 假

#define N 10 // 数组最大值
typedef int Status; // 函数返回结果类型

// 顺序表结构
typedef struct {
    int value[N + 1]; // 顺序表中的值
    int length; // 顺序表长度
} SqList;

/**
 * 交换顺序表L中i和j元素的值
 * @param L 顺序表
 * @param i 元素值
 * @param j 元素值
 */
void swap(SqList *L, int i, int j) {
    int temp = L->value[i];
    L->value[i] = L->value[j];
    L->value[j] = temp;
}

/**
 * 初始化顺序表
 * @param L 顺序表
 * @param d 存初始值的数组
 */
void InitSqList(SqList *L, int *d) {
    int i;

    for (i = 0; i < N; ++i) {
        L->value[i + 1] = d[i];
    }
    L->length = N;
}

/**
 * 遍历顺序表中元素的值
 * @param L 顺序表元素
 */
void Print(SqList L) {
    int i;

    printf("顺序表中的值为：");
    for (i = 1; i < L.length; i++) {
        printf("%d, ", L.value[i]);
    }
    printf("%d", L.value[i]);
    printf("\n");
}

/**
 * 冒泡排序（初级版）
 * 从顺序表最前面两个开始向后比较，每一轮排序都将确定第N小元素的位置
 * @param L 顺序表
 */
void BubbleSort0(SqList *L) {
    int i, j;

    for (i = 1; i < L->length; i++) {
        for (j = i + 1; j < L->length; j++) {
            if (L->value[i] > L->value[j]) { // 如果表中前面的元素比后面的元素大
                swap(L, i, j); // 交互这两个元素的位置
            }
        }
    }
}

/**
 * 冒泡排序（正式版）
 * 从顺序表最后面两个开始向前比较，每一轮排序都将确定第N小元素的位置
 * @param L 顺序表
 */
void BubbleSort(SqList *L) {
    int i, j;

    for (i = 1; i < L->length; i++) {
        for (j = L->length - 1; j >= i; j--) {
            if (L->value[j] > L->value[j + 1]) { // 如果表中前面的元素比后面的元素大
                swap(L, j, j + 1); // 交互这两个元素的位置
            }
        }
    }
}

/**
 * 冒泡排序（改进算法）
 * 从顺序表最后面两个开始向前比较，每一轮排序都将确定第N小元素的位置
 * 如果某轮排序没有交换，代表排序结束，效率比冒泡排序高
 * @param L
 */
void BubbleSort2(SqList *L) {
    int i, j;
    Status flag = TRUE; // 指示每一循环是否有交换的标记

    for (i = 1; i < L->length && flag; i++) {
        flag = FALSE; // 设置本轮循环未产生交换

        for (j = L->length - 1; j >= i; j--) {
            if (L->value[j] > L->value[j + 1]) { // 如果表中前面的元素比后面的元素大
                swap(L, j, j + 1); // 交互这两个元素的位置
                flag = TRUE; // 设置本轮进行了数据交换
            }
        }
    }
}

int main() {
    int d[N] = {50, 10, 90, 30, 70, 40, 80, 60, 20, 102}; // 存初始值的数组
    SqList L; // 顺序表

    InitSqList(&L, d); // 初始化顺序表
    printf("刚进行初始化后");
    Print(L); // 遍历顺序表

    BubbleSort0(&L); // 对顺序表进行初级冒泡排序
    printf("初级冒泡排序后");
    Print(L); // 遍历顺序表

    InitSqList(&L, d); // 初始化顺序表
    BubbleSort(&L); // 对顺序表进行正式冒泡排序
    printf("正式冒泡排序后");
    Print(L); // 遍历顺序表

    InitSqList(&L, d); // 初始化顺序表
    BubbleSort2(&L); // 对顺序表进行改进冒泡排序
    printf("改进冒泡排序后");
    Print(L); // 遍历顺序表
}

运行结果