冒泡排序

冒泡排序是一种排序算法，它比较两个相邻的元素，并在它们不在预期顺序时交换它们。

就像水中的气泡上升到表面一样，数组的每个元素在每次迭代中都会移动到末尾。因此，它被称为冒泡排序。

冒泡排序的工作原理

假设我们正在尝试按升序对元素进行排序。

1. 第一次迭代（比较和交换）

从第一个索引开始，比较第一个和第二个元素。
如果第一个元素大于第二个元素，则交换它们。
现在，比较第二个和第三个元素。如果它们不按顺序排列，则交换它们。
上述过程一直持续到最后一个元素。

比较相邻元素

2. 剩余迭代

剩余的迭代过程相同。

每次迭代后，未排序元素中最大的元素将放置在末尾。

Continue the swapping and put the largest element among the unsorted list at the end — 将最大的元素放在末尾

每次迭代，比较都会进行到最后一个未排序的元素。

Swapping occurs only if the first element is greater than the next element — 比较相邻元素

当所有未排序的元素都放置在正确的位置时，数组就排序好了。

The array is sorted if all the elements are kept in the right order. — 如果所有元素都按正确的顺序排列，数组就排序好了

冒泡排序算法

bubbleSort(array)
  for i <- 1 to sizeOfArray - 1
    for j <- 1 to sizeOfArray - 1 - i
      if leftElement > rightElement
        swap leftElement and rightElement
end bubbleSort

Python、Java 和 C/C++ 中的冒泡排序代码

冒泡排序可视化：不要只阅读冒泡排序，观看它的实时演示。通过我们新的 DSA 可视化工具，一步一步地了解算法的每一行是如何工作的。亲自尝试！

Python

Java

C++

# Bubble sort in Python

def bubbleSort(array):
    
  # loop to access each array element
  for i in range(len(array)):

    # loop to compare array elements
    for j in range(0, len(array) - i - 1):

      # compare two adjacent elements
      # change > to < to sort in descending order
      if array[j] > array[j + 1]:

        # swapping elements if elements
        # are not in the intended order
        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp


data = [-2, 45, 0, 11, -9]

bubbleSort(data)

print('Sorted Array in Ascending Order:')
print(data)

// Bubble sort in Java

import java.util.Arrays;

class Main {

  // perform the bubble sort
  static void bubbleSort(int array[]) {
    int size = array.length;
    
    // loop to access each array element
    for (int i = 0; i < size - 1; i++)
    
      // loop to compare array elements
      for (int j = 0; j < size - i - 1; j++)

        // compare two adjacent elements
        // change > to < to sort in descending order
        if (array[j] > array[j + 1]) {

          // swapping occurs if elements
          // are not in the intended order
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
  }

  public static void main(String args[]) {
      
    int[] data = { -2, 45, 0, 11, -9 };
    
    // call method using class name
    Main.bubbleSort(data);
    
    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(data));
  }
}

// Bubble sort in C

#include <stdio.h>

