数据结构–冒泡排序

大家好，欢迎来到IT知识分享网。

一、冒泡排序

冒泡排序是最简单的交换排序方法。通过两两比较相邻记录的关键字，如果为逆序，则进行交换，从而使关键字小的记录如气泡一样逐渐往上“漂浮”或逐渐向下“坠落”。

二、排序过程

【算法步骤】

1. 将待排序的记录存放在数组str中，首先比较第一个记录与第二个记录的关键字，若逆序（即str[1].key > str[0].key），则交换这两个记录。接着，继续比较当前已排序部分的最后一个记录（即之前比较中未被移动至最后位置的最后一个记录）与下一个记录的关键字，并根据需要交换它们。这一过程一直进行到比较完第n-1个记录和第n个记录的关键字为止。通过这样一轮比较和可能的交换操作，可以将当前未排序部分的最大关键字移动到数组的正确位置（即数组的末尾），完成一轮选择排序的部分过程。

2. 进行第二趟冒泡排序，对前n-1个记录同第一步进行同样的操作，次大的元素（或次小的元素，取决于排序顺序）将被放置在数组的n-1位置上（即倒数第二个位置）。这是因为每一趟冒泡排序都会确保至少有一个元素被放置在它最终应该在的位置，而这个元素是当前未排序部分中最大（或最小）的。

3. 重复进行上述操作，直至在某一趟排序过程中没有进行过交换记录为止。(优化：定义一个变量flag，若有操作，变量值变为true，反之则为false。在判断flag是否产生变化选择是否跳出)

【冒泡排序过程(升序)】

第一趟排序：将49与27进行比较，明显49>27，交换位置得

第二趟排序：将49与13进行比较，明显49>13，交换位置得

第三趟排序：将49和76进行比较，明显49<76,不交换位置

第四趟排序：将76和97进行比较，明显76<97，不交换位置

第五趟排序：将97和65进行比较，明显97>65，交换位置得

第六趟排序：将97与38进行比较，明显97>38，交换位置得

第七趟排序：将97与49进行比较，明显97>49，交换位置得

进行其次比较之后，我们将最大关键字放在了数组最后一位。

按照上述方法进行第二轮比较，直至没有交换

结果为：

【算法描述】

#include<bits/stdc++.h> using namespace std; int main() { int str[] = { 49,27,13,76,97,65,38,49 };//初始化数组 int len = sizeof(str) / 4;//计算数组长度 cout << "排序前：" << endl;//输出排序前结果 for (int i = 0; i < len; i++) { cout << str[i] << " "; } cout << endl; bool flag = false;//优化步骤，标记这一轮是否发生交换 for (int i = 0; i < len - 1; i++) { //比较轮数 for (int j = 0; j < len - i - 1; j++) { //比较次数 if (str[j] > str[j + 1]) { // >升序排序 < 降序排序 flag = true; //置为true，表示本趟排序发生了交换 int t = str[j]; str[j] = str[j + 1]; str[j + 1] = t; } } if (flag == false) { break; } } cout << "排序后：" << endl; for (int i = 0; i < len; i++) { cout << str[i] << " "; } }

三、例题

5334. 冒泡排序 – AcWing题库

四、总结

【时间复杂度】

最好情况：
        当输入数组已经是正序（即从小到大排序）时，只需要进行一次遍历就可以完成，因为在这一次遍历中，我们会发现没有任何一对相邻元素需要交换。然而，即使在这种情况下，我们仍然可以说冒泡排序进行了n-1次比较（其中n是数组的长度）

最坏情况：
        当输入数组是逆序（即从大到小排序）时，冒泡排序需要进行n-1趟排序（或称为n-1次遍历），每趟排序都会将当前未排序部分的最大元素移动到其最终位置。在每趟排序中，除了最后一趟可能只进行一次比较外（因为最大的元素已经在它应该在的位置上了），其他每趟都需要进行n-i-1次比较（其中i是当前趟数，从0开始计数）。因此，最坏情况下的总比较次数是(n-1) + (n-2) + ... + 2 + 1 = n*(n-1)/2，即等差数列求和的结果。同时，每次比较都可能导致记录的交换，因此在最坏情况下，记录的移动次数与比较次数相同，也是n*(n-1)/2。

【空间复杂度】

“冒泡排序在交换两个元素的关键字时，仅需要一个固定大小的辅助空间（如变量t）来暂存其中一个元素的值，因此其空间复杂度为O(1)。”

【算法特点】

1. 稳定排序

2. 可用于链式存储结构

3. 移动次数较多，算法的平均时间性能比直接插入排序差（当初始记录无序，n较大时，不宜采用冒泡排序）