Chia để trị: chọn một pivot, phân hoạch mảng thành 'nhỏ hơn pivot' và 'lớn hơn/bằng pivot', rồi đệ quy lên từng nửa. Trung bình O(n log n), xấu nhất O(n²).
Ý tưởng cốt lõi: nếu biết cách đặt đúng MỘT phần tử vào đúng vị trí cuối cùng của nó (so với các phần tử khác), thì phần còn lại tự chia thành hai bài toán con nhỏ hơn — đó là chia để trị.
Cho một mảng số nguyên, sắp xếp lại thành thứ tự tăng dần, nhanh hơn các thuật toán O(n²) như Bubble/Selection/Insertion Sort.
Chọn một phần tử làm pivot (ở đây chọn phần tử cuối đoạn). "Phân hoạch" (partition) đoạn mảng: duyệt qua, mọi phần tử nhỏ hơn pivot được dồn về bên trái, phần tử lớn hơn/bằng ở bên phải, rồi đặt pivot vào đúng ranh giới giữa hai vùng. Sau bước này, pivot đã ở đúng vị trí cuối cùng của nó trong mảng đã sắp xếp — không cần động vào nữa. Đệ quy làm tiếp với đoạn bên trái và đoạn bên phải.
| Trường hợp | Thời gian | Ghi chú |
|---|---|---|
| Trung bình | O(n log n) | Pivot chia mảng khá cân bằng mỗi lần |
| Xấu nhất | O(n²) | Mảng đã sắp xếp/ngược, luôn chọn pivot là phần tử nhỏ nhất hoặc lớn nhất |
| Không gian | O(log n) | Ngăn xếp đệ quy (trung bình); sắp xếp tại chỗ |
Trong thi đấu, tránh trường hợp xấu nhất bằng cách chọn pivot ngẫu nhiên hoặc lấy trung vị của 3 phần tử (đầu, giữa, cuối) thay vì luôn lấy phần tử cuối.
Mảng [6, 2, 9, 4], pivot = phần tử cuối = 4:
[2, 4, 9, 6]. Pivot 4 đã đúng vị trí cuối cùng.[2] (đã xong) và [9, 6] → phân hoạch tiếp cho ra [6, 9].[2, 4, 6, 9].sort() mặc định của C++ dùng Introsort (lai Quick Sort + Heap Sort) — hiểu Quick Sort giúp lý
giải vì sao STL sort trung bình rất nhanh.Kiểm tra nhanh
Quick Sort đạt độ phức tạp xấu nhất O(n²) khi nào?