氣泡排序遞迴實現
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