Cùng một bài, đọc bằng chữ. Nhanh hơn và tìm lại được bằng Ctrl+F.
Nhận thêm một lá bài
- Cầm bàiBài trên tay đã đúng thứ tự sẵn
- Lá mớiNhận thêm một lá, chưa biết xếp đâu
- Tìm chỗDò từ phải sang trái tới đúng vị trí
- Chèn vàoĐẩy các lá lớn hơn sang phải rồi chèn
Phần bên trái luôn đúng thứ tự
Insertion sort coi phần bên trái mảng là đã sắp xếp. Nó lấy phần tử kế tiếp rồi chèn vào đúng chỗ trong phần đó. Phần đã sắp xếp dài thêm một sau mỗi bước.
Điểm mạnh thật
Mảng gần đúng thứ tự thì chạy gần như O(n)
Ngưỡng trong thư viện thật
| Nơi dùng | Ngưỡng | Hằng số |
|---|---|---|
| JDK 8 | 47 | INSERTION_SORT_THRESHOLD |
| JDK 17 | 44 | MAX_INSERTION_SORT_SIZE |
| Go | 12 | maxInsertion |
Vì sao thư viện vẫn gọi insertion sort
Với đoạn vài chục phần tử, insertion sort thắng cả quick sort. Điều này không trái với O(n²). Big-O nói về xu hướng khi n lớn, không nói ai thắng trên mảng hai mươi phần tử.
Insertion sort được gì, mất gì
Ưu điểm
Mảng gần đúng thứ tự chạy gần như O(n)
Ổn định, và sắp xếp tại chỗ
Nhận dữ liệu đến dần, chèn tiếp là xong
Nhược điểm
Mảng ngẫu nhiên tốn khoảng n²/4 phép dịch
Dịch nhiều nên tốn khi phép ghi đắt
Chỉ hợp mảng nhỏ, luôn là bước phụ
Bài sau: merge sort
Hết nhóm n². Từ đây là nhóm n log n, bắt đầu bằng chia đôi.
