基于顺序表的冒泡排序（重者沉）

好的，基于顺序表的冒泡排序（重者沉）的实现思路如下：

1. 从表的第一个元素开始，依次比较相邻两个元素的大小，如果前者大于后者，则交换它们的位置。
2. 经过第一轮比较后，最后一个元素一定是最大的，因为每次比较都会把较大的元素往后移动，于是我们可以将最后一个元素视为已经排好序的元素，不再参与后面的比较。
3. 重复上述步骤，直到所有元素都排好序为止。

下面是基于顺序表的冒泡排序（重者沉）的实现代码：

void bubble_sort(int a[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

其中，a[] 表示要排序的数组，n 表示数组中元素的个数。在冒泡排序的过程中，我们使用了两个循环，外层循环控制排序的轮数，内层循环控制每轮比较的次数。在每轮比较中，如果相邻两个元素的大小关系不满足要求，就进行交换操作。

相关问题

C语言顺序表冒泡排序代码

以下是C语言顺序表冒泡排序的代码示例：

#include <stdio.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 main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    for (int i=0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

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)$，因为只需要常数级别的辅助空间来进行交换操作。

完整代码