冒泡排序算法

冒泡排序是一种简单的排序算法。这是一种基于比较的排序算法，其中每对相邻元素进行比较，如果它们没有按顺序排列，则交换元素。该算法不适用于大型数据集，因为它的平均和最坏情况复杂度为 O(n²)，其中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)

显然，该图显示了冒泡排序的n²特性。

在此算法中，比较次数与数据集无关，即提供的输入元素是按排序顺序、反向顺序还是随机顺序。

内存需求

从上面描述的算法可以看出，冒泡排序不需要额外的内存。

示例

我们以一个未排序的数组为例。冒泡排序需要Ο(n2)时间，所以我们将其保持简短和精确。

冒泡排序从最前面的两个元素开始，比较它们以检查哪个更大。

在这种情况下，值 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; //flag to detect any swap is there or not
      for(int j = 0; j<size-i-1; j++) {
         if(array[j] > array[j+1]) { //when the current item is bigger than next
            int temp;
            temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
            swaps = 1; //set swap flag
         }
      }
      if(!swaps)
         break; // No swap in this pass, so array is sorted
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {67, 44, 82, 17, 20}; //initialize an array 
   printf("Array before Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ",arr[i]);
   printf("\n");
   bubbleSort(arr, n);
   printf("Array after Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ", arr[i]);
   printf("\n");
}

Array before Sorting: 67 44 82 17 20 
Array after Sorting: 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; //flag to detect any swap is there or not
      for(int j = 0; j<size-i-1; j++) {
         if(array[j] > array[j+1]) { //when the current item is bigger than next
            int temp;
            temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
            swaps = 1; //set swap flag
         }
      }
      if(!swaps)
         break; // No swap in this pass, so array is sorted
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {67, 44, 82, 17, 20}; //initialize an array
   cout << "Array before Sorting: ";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
   bubbleSort(arr, n);
   cout << "Array after Sorting: ";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
}

Array before Sorting: 67 44 82 17 20 
Array after Sorting: 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}; //initialize an array
      System.out.print("Array before Sorting: ");
      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; //flag to detect any swap is there or not
         for(int j = 0; j<n-i-1; j++) {
            if(arr[j] > arr[j+1]) { //when the current item is bigger than next
               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("Array After Sorting: ");
      for(int i = 0; i<n; i++)
         System.out.print(arr[i] + " ");
      System.out.println();
   }
}

Array before Sorting: 67 44 82 17 20 
Array After Sorting: 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("Array before Sorting: ")
print(arr)
bubble_sort(arr, n);
print("Array after Sorting: ")
print(arr)

Array before Sorting: 
[67, 44, 82, 17, 20]
Array after Sorting: 
[17, 20, 44, 67, 82]