冒泡排序递归实现
Harshit Jindal
2023年1月30日
2021年2月7日
冒泡排序是一种简单的排序算法。它的工作原理是对相邻元素进行反复比较，如果它们的顺序不对，则进行交换。反复比较后，将最小/最大的元素向数组最后冒泡，因此这种算法被命名为冒泡排序。虽然效率不高，但它仍然代表了排序算法的基础。
冒泡排序递归算法
假设我们有一个未排序的数组 A[]，包含 n 个元素。
-
如果数组
A的大小是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<bits/stdc++.h>
using namespace std;
void bubbleSort(int arr[], int n)
{
if (n == 1)return;
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
}
}
bubbleSort(arr, n - 1);
}
int main() {
int n = 8;
int arr[8] = {9, 8 , 3 , 7, 5, 6, 4, 1};
cout << "Input arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
bubbleSort(arr, n); // Sort elements in ascending order
cout << "Output arr: ";
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)。
Author: Harshit Jindal
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