Thuật toán trực quan: video hoạt hình ngắn, chạy thử từng bước, kèm code nhiều ngôn ngữ.
5 thuật toán
Nổi bật
Quét qua mảng, đổi chỗ hai phần tử kề nhau nếu sai thứ tự, để mỗi lượt giá trị lớn nhất nổi lên cuối. Bản sắp xếp tại chỗ, ổn định, dừng ngay khi một lượt không đổi chỗ lần nào: O(n) nếu đã sắp xếp, O(n²) còn lại.
Trung bìnhO(n log n)
Cắt mảng làm đôi, sắp xếp từng nửa, rồi trộn hai nửa đã có thứ tự trong một lượt. Bản sắp xếp trộn từ trên xuống, ổn định, dùng chung một bộ đệm cho mọi lần trộn: O(n log n) với mọi đầu vào, thêm O(n) bộ nhớ.
DễO(log n)
Tìm một giá trị trong mảng đã sắp xếp bằng cách nhìn phần tử ở giữa rồi bỏ đi nửa chắc chắn không chứa nó — một triệu phần tử chỉ mất khoảng 20 bước. Kèm luôn lowerBound, dạng hay gặp nhất khi phỏng vấn.
Trung bìnhO((V + E) log V)
Tìm đường đi ngắn nhất từ một đỉnh trên đồ thị có trọng số: luôn chốt đỉnh gần nhất chưa xong tiếp theo, nhờ hàng đợi ưu tiên. Có khoảng cách, cách dựng lại đường đi và lý do cạnh âm làm thuật toán sai.
Trung bìnhO(n log n) avg, O(n²) worst
Chọn một phần tử chốt, dồn giá trị nhỏ hơn sang trái và lớn hơn sang phải, rồi sắp xếp từng bên theo cùng cách đó. Bản sắp xếp tại chỗ dùng phân hoạch Hoare, chốt trung vị của ba và ngăn xếp chỉ O(log n).