Skip to main content

Selection Sort

Cập nhật: 2026-08-10

Mục lục​

1. Ý tưởng của Selection Sort​

Selection Sort chia mảng thành hai phần: phần đã sắp xếp (bên trái) và phần chưa sắp xếp (bên phải). Ở mỗi lượt, thuật toán quét toàn bộ phần chưa sắp xếp để tìm phần tử nhỏ nhất, rồi hoán đổi nó vào đầu phần chưa sắp xếp — mở rộng phần đã sắp xếp thêm một vị trí.

Với mảng có n phần tử, thuật toán cần đúng n - 1 lượt để hoàn tất.

2. Xem thuật toán chạy từng bước​

Bấm Chạy để xem animation tự động, hoặc dùng Lùi / Tiến để đi qua từng bước một. Cột màu cam là cặp đang được so sánh, viền xanh dương là min_idx hiện tại, và cột màu xanh mint là phần đã sắp xếp xong.

SORTING · TRỰC QUAN HOÁ

Selection Sort

LƯỢT 1/10SO SÁNH 0/45HOÁN ĐỔI 0/8
0
i, min
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
9
 

Bắt đầu lượt 1: tìm phần tử nhỏ nhất trong phần chưa sắp xếp.

selection_sort.pyO(n²) time · O(1) space
1for i in range(n):
2 min_idx = i
3 for j in range(i + 1, n):
4 if arr[j] < arr[min_idx]:
5 min_idx = j
6 arr[i], arr[min_idx] = arr[min_idx], arr[i]
Bước 1/134

3. Độ phức tạp​

Selection Sort
Thời gian (mọi trường hợp)O(n²)
Bộ nhớ phụO(1)
Ổn định (stable)Không
Số lần hoán đổiTối đa O(n) — ít hơn hẳn Bubble Sort

Điểm mạnh của Selection Sort là số lần hoán đổi rất ít (tối đa n - 1 lần), nên nó phù hợp khi chi phí ghi (write) đắt hơn nhiều so với chi phí so sánh — ví dụ ghi vào bộ nhớ flash.