Đây là ba thuật toán sắp xếp dựa trên so sánh đơn giản, độ phức tạp O(n²). Chúng chậm trên đầu vào lớn nhưng dễ hiểu và hữu ích để dạy cơ chế của việc sắp xếp.
Đây là ba thuật toán sắp xếp dựa trên so sánh đơn giản, độ phức tạp O(n²). Chúng chậm trên đầu vào lớn nhưng dễ hiểu và hữu ích để dạy cơ chế của việc sắp xếp.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # phần tử cần đặt vào
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # dịch các phần tử lớn hơn sang phải
j -= 1
arr[j + 1] = key # đặt key vào khoảng trống
return arr
insertion_sort([5, 2, 4, 1]) # -> [1, 2, 4, 5]
| Thuật toán | Tốt nhất | Xấu nhất | Ổn định | Tại chỗ |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Có | Có |
| Selection | O(n²) | O(n²) | Không | Có |
| Insertion | O(n) | O(n²) | Có | Có |
Insertion sort thực sự nhanh với các mảng nhỏ hoặc gần như đã sắp xếp và được dùng bên trong các thuật toán sắp xếp lai. Tránh dùng cả ba trên dữ liệu lớn chưa sắp xếp — hãy dùng các thuật toán sắp xếp O(n log n) thay thế.
Những thuật toán sắp xếp này xây dựng trực giác về bất biến (invariant), hoán đổi và tính ổn định trước khi bạn tiếp cận các thuật toán nâng cao.
Insertion sort nói riêng xuất hiện bên trong các thuật toán sắp xếp thực tế (như Timsort) cho các mảng con nhỏ.
Hiểu được tại sao chúng là O(n²) khiến bước nhảy lên các thuật toán sắp xếp O(n log n) trở nên có ý nghĩa.