Sắp xếp · Chèn · Ổn định
Insertion Sort
Sắp xếp chèn — lấy từng phần tử và chèn vào đúng vị trí trong phần đã sắp, như cách sắp xếp bài poker trong tay.
Tốc độ
Chưa xử lý
Key (đang chèn)
Đang dịch phải
Đã sắp xong
So sánh0
Dịch chuyển0
Lượt0
Nhấn Chạy hoặc Bước kế...
Ý tưởng
Mảng được chia thành phần đã sắp (ban đầu chỉ có a[0]) và phần chưa sắp. Mỗi bước, lấy phần tử đầu tiên của phần chưa sắp (key = a[i]), dịch chuyển các phần tử lớn hơn key sang phải một vị trí, rồi chèn key vào chỗ trống.
Hiệu quả với mảng gần sắp: Khi dữ liệu gần như đã sắp xếp, Insertion Sort đạt O(n) vì mỗi phần tử chỉ dịch ít hoặc không dịch. Đây là lý do nhiều thư viện dùng Insertion Sort cho chunk nhỏ trong các thuật toán hybrid như TimSort.
Cài đặt C
insertion_sort.c
#include <stdio.h> void insertionSort(int a[], int n) { for (int i = 1; i < n; i++) { int key = a[i]; /* Phần tử cần chèn */ int j = i - 1; /* Dịch các phần tử lớn hơn key sang phải */ while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } /* Chèn key vào vị trí đúng */ a[j + 1] = key; } } int main() { int a[] = {12, 11, 13, 5, 6}; int n = sizeof(a) / sizeof(a[0]); insertionSort(a, n); for (int i = 0; i < n; i++) printf("%d ", a[i]); /* Output: 5 6 11 12 13 */ return 0; }
Độ phức tạp
| Trường hợp | Thời gian | Không gian | Ghi chú |
|---|---|---|---|
| Tốt nhất | O(n) | O(1) | Mảng đã sắp — mỗi key không dịch bước nào |
| Trung bình | O(n²) | O(1) | — |
| Tệ nhất | O(n²) | O(1) | Mảng sắp ngược — mỗi key dịch hết vùng đã sắp |
💡
TimSort: Python và Java sử dụng thuật toán hybrid TimSort — kết hợp Merge Sort và Insertion Sort. Với mảng nhỏ (< 64 phần tử), TimSort dùng Insertion Sort vì overhead thấp và cache-friendly.