選擇排序
選擇排序是一種簡單的排序演算法。它的工作原理是將陣列分為兩部分:已排序和未排序的子陣列。選擇排序在未排序子陣列中找到最小的元素,並將其移動到排序子陣列的最後一個索引。當交換操作的成本非常高時,就會用到它,因為在最大限度內,只需要 n
交換。
選擇排序演算法
假設我們有一個未排序的陣列 A[]
,包含 n
個元素。
-
選擇未排序子陣列中第一個元素的索引作為最小元素索引
min
。 -
將
min
處的值與其餘元素進行比較,如果發現較小的元素,則將其重置為該元素。 -
將
min
處的元素與排序子陣列最後一個索引的元素進行交換。 -
對未排序子陣列中的其餘元素重複以上步驟
n-2
次。
選擇排序示例
假設我們有陣列:(5,3,4,2,1,6)
。我們將使用選擇排序演算法對其進行排序。
- 第一次迭代
最小要素:A[4]
=1;
交換(A[4]
,A[0]
)。陣列變成:(1) (3,4,2,5,6)
。
- 第二次迭代
最小要素:A[3]
=2;
交換(A[3]
,A[1]
)。陣列變成:(1,2) (4,3,5,6)
。
- 第三次迭代
最小要素:A[3]
=3;
交換(A[3]
,A[2]
)。陣列變成:(1,2,3) (4,5,6)
。
- 第四次迭代
最小要素:A[3]
=4;
交換(A[3]
,A[3]
)。陣列變成:(1,2,3,4) (5,6)
。
- 第五次迭代
最小要素:A[4]
=5;
交換(A[4]
,A[4]
)。陣列變成:(1,2,3,4,5) (6)
。
最後一個元素已經被排序了。我們得到的排序陣列為:(1,2,3,4,5,6)
選擇排序演算法的實現
#include<bits/stdc++.h>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++)
{
// Find the minimum element for index i
int min = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min])
min = j;
// Put element in sorted position
swap(arr[min], arr[i]);
}
}
int main() {
int n = 6;
int arr[6] = {5, 3, 4, 2, 1, 6};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
selectionSort(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
因此,時間複雜度為 [Big Theta]量級:O(n2). 它也可以通過計算迴圈次數來計算。總共有兩個迴圈的 n
次迭代,所以複雜度為:n*n = n2。
- 最壞情況
最壞情況下的時間複雜度為 [Big O]:O(n2)。
- 最佳情況
最佳情況下的時間複雜度為 [Big Omega]:O(n2)。它與最壞情況下的時間複雜度相同。
空間複雜度
選擇排序演算法的空間複雜度為 O(1)
,因為除了一個臨時變數外,不需要額外的記憶體。
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