Ở đây chúng ta xem một số phương pháp sắp xếp. Có 200+ kỹ thuật sắp xếp. Chúng ta xem một vài. Một số dựa trên so sánh (comparison based), một số không (non-comparison based).
Kỹ thuật so sánh: bubble sort, selection sort, insertion sort, merge sort, quicksort, heap sort... Giá trị được so sánh và đặt vào vị trí đã sắp xếp qua các giai đoạn. Độ phức tạp thời gian:
Sắp xếp dựa trên so sánh (Comparison Based)
| Loại phân tích | Bubble Sort | Selection Sort | Insertion Sort | Merge Sort | Quick Sort | Heap Sort |
|---|---|---|---|---|---|---|
| Best Case | O(n²) | O(n²) | O(n) | O(n log n) | O(n log n) | O(n log n) |
| Average Case | O(n²) | O(n²) | O(n²) | O(n log n) | O(n log n) | O(n log n) |
| Worst Case | O(n²) | O(n²) | O(n²) | O(n log n) | O(n²) | O(n log n) |
Lưu ý: Sửa lại các giá trị Merge/Quick/Heap sort từ O(log n) thành O(n log n) cho chính xác.
Sắp xếp không dựa trên so sánh (Non-comparison Based)
Một số thuật toán: Radix sort, Bucket sort, Counting sort. Không so sánh hai phần tử khi sắp xếp. Độ phức tạp:
| Loại phân tích | Radix Sort (k = chữ số max) | Counting Sort (k = kích thước mảng đếm) | Bucket Sort (k = số bucket) |
|---|---|---|---|
| Best Case | O(nk) | O(n + k) | O(n + k) |
| Average Case | O(nk) | O(n + k) | O(n + k) |
| Worst Case | O(nk) | O(n + k) | O(n²) |
Các tiêu chí so sánh khác
- In-place vs Out-place: In-place không cần không gian phụ (quicksort, heapsort). Out-place cần không gian phụ (merge sort).
- Online vs Offline: Online chấp nhận phần tử mới trong quá trình sắp xếp (insertion sort là online).