冒泡排序算法
冒泡排序是一种简单的排序算法。这种排序算法基于比较，它会比较每对相邻元素，如果它们顺序不对，则交换元素。该算法不适用于大型数据集，因为其平均和最坏情况复杂度均为 O(n2)，其中 n 为项目数。
冒泡排序算法
冒泡排序是一种基本的排序算法，其工作原理是根据需要反复交换相邻元素。当不需要交换元素时，文件即已排序。
假设 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]
伪代码
我们在算法中观察到，冒泡排序会比较每一对数组元素，除非整个数组完全按升序排序。这可能会导致一些复杂性问题，例如，如果数组中所有元素都已升序排列，不再需要交换元素，该怎么办？
为了解决这个问题，我们使用一个标志变量 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;
}
}
分析
这里，比较次数为
1 + 2 + 3 + ... + (n - 1) = n(n - 1)/2 = O(n2)
显然，该图显示了冒泡排序的n2性质。
在该算法中，比较次数与数据集无关，即提供的输入元素是按排序顺序、反向顺序还是随机排列。
内存需求
从上述算法可以看出，冒泡排序不需要额外的内存。
示例
我们以一个未排序的数组作为示例。冒泡排序需要Ο(n²)的时间，所以我们尽量保持其简短和精确。
冒泡排序从最开始的两个元素开始，比较它们以确定哪个更大。
在本例中，值33大于14，因此它已经位于已排序的位置。接下来，我们比较 33 和 27。
我们发现 27 小于 33，这两个值必须交换。
接下来，我们比较 33 和 35。我们发现两者都处于已排序的位置。
然后我们转到接下来的两个值，35 和 10。
我们知道 10 小于 35。因此它们没有排序。我们交换这些值。我们发现已经到达数组末尾。经过一次迭代后，数组应该如下所示 −
准确地说，我们现在展示的是每次迭代后数组应该是什么样子。第二次迭代后，结果应如下所示 −
请注意，每次迭代后，至少有一个值在末尾移动。
当不需要交换元素时，冒泡排序会判断数组已完全排序。
现在我们应该研究一下冒泡排序的一些实际操作。
实现
在我们的原始算法及其改进的伪代码中，还有一个问题没有解决：每次迭代后，最大值都会稳定在数组的末尾。因此，下一次迭代不需要包含已排序的元素。为此，在我们的实现中，我们限制了内部循环以避免包含已排序的值。
#include <stdio.h>
void bubbleSort(int array[], int size){
for(int i = 0; i<size; i++) {
int swaps = 0; //标志来检测是否存在任何交换
for(int j = 0; j<size-i-1; j++) {
if(array[j] > array[j+1]) { //当当前项大于下一个项时
int temp;
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
swaps = 1; //set swap flag
}
}
if(!swaps)
break; // 此过程没有交换，因此数组是排序的
}
}
int main(){
int n;
n = 5;
int arr[5] = {67, 44, 82, 17, 20}; //initialize an array
printf("排序前的数组：");
for(int i = 0; i<n; i++)
printf("%d ",arr[i]);
printf("
");
bubbleSort(arr, n);
printf("排序后的数组：");
for(int i = 0; i<n; i++)
printf("%d ", arr[i]);
printf("
");
}
输出
排序前的数组：67 44 82 17 20 排序后的数组：17 20 44 67 82
#include<iostream>
using namespace std;
void bubbleSort(int *array, int size){
for(int i = 0; i<size; i++) {
int swaps = 0; //标志来检测是否存在任何交换
for(int j = 0; j<size-i-1; j++) {
if(array[j] > array[j+1]) { //当当前项大于下一个项时
int temp;
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
swaps = 1; //set swap flag
}
}
if(!swaps)
break; // 此过程没有交换，因此数组是排序的
}
}
int main(){
int n;
n = 5;
int arr[5] = {67, 44, 82, 17, 20}; //初始化数组
cout << "排序前的数组：";
for(int i = 0; i<n; i++)
cout << arr[i] << " ";
cout << endl;
bubbleSort(arr, n);
cout << "排序后的数组：";
for(int i = 0; i<n; i++)
cout << arr[i] << " ";
cout << endl;
}
输出
排序前的数组：67 44 82 17 20 排序后的数组：17 20 44 67 82
import java.io.*;
import java.util.*;
public class BubbleSort {
public static void main(String args[]) {
int n = 5;
int[] arr = {67, 44, 82, 17, 20}; //初始化数组
System.out.print("排序前的数组：");
for(int i = 0; i<n; i++)
System.out.print(arr[i] + " ");
System.out.println();
for(int i = 0; i<n; i++) {
int swaps = 0; //标志来检测是否存在任何交换
for(int j = 0; j<n-i-1; j++) {
if(arr[j] > arr[j+1]) { //当当前项大于下一个项时
int temp;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swaps = 1; //set swap flag
}
}
if(swaps == 0)
break;
}
System.out.print("排序后的数组：");
for(int i = 0; i<n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
输出
排序前的数组：67 44 82 17 20 排序后的数组：17 20 44 67 82
def bubble_sort(array, size):
for i in range(size):
swaps = 0;
for j in range(0, size-i-1):
if(arr[j] > arr[j+1]):
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swaps = 1;
if(swaps == 0):
break;
arr = [67, 44, 82, 17, 20]
n = len(arr)
print("排序前的数组：")
print(arr)
bubble_sort(arr, n);
print("排序后的数组：")
print(arr)
输出
排序前的数组： [67, 44, 82, 17, 20] 排序后的数组： [17, 20, 44, 67, 82]
