AP Computer Science A

sắp xếp chèninsertion sort

insertion sortVietnamese: sắp xếp chèn

Định nghĩaIn short

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ự.

Định nghĩa đầy đủ1 phút đọc

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ỗ.

Hay hiểu sai2 ý, 1 phút đọc

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.

Mẹo phòng thi2 mẹo

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 đủ.

Tần suất trong đề AP Computer Science AHow often it shows up on AP Computer Science AÍt gặpUncommon
Ví dụ có lời giải1 phút đọc
Mảng a sau đoạn mã là gì?

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.

Bạn nắm chắc chưa?Check your understanding

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.

Tạo tài khoảnCreate an account

Học tiếp từ đâyKeep learning

Bài học chứa thuật ngữ nàyLesson that uses this termThuật toán sắp xếpCấu trúc dữ liệu tập hợp, khoácourse AP Computer Science A
Liên quanRelatedthuật toánalgorithm
Mục tiêu và lộ trình unit ai cũng xem được — làm bài tập và lưu tiến độ thì cần đăng nhập.Anyone can view a unit's goals and roadmap — sign in to do the exercises and save your progress.

Cùng chủ đềSame topic

Biên soạn bởi DucklingStudy, bản quyền thuộc DucklingStudy.Written by DucklingStudy. © DucklingStudy. Xuất bảnPublished .