Data Structures Algorithms 简明教程
Bubble Sort Algorithm
冒泡排序是一种简单的排序算法。该排序算法是基于比较的算法，其中比较相邻的两对元素，如果不按顺序则交换这些元素。此算法不适用于大型数据集，因为其平均和最坏情况的复杂度为 O(n2)，其中 n 是项目的数量。
Bubble Sort Algorithm
冒泡排序是一种基本排序算法，通过根据需要重复交换相邻元素来工作。当不需要交换时，文件将被排序。
我们假设 list 是 n 元素的数组。我们进一步假设 swap 函数交换给定数组元素的值。
*第 1 步 *——检查输入数组中的第一个元素是否大于数组中的下一个元素。
*第 2 步 *——如果较大，则交换这两个元素；否则，在数组中向前移动指针。
步骤 3−重复步骤 2，直至达到数组末尾。
步骤 4−检查元素是否已排序；如果没有，则从数组的最后一个元素到第一个元素重复上述过程（步骤 1 至步骤 3）。
步骤 5−最终获得的结果是有序数组。
Algorithm: Sequential-Bubble-Sort (A)
fori ← 1 to length [A] do
for j ← length [A] down-to i +1 do
if A[A] < A[j-1] then
Exchange A[j] ⟷ A[j-1]Pseudocode
我们在算法中观察到，冒泡排序会比较每对数组元素，除非整个数组按升序完全排序。这可能会导致一些复杂性的问题，例如，如果所有元素都已经按升序排序，则数组不再需要交换。
为了简化此问题，我们使用一个标记变量 swapped ，该变量将帮助我们了解是否发生过任何交换。如果没有发生交换，即数组不再需要进一步处理即可排序，它将退出循环。
冒泡排序算法的伪代码可以写成如下：
voidbubbleSort(int numbers[], intarray_size){
inti, j, temp;
for (i = (array_size - 1); i>= 0; i--)
for (j = 1; j <= i; j++)
if (numbers[j-1] > numbers[j]){
temp = numbers[j-1];
numbers[j-1] = numbers[j];
numbers[j] = temp;
}
}Analysis
在此处，比较次数是
1 + 2 + 3 + ... + (n - 1) = n(n - 1)/2 = O(n2)很明显，该图显示了冒泡排序的 n2 特性。
在此算法中，比较次数与数据集无关，即提供的输入元素是按升序、降序或随机顺序排列的。
Example
我们以一个未排序数组为例。冒泡排序耗费 Ο(n2) 时间，所以我们将其简短而精炼。
冒泡排序从前两个元素开始，比较它们以检查哪个元素更大。
在此情况下，值 33 大于 14，所以它已经位于经过排序的位置。接着，我们将 33 与 27 比较。
我们发现 27 小于 33，并且这两个值必须交换。
接着，我们比较 33 和 35。我们发现这两者都位于经过排序的位置。
然后，我们转到接下来的两个值，35 和 10。
我们知道 10 小于 35。因此，它们未经排序。我们将这些值交换。我们发现已经达到数组末尾。经过一次迭代后，数组应如下所示−
确切地说，我们现在展示了每个迭代之后数组应如何显示。经过第二次迭代后，它应如下所示−
请注意，在每次迭代后，至少有一个值会移动到末尾。
并且当不需要交换时，冒泡排序会认为数组是完全排序的。
现在我们应该深入了解冒泡排序的某些实用方面。