跳到主要内容

冒泡排序算法

提示
  1. 基本原理：冒泡排序通过比较相邻的元素并根据需要交换它们的位置，达到排序的目的。
  2. 迭代过程：在每次迭代中，数组中的每个元素都会向正确的位置“冒泡”上升，直到所有元素按预定顺序排列。
  3. 优化策略：通过引入 swapped 标志来检测一次迭代中是否发生了交换，以减少不必要的比较和优化性能。

冒泡排序 是一种排序算法，通过比较相邻两个元素并交换它们的位置，直至它们达到预期的顺序。

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

冒泡排序的工作原理​

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

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

  1. 从第一个索引开始，比较第一个和第二个元素。
  2. 如果第一个元素大于第二个元素，则交换它们。
  3. 接下来，比较第二个和第三个元素。如果它们顺序不正确，就交换它们。
  4. 上述过程一直进行到最后一个元素。 比较两个相邻元素，如果第一个元素大于下一个元素，则交换它们

2. 剩余迭代

剩余迭代中进行相同的过程。

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

继续交换并将未排序列表中的最大元素放在末尾

在每次迭代中，比较都发生在最后一个未排序元素之前。

只有当第一个元素大于下一个元素时才会发生交换

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

如果所有元素都按正确顺序排列，则数组被排序

冒泡排序算法​

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

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

Python Java C C++

# Python 中的冒泡排序

def bubbleSort(array):

  # 循环访问每个数组元素
  for i in range(len(array)):

    # 循环比较数组元素
    for j in range(0, len(array) - i - 1):

      # 比较两个相邻元素
      # 将 > 改为 < 可以按降序排序
      if array[j] > array[j + 1]:

        # 如果元素顺序不对，进行交换
        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp


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

bubbleSort(data)

print('升序排序后的数组:')
print(data)
// Java 中的冒泡排序

import java.util.Arrays;

class Main {

  // 执行冒泡排序
  static void bubbleSort(int array[]) {
    int size = array.length;

    // 循环访问每个数组元素
    for (int i = 0; i < size - 1; i++)

      // 循环比较数组元素
      for (int j = 0; j < size - i - 1; j++)

        // 比较两个相邻元素
        // 将 > 改为 < 可以按降序排序
        if (array[j] > array[j + 1]) {

          // 如果元素顺序不对，进行交换
          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 };

    // 使用类名调用方法
    Main.bubbleSort(data);

    System.out.println("升序排序后的数组:");
    System.out.println(Arrays.toString(data));
  }
}

优化的冒泡排序算法​

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

这增加了执行时间。

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

// C语言中的冒泡排序

#include <stdio.h>

// 执行冒泡排序
void bubbleSort(int array[], int size) {

  // 循环访问每个数组元素
  for (int step = 0; step < size - 1; ++step) {

    // 循环比较数组元素
    for (int i = 0; i < size - step - 1; ++i) {

      // 比较两个相邻元素
      // 将 > 改为 < 来进行降序排序
      if (array[i] > array[i + 1]) {

        // 如果元素不按预期顺序排列，则进行交换
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

// 打印数组
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};

  // 计算数组的长度
  int size = sizeof(data) / sizeof(data[0]);

  bubbleSort(data, size);

  printf("Sorted Array in Ascending Order:\n");
  printArray(data, size);
}
// C++中的冒泡排序

#include <iostream>
using namespace std;

// 执行冒泡排序
void bubbleSort(int array[], int size) {

  // 循环访问每个数组元素
  for (int step = 0; step < size; ++step) {

    // 循环比较数组元素
    for (int i = 0; i < size - step; ++i) {

      // 比较两个相邻元素
      // 将 > 改为 < 来进行降序排序
      if (array[i] > array[i + 1]) {

        // 如果元素不按预期顺序排列，则进行交换
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

// 打印数组
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};

  // 计算数组的长度
  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)
  swapped <- false
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
      swapped <- true
end bubbleSort

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

Python Java C C++

# Python中的优化冒泡排序

def bubbleSort(array):

  # 遍历数组的每个元素
  for i in range(len(array)):

    # 跟踪交换情况
    swapped = False

    # 循环比较数组元素
    for j in range(0, len(array) - i - 1):

      # 比较两个相邻元素
      # 将 > 改为 < 来进行降序排序
      if array[j] > array[j + 1]:

        # 如果元素不按预期顺序排列，则进行交换
        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp

        swapped = True

    # 没有交换意味着数组已经排序
    # 所以不需要进一步比较
    if not swapped:
      break

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

bubbleSort(data)

print('Sorted Array in Ascending Order:')
print(data)
// Java中的优化冒泡排序

import java.util.Arrays;

class Main {

  // 执行冒泡排序
  static void bubbleSort(int array[]) {
    int size = array.length;

    // 遍历访问每个数组元素
    for (int i = 0; i < (size-1); i++) {

      // 检查是否发生交换
      boolean swapped = false;

      // 循环比较相邻元素
      for (int j = 0; j < (size-i-1); j++) {

        // 比较两个数组元素
        // 将 > 改为 < 来进行降序排序
        if (array[j] > array[j + 1]) {

          // 如果元素不按预期顺序排列，则进行交换
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;

          swapped = true;
        }
      }
      // 没有交换意味着数组已经排序
      // 所以不需要进一步比较
      if (!swapped)
        break;

    }
  }

  public static void main(String args[]) {

    int[] data = { -2, 45, 0, 11, -9 };

    // 使用类名调用方法
    Main.bubbleSort(data);

    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(data));
  }
}
// C 中的优化冒泡排序

#include <stdio.h>

// 执行冒泡排序
void bubbleSort(int array[], int size) {

  // 循环访问每个数组元素
  for (int step = 0; step < size - 1; ++step) {

    // 检查是否发生交换
    int swapped = 0;

    // 循环比较数组元素
    for (int i = 0; i < size - step - 1; ++i) {

      // 比较两个数组元素
      // 将 > 改为 < 可以按降序排序
      if (array[i] > array[i + 1]) {

        // 如果元素顺序不对，进行交换
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;

        swapped = 1;
      }
    }

    // 如果没有交换，意味着数组已排序
    // 因此不需要进一步比较
    if (swapped == 0) {
      break;
    }

  }
}

// 打印数组
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};

  // 获取数组的长度
  int size = sizeof(data) / sizeof(data[0]);

  bubbleSort(data, size);

  printf("升序排序后的数组:\n");
  printArray(data, size);
}
// C++ 中的优化冒泡排序

#include <iostream>
using namespace std;

// 执行冒泡排序
void bubbleSort(int array[], int size) {

  // 循环访问每个数组元素
  for (int step = 0; step < (size-1); ++step) {

    // 检查是否发生交换
    int swapped = 0;

    // 循环比较两个元素
    for (int i = 0; i < (size-step-1); ++i) {

      // 比较两个数组元素
      // 将 > 改为 < 可以按降序排序
      if (array[i] > array[i + 1]) {

        // 如果元素顺序不对，进行交换
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;

        swapped = 1;
      }
    }

    // 如果没有交换，意味着数组已排序
    // 因此不需要进一步比较
    if (swapped == 0)
      break;
  }
}

// 打印数组
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};

  // 获取数组的长度
  int size = sizeof(data) / sizeof(data[0]);

  bubbleSort(data, size);

  cout << "升序排序后的数组:\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)。

冒泡排序的应用​

如果

  • 复杂度不重要
  • 更倾向于简短和简单的代码

那么可以使用冒泡排序。

类似的排序算法​

最后于 更新