冒泡排序

冒泡排序分多个阶段对数组进行排序。如果元素不按顺序排列，则每次传递都会连续交换相邻元素。冒泡排序算法对数组进行多次遍历。在每次传递中，都会比较连续的相邻对。如果一对按降序排列，则交换其值；否则，值保持不变。该技术称为冒泡排序或下沉排序，因为较小的值逐渐“冒泡”到顶部，而较大的值则沉入底部。第一次遍历后，最后一个元素成为数组中最大的元素。第二遍之后，倒数第二个元素成为数组中第二大的元素。这个过程一直持续到所有元素都排序完毕。

下图 (a) 显示了对六个元素 (2 9 5 4 8 1) 的数组进行冒泡排序的第一遍。比较第一对中的元素（2 和 9），不需要交换，因为它们已经按顺序排列。比较第二对（9 和 5）中的元素，并将 9 与 5 交换，因为 9 大于 5。比较第三对（9 和 4）中的元素，并将 9 与 4 交换。比较第四对中的元素对（9 和 8），并将 9 与 8 交换。比较第五对（9 和 1）中的元素，并将 9 与 1 交换。正在比较的对突出显示，已排序的数字在下图中以斜体显示。

第一遍将最大的数字 (9) 作为数组的最后一个。在第二遍中，如下图 (b) 所示，您按顺序对元素对进行比较和排序。不需要考虑最后一对，因为数组中的最后一个元素已经是最大的了。在第三遍中，如下图 (c) 所示，您将按顺序对除最后两个元素之外的元素对进行比较和排序，因为它们已经按顺序排列。所以在第 k 遍中，你不需要考虑最后 k - 1 个元素，因为它们已经排序了。

冒泡排序的算法在下面的代码中描述。

for (int k = 1; k // 执行第 k 遍
for (int i = 0; i if (列表[i] > 列表[i + 1])
将 list[i] 与 list[i + 1] 交换；
}
}

请注意，如果一次传递中没有发生交换，则无需执行下一次传递，因为所有元素都已排序。您可以使用此属性来改进上面代码中的算法，如下代码所示。

布尔值 needNextPass = true;
for (int k = 1; k // 数组可能已排序并且不需要下一次遍历
needNextPass = false;
// 执行第 k 遍
for (int i = 0; i if (列表[i] > 列表[i + 1]) {
将 list[i] 与 list[i + 1] 交换；
需要下一个通行证 = true; // 还需要下一次传递
}
}
}

该算法可以用下面的代码实现

在最好的情况下，冒泡排序算法只需要第一遍就可以发现数组已经排序，不需要下一步。由于第一遍的比较次数为 n - 1，因此冒泡排序的最佳情况时间为 O(n)。

在最坏的情况下，冒泡排序算法需要 n - 1 遍。第一遍进行 n - 1 次比较；第二遍进行 n - 2 次比较；等等;最后一遍进行 1 次比较。因此，比较的总数为：

因此，冒泡排序最坏情况的时间是 O(n^2)。

以上是冒泡排序的详细内容。更多信息请关注PHP中文网其他相关文章！