Thuật toán sắp xếp trong Java: QuickSort & HeapSort

Thuật toán sắp xếp trong Java là tập các phương pháp để xếp phần tử theo thứ tự tăng hoặc giảm. Bài này giải thích QuickSort và HeapSort. Mình đưa ra phân tích độ phức tạp. Và cung cấp mã Java hoàn chỉnh để bạn copy và chạy. Bạn sẽ hiểu khi nào dùng thuật toán nào.

QuickSort là gì và khi nào nên dùng?

QuickSort (Sắp xếp nhanh) là một thuật toán chia để trị do C.A.R. Hoare phát triển.
Nó chia mảng thành hai phần dựa trên một phần tử “chốt” (pivot).
Các phần tử nhỏ hơn pivot nằm bên trái, phần tử lớn hơn nằm bên phải.

Thuật toán tiếp tục đệ quy cho đến khi mảng con chỉ còn một phần tử.
Kết quả cuối cùng là một mảng đã được sắp xếp hoàn chỉnh.

QuickSort là thuật toán sắp xếp tại chỗ (in-place) và hoạt động nhanh hơn MergeSort hoặc HeapSort trong hầu hết trường hợp.

Độ phức tạp:

• Trung bình: Θ(n log n)

• Xấu nhất: Θ(n²)

Hiệu suất của QuickSort phụ thuộc cách chọn pivot. Chọn pivot tốt giúp tránh trường hợp xấu và tăng tốc đáng kể.

Triển khai thuật toán sắp xếp trong Java – QuickSort

HeapSort là gì và khi nào nên dùng?

HeapSort (Sắp xếp vun đống) được đề xuất năm 1964 bởi J.W.J. Williams. Sau đó R.W. Floyd đã cải tiến để giúp nó chạy nhanh và tiết kiệm bộ nhớ. Thuật toán này dựa trên cấu trúc dữ liệu heap (cây nhị phân hoàn chỉnh). HeapSort chia mảng thành hai phần:

• Phần đã sắp xếp.

• Phần chưa sắp xếp.

Thay vì tìm phần tử lớn nhất theo cách tuyến tính, HeapSort dùng heap để trích phần tử lớn nhất nhanh hơn. HeapSort là thuật toán in-place, không cần thêm vùng nhớ phụ.
Tuy nhiên, nó không ổn định, tức là thứ tự của phần tử bằng nhau có thể thay đổi.

Thuật toán sắp xếp Heap Sort được chia thành hai giai đoạn:

Hai giai đoạn của HeapSort

Giai đoạn 1 – Xây dựng heap:
Biến mảng thành một cây nhị phân (max-heap hoặc min-heap).

Giai đoạn 2 – Trích phần tử lớn nhất:
Hoán đổi nút gốc với phần tử cuối.
Giảm kích thước heap và lặp lại đến khi mảng được sắp xếp hoàn toàn.

Triển khai thuật toán sắp xếp trong Java – Heap Sort

Dù tốc độ chạy của Heap Sort có đôi chút chậm hơn Quick Sort, nhưng bù lại Heapsort là giải thuật đảm bảo trong trường hợp xấu nhất, độ phức tạp giải thuật cũng là O (n log n). Giải thuật này cũng không cần thêm các cấu trúc dữ liệu phụ trợ trong quá trình thực thi, do đó sẽ có tốc độ nhanh và thường được sử dụng rộng rãi do không khó để hiện thực.

FAQ – Câu hỏi thường gặp

1. QuickSort hay HeapSort chạy nhanh hơn?
QuickSort thường nhanh hơn trung bình, nhưng HeapSort ổn định hơn trong trường hợp xấu.

2. Java có thuật toán sắp xếp nào tối ưu sẵn không?
Có. Arrays.sort() và Arrays.parallelSort() được tối ưu sẵn trong Java.

3. HeapSort có cần nhiều bộ nhớ không?
Không. Đây là thuật toán in-place, không cần vùng nhớ bổ sung.

Xem thêm các bài chia sẻ, hướng dẫn học lập trình khác tại đây.

⏱️ Estimated reading time: 7 phút

Tác Giả: Vũ Hoàng Tuấn