Mục lục bài họcĐang ở d04-b4
Standard Algorithms: Searching, Sorting, Recursion
Searching
Sequential search checks elements one at a time from index 0. It works on any array and needs up to n comparisons.
Binary search repeatedly halves the search interval and needs only about log₂n comparisons — but it is correct only on a sorted array. On unsorted data it does not crash; it simply returns the wrong answer.
int low = 0, high = a.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == key) return mid;
else if (a[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1;Sorting
Selection sort finds the smallest remaining element and swaps it into place. It always makes n(n − 1) / 2 comparisons, no matter what the data looks like.
Insertion sort takes the next element and slides it left into the already-sorted front portion. Its comparison count depends on the data: near-sorted input is fast, reverse-sorted input is worst case.
Recursion
A recursive method calls itself on a smaller input and stops at a base case. Trace one by writing the calls top-down, then combining the returned values bottom-up.
Tìm tuần tự xét từng phần tử từ đầu. Chạy được trên mọi mảng, tốn tối đa n phép so sánh. Tìm nhị phân mỗi lần cắt đôi vùng còn lại nên chỉ tốn khoảng log₂n phép so sánh — mảng 1.000 phần tử chỉ cần khoảng 10 lần. Đổi lại, nó chỉ đúng khi mảng đã sắp xếp. Trên mảng chưa sắp, nó không ném ngoại lệ và không treo máy: nó lặng lẽ trả về một kết quả sai, thường là −1 dù giá trị cần tìm vẫn nằm trong mảng.
Sắp xếp chọn tìm phần tử nhỏ nhất trong phần chưa sắp rồi hoán đổi vào đúng chỗ. Số phép so sánh của nó là n(n − 1) / 2, cố định, không phụ thuộc dữ liệu — mảng đã sắp sẵn cũng tốn đúng chừng ấy. Sau k lượt, k phần tử đầu đã ở đúng vị trí cuối cùng.
Sắp xếp chèn lấy phần tử kế tiếp rồi đẩy nó lùi về trái cho tới khi lọt vào đúng chỗ trong phần đầu đã sắp. Số phép so sánh phụ thuộc dữ liệu: gần như đã sắp thì rất nhanh, sắp ngược thì tệ nhất. Sau k lượt, k + 1 phần tử đầu đã sắp với nhau nhưng chưa chắc đã đúng vị trí cuối cùng — đây đúng là chỗ đề thi so hai thuật toán.
Đệ quy là phương thức tự gọi chính nó trên đầu vào nhỏ hơn và dừng ở trường hợp cơ sở. Cách lần vết không bao giờ sai: viết chuỗi lời gọi đi xuống cho tới trường hợp cơ sở, rồi ghép giá trị trả về đi ngược lên.
Sắp xếp chọn chạy trên mảng 8 phần tử tốn bao nhiêu phép so sánh giữa các phần tử? Kết quả có phụ thuộc thứ tự ban đầu không?
Lượt 1 phải xét cả 8 phần tử để tìm phần tử nhỏ nhất, tức 7 phép so sánh. Lượt 2 xét 7 phần tử còn lại: 6 phép. Cứ thế xuống tới lượt cuối cùng còn 2 phần tử: 1 phép.
Tổng: 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28, đúng bằng n(n − 1) / 2 với n = 8.
Không phụ thuộc thứ tự ban đầu. Vòng lặp tìm nhỏ nhất luôn quét hết phần chưa sắp, kể cả khi mảng đã sắp sẵn — nó không có cách nào biết mà dừng sớm. Chỉ có số lần hoán đổi mới thay đổi theo dữ liệu.
Điểm này phân biệt với sắp xếp chèn: chèn trên mảng đã sắp sẵn chỉ tốn 7 phép so sánh, vì mỗi phần tử so một lần với phần tử liền trước rồi dừng ngay.
k lượt của hai thuật toán sắp xếp. Cách chặn — nhớ một câu: chọn khoá cứng k phần tử ĐẦU vào vị trí cuối cùng, chèn chỉ làm k + 1 phần tử đầu sắp với nhau.n(n − 1) / 2 phép so sánh bất chấp dữ liệu; sắp xếp chèn thì tuỳ dữ liệu. Đệ quy: lần vết đi xuống tới trường hợp cơ sở rồi ghép ngược lên.Đọc xong rồi — làm thử ngay
Bài tập của chương Unit 4 — Data Collections gồm 14 câu trắc nghiệm và 8 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.