Sắp xếp (Sorting)
Các thuật toán sắp xếp phổ biến
| Thuật toán | Thời gian | Bộ nhớ | Ổn định |
|---|---|---|---|
| Bubble Sort | Có | ||
| Selection Sort | Không | ||
| Insertion Sort | Có | ||
| Merge Sort | Có | ||
| Quick Sort | TB | Không | |
| Heap Sort | Không |
Trong thi đấu, luôn dùng hàm sort có sẵn — được tối ưu tốt nhất.
C++
#include <algorithm>
vector<int> a = {3, 1, 4, 1, 5, 9};
// Tăng dần
sort(a.begin(), a.end());
// Giảm dần
sort(a.begin(), a.end(), greater<int>());
// Tùy chỉnh comparator
sort(a.begin(), a.end(), [](int x, int y) {
return x > y; // giảm dần
});
// Sắp xếp mảng thô
sort(arr, arr + n);
// Sắp xếp pair: tăng theo first, giảm theo second
sort(v.begin(), v.end(), [](auto& a, auto& b) {
if (a.first != b.first) return a.first < b.first;
return a.second > b.second;
});
Python
a = [3, 1, 4, 1, 5, 9]
a.sort() # in-place tăng dần
a.sort(reverse=True) # in-place giảm dần
b = sorted(a) # trả về list mới
# Tùy chỉnh key
pairs = [(1, 3), (2, 1), (1, 2)]
pairs.sort(key=lambda x: (x[0], -x[1])) # tăng theo [0], giảm theo [1]
Tìm kiếm nhị phân (Binary Search)
Tìm kiếm nhị phân tìm một giá trị trong mảng đã sắp xếp với độ phức tạp .
Ý tưởng
Mỗi bước loại bỏ một nửa không gian tìm kiếm bằng cách so sánh với phần tử giữa.
Cài đặt thủ công
// Tìm vị trí của target trong mảng tăng dần
int binary_search(vector<int>& a, int target) {
int lo = 0, hi = a.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1; // không tìm thấy
}
Dùng STL trong C++
// lower_bound: iterator đến phần tử đầu tiên >= target
auto it = lower_bound(a.begin(), a.end(), target);
// upper_bound: iterator đến phần tử đầu tiên > target
auto it = upper_bound(a.begin(), a.end(), target);
// Số lần xuất hiện của target
int cnt = upper_bound(a.begin(), a.end(), x) - lower_bound(a.begin(), a.end(), x);
Python
import bisect
a = [1, 2, 2, 3, 4, 5]
bisect.bisect_left(a, 2) # 1 — vị trí đầu tiên >= 2
bisect.bisect_right(a, 2) # 3 — vị trí đầu tiên > 2
bisect.insort(a, 2) # chèn và giữ thứ tự
Tìm kiếm nhị phân trên đáp án
Kỹ thuật mạnh: thay vì tìm đáp án trực tiếp, tìm kiếm nhị phân trên không gian đáp án.
// Kiểm tra xem đáp án 'mid' có khả thi không
bool check(int mid) {
// ... logic kiểm tra
}
int lo = 0, hi = 1e9;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (check(mid)) hi = mid;
else lo = mid + 1;
}
// lo là đáp án nhỏ nhất thỏa mãn
Ví dụ: Tìm tốc độ in sách nhỏ nhất để in xong trong ngày.
Bình luận