AP Computer Science A
selection sortVietnamese: sắp xếp chọn
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.
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.
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ũ.
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.
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.
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 .