AP Computer Science A
insertion sortVietnamese: sắp xếp chèn
Sắp xếp chèn (insertion sort) là thuật toán sắp xếp lấy lần lượt từng phần tử và chèn nó vào đúng chỗ trong phần đầu mảng đã sắp xếp.
Trực giác: Như xếp bài trên tay: rút từng lá mới, trượt nó vào giữa các lá đã xếp sao cho đúng thứ tự.
Insertion sort chia mảng thành phần đầu đã có thứ tự và phần còn lại. Mỗi lượt lấy phần tử kế tiếp, dời các phần tử lớn hơn nó sang phải một ô, rồi đặt nó vào chỗ trống. Khác selection sort, vốn tìm phần tử nhỏ nhất của phần còn lại rồi đổi chỗ.
Nghĩ sau lượt đầu phần tử nhỏ nhất đã ở vị trí 0 — đó là selection sort; insertion sort chỉ xếp phần đầu.
Quên điều kiện j >= 0 trong vòng while, gây ArrayIndexOutOfBoundsException.
Sau lượt thứ k, k+1 phần tử đầu đã có thứ tự với nhau nhưng chưa chắc ở vị trí cuối cùng.
Mảng đã gần có thứ tự thì insertion sort chạy rất ít bước; khác selection sort luôn so sánh đủ.
int[] a = {5, 2, 4, 1}; for (int i = 1; i < a.length; i++) { int key = a[i], j = i - 1; while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; } // a là {1, 2, 4, 5} Các lượt: {2, 5, 4, 1} → {2, 4, 5, 1} → {1, 2, 4, 5}. Mỗi lượt chèn `key` vào phần đầu đã sắp xếp.
Quiz câu thật từ ngân hàng đềReal exam questions from our question bank
Vài câu thật gắn đúng khái niệm này, chấm ngay kèm giải thích từng đáp án — hệ thống ghi nhớ bạn nắm tới đâu.A few real questions on exactly this concept, graded instantly with an explanation for every choice — the system remembers how well you know it.
Biên soạn bởi DucklingStudy, bản quyền thuộc DucklingStudy.Written by DucklingStudy. © DucklingStudy. Xuất bảnPublished .