6-1 基于顺序表的冒泡排序（重者沉）【有题解视频，可本地编译器调试】 分数 30 作者 通信DS课程组 单位 成都信息工程大学 本题要求实现基于顺序表的“重者沉”的冒泡排序算法，就是第一趟排序把最大值排到表尾，第二趟排序把次大值排到表尾倒数第二位，以此类推。最后要求打印出每一趟的排序结果。顺序表的结构体定义如下

题目描述

本题要求实现基于顺序表的“重者沉”的冒泡排序算法，就是第一趟排序把最大值排到表尾，第二趟排序把次大值排到表尾倒数第二位，以此类推。最后要求打印出每一趟的排序结果。

顺序表的结构体定义如下：

typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data[MAXSIZE];
    int Last;
};
typedef PtrToLNode List;

其中 `ElementType` 为顺序表中存储的元素类型，`MAXSIZE` 为顺序表的最大长度，`Last` 为顺序表中最后一个元素的下标。

函数接口定义：

void PrintList( List L );  // 输出整个表
void Bubble_Sort( List L );  // 冒泡排序

输入样例：

无输入。

输出样例：

无输出。

输入样例2：

无输入。

输出样例2：

假设顺序表中初始元素为 9 8 7 6 5 4 3 2 1 ，则每一趟排序的结果依次输出如下：

9 8 7 6 5 4 3 2 1 
8 7 6 5 4 3 2 1 9 
7 6 5 4 3 2 1 8 9 
6 5 4 3 2 1 7 8 9 
5 4 3 2 1 6 7 8 9 
4 3 2 1 5 6 7 8 9 
3 2 1 4 5 6 7 8 9 
2 1 3 4 5 6 7 8 9 
1 2 3 4 5 6 7 8 9 

函数实现：

void PrintList( List L )
{
    int i;
    for ( i = 0; i < L->Last; i++ )
        printf( "%d ", L->Data[i] );
    printf( "%d\n", L->Data[L->Last] );
}

void Bubble_Sort( List L )
{
    int i, j, tmp;
    for ( i = L->Last; i >= 1; i-- ) {  // i 表示尚未排好序的最后一个位置
        for ( j = 0; j < i; j++ ) {  // 内层循环遍历 i 之前的元素
            if ( L->Data[j] > L->Data[j+1] ) {  // 如果相邻元素逆序，则交换
                tmp = L->Data[j];
                L->Data[j] = L->Data[j+1];
                L->Data[j+1] = tmp;
            }
        }
        PrintList( L );  // 每一趟排序结束后输出结果
    }
}

时间复杂度

冒泡排序的最好时间复杂度为 $O(n)$（即顺序表已经有序的情况），最坏时间复杂度为 $O(n^2)$（即顺序表逆序的情况），平均时间复杂度为 $O(n^2)$。

空间复杂度

冒泡排序的空间复杂度为 $O(1)$，因为只需要常数级别的辅助空间来进行交换操作。

完整代码