Skip to main content

Quick Sort

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

Mục lục​

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

Quick Sort cũng theo chiến lược chia để trị như Merge Sort, nhưng chia theo cách khác: chọn một phần tử làm pivot (ở đây là phần tử cuối đoạn), rồi phân vùng (partition) mảng sao cho mọi phần tử nhỏ hơn pivot nằm bên trái, mọi phần tử lớn hơn hoặc bằng nằm bên phải. Sau bước phân vùng, pivot đã đứng đúng vị trí cuối cùng của nó — thuật toán chỉ cần đệ quy tiếp tục trên hai đoạn con bên trái và bên phải.

Khác với Merge Sort, Quick Sort sắp xếp tại chỗ (in-place) — chỉ hoán đổi vị trí các phần tử, không cần mảng tạm.

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 viền tím là pivot, dải màu tím dưới hàng pin là đoạn [lo, hi] đang được phân vùng, cột màu xanh mint là các vị trí đã "chốt" cố định (pivot đã landing đúng chỗ).

SORTING · TRỰC QUAN HOÁ

Quick Sort

PHÂN VÙNG 0/7SO SÁNH 0/22HOÁN ĐỔI 0/10
0
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
9
 

Gọi quick_sort trên đoạn [0, 9].

quick_sort.pyO(n log n) trung bình, O(n²) xấu nhất · O(log n) space
1def quick_sort(lo, hi):
2 if lo >= hi: return
3 pivot = arr[hi]
4 p = lo
5 for i in range(lo, hi):
6 if arr[i] < pivot:
7 swap(arr[i], arr[p]); p += 1
8 swap(arr[p], arr[hi])
9 quick_sort(lo, p - 1)
10 quick_sort(p + 1, hi)
Bước 1/102

3. Độ phức tạp​

Quick Sort
Thời gian (trung bình)O(n log n)
Thời gian (xấu nhất — pivot luôn là min/max)O(n²)
Bộ nhớ phụO(log n) — ngăn xếp đệ quy
Ổn định (stable)Không

Trong thực tế, Quick Sort thường nhanh hơn Merge Sort dù cùng độ phức tạp trung bình O(n log n), vì sắp xếp tại chỗ nên tận dụng cache tốt hơn và không tốn chi phí cấp phát mảng tạm. Đây là lý do nhiều thư viện chuẩn (như qsort trong C, hoặc sort mặc định của một số ngôn ngữ) dùng các biến thể của Quick Sort (thường kết hợp Insertion Sort cho đoạn nhỏ, hoặc chọn pivot ngẫu nhiên để tránh trường hợp xấu nhất).