AP Computer Science A

sắp xếp chọnselection sort

selection sortVietnamese: sắp xếp chọn

Định nghĩaIn short

Sắp xếp chọn (selection sort) là thuật toán mỗi lượt tìm phần tử nhỏ nhất trong phần chưa sắp xếp rồi đổi chỗ nó lên đầu phần đó.

Trực giác: Như xếp hàng theo chiều cao: mỗi lượt gọi bạn thấp nhất trong nhóm còn lại lên đứng ở chỗ trống đầu tiên.

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

Vòng ngoài chạy qua từng vị trí i; vòng trong tìm chỉ số giá trị nhỏ nhất từ i tới cuối, rồi hoán đổi với phần tử ở i. Với n phần tử, thuật toán cần n − 1 lượt và tối đa n − 1 lần hoán đổi. Khác sắp xếp chèn (insertion sort), phần đầu đã xếp của selection sort không bao giờ thay đổi về sau.

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

Nhầm với insertion sort: insertion sort chèn phần tử mới vào phần đầu, nên phần đầu vẫn có thể dịch chuyển.

Mảng đã sắp xếp không làm selection sort chạy nhanh hơn; vòng trong vẫn so sánh đủ.

Hoán đổi cần biến tạm; viết a[i] = a[min]; a[min] = a[i]; làm mất giá trị cũ.

Mẹo phòng thi2 mẹo

Sau k lượt vòng ngoài, k phần tử đầu là k giá trị nhỏ nhất và đã ở đúng vị trí cuối cùng.

Số phép so sánh luôn như nhau dù mảng đã sắp xếp sẵn hay chưa.

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
Selection sort trên {5, 2, 9, 1}: mảng sau lượt đầu và khi xong?

int[] a = {5, 2, 9, 1}; for (int i = 0; i < a.length - 1; i++) { int min = i; for (int j = i + 1; j < a.length; j++) if (a[j] < a[min]) min = j; int t = a[i]; a[i] = a[min]; a[min] = t; } // lượt 1: {1, 2, 9, 5}; cuối: {1, 2, 5, 9} Lượt đầu đổi 5 với 1 nhỏ nhất. Lượt hai 2 đã đúng chỗ, lượt ba đổi 9 với 5.

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

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