// perform the bubble sort
void bubbleSort(int array[], int size) {

  // loop to access each array element
  for (int step = 0; step < size - 1; ++step) {
      
    // loop to compare array elements
    for (int i = 0; i < size - step - 1; ++i) {
      
      // compare two adjacent elements
      // change > to < to sort in descending order
      if (array[i] > array[i + 1]) {
        
        // swapping occurs if elements
        // are not in the intended order
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

// print array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}

int main() {
  int data[] = {-2, 45, 0, 11, -9};
  
  // find the array's length
  int size = sizeof(data) / sizeof(data[0]);

  bubbleSort(data, size);
  
  printf("Sorted Array in Ascending Order:\n");
  printArray(data, size);
}

// Bubble sort in C++

#include <iostream>
using namespace std;

// perform bubble sort
void bubbleSort(int array[], int size) {

  // loop to access each array element
  for (int step = 0; step < size -1; ++step) {
      
    // loop to compare array elements
    for (int i = 0; i < size - step - 1; ++i) {

      // compare two adjacent elements
      // change > to < to sort in descending order
      if (array[i] > array[i + 1]) {

        // swapping elements if elements
        // are not in the intended order
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

// print array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    cout << "  " << array[i];
  }
  cout << "\n";
}

int main() {
  int data[] = {-2, 45, 0, 11, -9};
  
  // find array's length
  int size = sizeof(data) / sizeof(data[0]);
  
  bubbleSort(data, size);
  
  cout << "Sorted Array in Ascending Order:\n";  
  printArray(data, size);
}

优化冒泡排序算法

在上述算法中，即使数组已经排序，也会进行所有比较。

这会增加执行时间。

为了解决这个问题，我们可以引入一个额外的变量 swapped。如果发生元素交换，则将 swapped 的值设置为 true。否则，设置为false。

一次迭代后，如果没有发生交换，则 swapped 的值将为false。这意味着元素已经排序，无需进行进一步的迭代。

这将减少执行时间，并有助于优化冒泡排序。

优化冒泡排序的算法是

bubbleSort(array)
  for i <- 1 to sizeOfArray - 1
    swapped <- false
    for j <- 1 to sizeOfArray - 1 - i
      if leftElement > rightElement
        swap leftElement and rightElement
        swapped <- true
    if swapped == false
      break
end bubbleSort

Python、Java 和 C/C++ 中的优化冒泡排序

优化冒泡排序可视化：不要只阅读优化冒泡排序，观看它的实时演示。通过我们新的 DSA 可视化工具，一步一步地了解算法的每一行是如何工作的。亲自尝试！

Python

Java

C++

# Optimized Bubble sort in Python

def bubbleSort(array):
    
  # loop through each element of array
  for i in range(len(array)):
        
    # keep track of swapping
    swapped = False
    
    # loop to compare array elements
    for j in range(0, len(array) - i - 1):

      # compare two adjacent elements
      # change > to < to sort in descending order
      if array[j] > array[j + 1]:

        # swapping occurs if elements
        # are not in the intended order
        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp

        swapped = True
          
    # no swapping means the array is already sorted
    # so no need for further comparison
    if not swapped:
      break

data = [-2, 45, 0, 11, -9]

bubbleSort(data)

print('Sorted Array in Ascending Order:')
print(data)

// Optimized Bubble sort in Java

import java.util.Arrays;

class Main {

  // perform the bubble sort
  static void bubbleSort(int array[]) {
    int size = array.length;
    
    // loop to access each array element
    for (int i = 0; i < (size-1); i++) {
    
      // check if swapping occurs
      boolean swapped = false;
      
      // loop to compare adjacent elements
      for (int j = 0; j < (size-i-1); j++) {

        // compare two array elements
        // change > to < to sort in descending order
        if (array[j] > array[j + 1]) {

          // swapping occurs if elements
          // are not in the intended order
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
          
          swapped = true;
        }
      }
      // no swapping means the array is already sorted
      // so no need for further comparison
      if (!swapped)
        break;

    }
  }

  public static void main(String args[]) {
      
    int[] data = { -2, 45, 0, 11, -9 };
    
    // call method using the class name
    Main.bubbleSort(data);
    
    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(data));
  }
}

// Optimized Bubble sort in C

#include 

// perform the bubble sort
void bubbleSort(int array[], int size) {

  // loop to access each array element
  for (int step = 0; step < size - 1; ++step) {
    
    // check if swapping occurs  
    int swapped = 0;
    
    // loop to compare array elements
    for (int i = 0; i < size - step - 1; ++i) {
      
      // compare two array elements
      // change > to < to sort in descending order
      if (array[i] > array[i + 1]) {
        
        // swapping occurs if elements
        // are not in the intended order
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        
        swapped = 1;
      }
    }
    
    // no swapping means the array is already sorted
    // so no need for further comparison
    if (swapped == 0) {
      break;
    }
    
  }
}

// print array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}

// main method
int main() {
  int data[] = {-2, 45, 0, 11, -9};
  
  // find the array's length
  int size = sizeof(data) / sizeof(data[0]);

  bubbleSort(data, size);
  
  printf("Sorted Array in Ascending Order:\n");
  printArray(data, size);
}

// Optimized bubble sort in C++

#include <iostream>
using namespace std;

// perform bubble sort
void bubbleSort(int array[], int size) {
    
  // loop to access each array element
  for (int step = 0; step < (size-1); ++step) {
      
    // check if swapping occurs
    int swapped = 0;
    
    // loop to compare two elements
    for (int i = 0; i < (size-step-1); ++i) {
        
      // compare two array elements
      // change > to < to sort in descending order
      if (array[i] > array[i + 1]) {

        // swapping occurs if elements
        // are not in intended order 
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        
        swapped = 1;
      }
    }

    // no swapping means the array is already sorted
    // so no need of further comparison
    if (swapped == 0)
      break;
  }
}

// print an array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    cout << "  " << array[i];
  }
  cout << "\n";
}

int main() {
  int data[] = {-2, 45, 0, 11, -9};
  
  // find the array's length
  int size = sizeof(data) / sizeof(data[0]);
  
  bubbleSort(data, size);
  
  cout << "Sorted Array in Ascending Order:\n";
  printArray(data, size);
}

冒泡排序复杂度

时间复杂度
最佳	O(n)
最坏	O(n²)
平均	O(n²)
空间复杂度	O(1)
稳定性	是

复杂度详解

冒泡排序会比较相邻的元素。

循环	比较次数
第 1 次	(n-1)
第 2 次	(n-2)
第 3 次	(n-3)
.......	......
最后	1

因此，比较次数为

(n-1) + (n-2) + (n-3) +.....+ 1 = n(n-1)/2

约等于 n²

因此，复杂度：O(n²)

另外，如果我们观察代码，冒泡排序需要两个循环。因此，复杂度为 n*n = n²

1. 时间复杂度

最坏情况复杂度： O(n²)
如果要按升序排序，而数组按降序排列，则会发生最坏情况。
最佳情况复杂度： O(n)
如果数组已经排序，则无需排序。
平均情况复杂度： O(n²)
当数组的元素混乱（既非升序也非降序）时，就会发生这种情况。

2. 空间复杂度

空间复杂度为 O(1)，因为使用了额外的变量进行交换。
在优化冒泡排序算法中，使用了两个额外的变量。因此，空间复杂度为 O(2)。

冒泡排序的应用

如果需要，则使用冒泡排序

复杂度不重要
倾向于简洁明了的代码

热门教程

热门实例

参考资料

认证课程

成为一名认证的 Python
程序员。

热门教程

参考资料

热门实例

DSA 简介

数据结构 (I)

数据结构 (II)

基于树的 DSA (I)

基于树的 DSA (II)

基于图的 DSA

排序和搜索算法

贪婪算法

动态规划

其他算法

冒泡排序

冒泡排序的工作原理

冒泡排序算法

Python、Java 和 C/C++ 中的冒泡排序代码

优化冒泡排序算法

Python、Java 和 C/C++ 中的优化冒泡排序

冒泡排序复杂度

复杂度详解

1. 时间复杂度

2. 空间复杂度

冒泡排序的应用

类似的排序算法

目录

热门教程

热门实例

参考资料

认证课程

成为一名认证的 Python程序员。

热门教程

参考资料

热门实例

DSA 简介

数据结构 (I)

数据结构 (II)

基于树的 DSA (I)

基于树的 DSA (II)

基于图的 DSA

排序和搜索算法

贪婪算法

动态规划

其他算法

DSA 教程

冒泡排序

冒泡排序的工作原理

冒泡排序算法

Python、Java 和 C/C++ 中的冒泡排序代码

优化冒泡排序算法

Python、Java 和 C/C++ 中的优化冒泡排序

冒泡排序复杂度

复杂度详解

1. 时间复杂度

2. 空间复杂度

冒泡排序的应用

类似的排序算法

目录

相关教程

成为一名认证的 Python
程序员。