冒泡排序

Harshit Jindal 2023年1月30日 2021年2月7日
  1. 冒泡排序算法
  2. 冒泡排序算法示例
  3. 冒泡排序算法的实现
  4. 冒泡排序算法的复杂度
冒泡排序

冒泡排序是一种简单的排序算法。它的工作原理是对相邻元素进行反复比较,如果它们的顺序不对,则进行交换。反复比较后,将最小/最大的元素向数组最后冒泡,因此这种算法被命名为冒泡排序。虽然效率不高,但它仍然代表了排序算法的基础。

冒泡排序算法

假设我们有一个未排序的数组 A[],包含 n 个元素。

  • 从前两个元素的对子(A[0]A[1])开始,比较它们的值,如果它们的顺序不对,就交换它们。对下一对元素(A[1]A[2])做同样的操作,并对数组的其余部分做类似的移动。最小/最大的元素在这一步之后的最后一个位置。
  • 对剩余的迭代重复上述步骤 (n-2) 次。每次数组大小减一,因为最后一个元素已经被排序。本次迭代中最小/最大的元素移动到最右边的位置。

上述算法中的第 1 步也称为执行。要对一个大小为 n 的数组进行排序,需要进行 n-1 次的执行。

冒泡排序算法示例

假设我们有数组:(5,3,4,2,1). 我们将使用冒泡排序算法对其进行排序。

  • 第一次执行:
(** 5 3 ** 4 2 1) (** 3 5 ** 4 2 1) (交换 3 <5)
(3 ** 5 4 ** 2 1) (3 ** 4 5 ** 2 1) (交换 4 <5)
(3 4 ** 5 2 ** 1) (3 4 ** 2 5 ** 1) (交换 2 <5)
(3 4 2 ** 5 1 **) (3 4 2 ** 1 5 **) (交换 1 <5)
  • 第二次执行:
(** 3 4 ** 2 1 5) (** 3 4 ** 2 1 5)
(3 ** 4 2 ** 1 5) (3 ** 2 4 ** 1 5) (交换 2 <4)
(3 2 ** 4 1 ** 5) (3 2 ** 1 4 ** 5) (交换 1 <4)
  • 第三次执行:
(** 3 2 ** 1 4 5) (** 2 3 ** 1 4 5) (交换 2 <3)
(2 ** 3 1 ** 4 5) (2 ** 1 3 ** 4 5) (交换<1 <3)
  • 第四次执行:
(** 2 1 ** 3 4 5) (** 1 2 ** 3 4 5) (交换 1 <2)

第四次执行后,我们得到排序数组 - (1 2 3 4 5)

冒泡排序算法的实现

#include<iostream>

using namespace std;
void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
}
int main() {

    int n = 5;
    int arr[5] = {5, 3, 4, 2, 1};
    cout << "Input array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    bubble_sort(arr, n); // Sort elements in ascending order
    cout << "Output array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

冒泡排序算法的复杂度

时间复杂度

  • 平均情况

平均来说,在冒泡排序的第 i 次执行中,会进行 n-i 次比较。因此,如果有 n 个通道,那么平均的时间复杂度可以用以下方式给出

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

因此,时间复杂度为 O(n2)。

  • 最坏情况

最坏的情况发生在数组被反向排序的时候,并且必须执行最大数量的比较和交换。

最坏的情况下时间复杂度是 O(n2)。

  • 最佳情况

最好的情况发生在数组已经被排序的时候,那么只需要进行 N 次比较。

最佳情况下的时间复杂度为 O(n)

空间复杂度

这个算法的空间复杂度是 O(n),因为除了一个临时变量外,不需要额外的内存。

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相关文章 - Sort Algorithm