Buổi 3: Mảng, tìm kiếm và sắp xếp
Hãy tưởng tượng bạn làm phần mềm cho một lớp học 40 sinh viên. Bạn cần lưu điểm của cả lớp, tính điểm trung bình, tìm bạn cao điểm nhất, xếp hạng danh sách và tra nhanh xem một mã sinh viên có trong lớp hay không. Nếu khai báo double score1, score2, ..., score40 thì chương trình dài lê thê và không thể dùng vòng lặp. Cấu trúc dữ liệu giải quyết bài toán này chính là mảng (array): một dãy ô nhớ liền nhau, cùng kiểu, truy cập bằng chỉ số. Buổi này bạn sẽ học cách khai báo và duyệt mảng, hiểu vì sao mảng trong Java là đối tượng nằm trên heap, làm việc với ma trận, dùng lớp tiện ích Arrays, rồi cài đặt các thuật toán kinh điển: tìm kiếm tuần tự, tìm kiếm nhị phân và ba thuật toán sắp xếp đơn giản.
Mục tiêu buổi học
- Sau buổi này bạn có thể khai báo, khởi tạo, duyệt mảng một chiều, hai chiều và mảng răng cưa bằng
forvàfor-each. - Sau buổi này bạn có thể giải thích mảng là đối tượng tham chiếu, dự đoán kết quả khi gán mảng, truyền mảng vào phương thức và sao chép mảng.
- Sau buổi này bạn có thể dùng thành thạo
Arrays.toString,sort,fill,copyOf,copyOfRange,equals,binarySearch. - Sau buổi này bạn có thể cài đặt tìm kiếm tuần tự và tìm kiếm nhị phân, biết khi nào dùng cái nào.
- Sau buổi này bạn có thể cài đặt sắp xếp chọn, nổi bọt, chèn và so sánh với
Arrays.sort. - Sau buổi này bạn có thể ước lượng sơ lược độ phức tạp thời gian bằng ký hiệu O lớn để chọn thuật toán phù hợp.
Bản đồ buổi học
| Phần | Nội dung | Thời lượng gợi ý |
|---|---|---|
| 1 | Mảng một chiều: khai báo, khởi tạo, chỉ số, duyệt | 25 phút |
| 2 | Mảng là đối tượng: tham chiếu, truyền tham số, sao chép | 20 phút |
| 3 | Mảng hai chiều và mảng răng cưa | 30 phút |
| 4 | Lớp tiện ích Arrays |
25 phút |
| 5 | Tìm kiếm tuần tự và nhị phân | 30 phút |
| 6 | Sắp xếp: chọn, nổi bọt, chèn | 30 phút |
| 7 | Độ phức tạp sơ lược và tổng kết | 20 phút |
Thực hành (ví dụ chạy thử và bài tập chấm tự động) chiếm khoảng 55% thời gian. Trong lúc đọc, hãy bấm nút chạy thử ở từng ví dụ, sửa code rồi chạy lại để xem kết quả thay đổi thế nào.
1. Mảng một chiều
1.1. Khai báo và tạo mảng
Mảng là một tập hợp có thứ tự các phần tử cùng kiểu, độ dài cố định sau khi tạo. Mỗi phần tử có một chỉ số (index) bắt đầu từ 0. Việc tạo một mảng gồm hai bước: khai báo biến mảng, rồi cấp phát bộ nhớ bằng new.
int[] scores; // khai báo biến tham chiếu tới mảng int
scores = new int[5]; // cấp phát 5 ô int, mỗi ô tự động bằng 0
int[] ages = new int[3]; // gộp hai bước vào một dòngCú pháp int[] a là phong cách Java chuẩn; cú pháp int a[] kiểu C vẫn hợp lệ nhưng không khuyến khích. Khi dùng new, Java tự điền giá trị mặc định cho mọi ô: 0 cho kiểu số nguyên, 0.0 cho kiểu thực, false cho boolean, '\u0000' cho char và null cho kiểu tham chiếu (như String).
int[] a = new int[4];
double[] d = new double[2];
boolean[] flags = new boolean[2];
String[] names = new String[2];
System.out.println(a[0] + " " + d[1] + " " + flags[0] + " " + names[1]);
System.out.println("Độ dài mảng a: " + a.length);Chú ý length là thuộc tính của mảng (không có dấu ngoặc), khác với String.length() là phương thức. Quên điều này là lỗi biên dịch rất hay gặp.
1.2. Khởi tạo bằng danh sách giá trị
Khi đã biết sẵn các giá trị, bạn dùng danh sách trong cặp ngoặc nhọn. Java tự suy ra độ dài.
int[] primes = {2, 3, 5, 7, 11};
String[] days = {"Hai", "Ba", "Tư"};
double[] prices = new double[]{12.5, 8.0, 99.9};
System.out.println(primes.length + " " + days.length + " " + prices.length);
System.out.println(primes[0] + " " + primes[primes.length - 1]);Dạng {...} gọn chỉ dùng được ngay tại dòng khai báo. Muốn gán lại một mảng mới cho biến đã có, phải viết đầy đủ primes = new int[]{1, 2, 3};.
1.3. Truy cập phần tử và lỗi vượt biên
Phần tử đầu tiên là a[0], phần tử cuối cùng là a[a.length - 1]. Truy cập chỉ số ngoài khoảng 0 .. length-1 làm Java ném ngoại lệ ArrayIndexOutOfBoundsException lúc chạy (khác với C, Java kiểm tra biên và không âm thầm ghi đè bộ nhớ).
int[] a = {10, 20, 30};
try {
System.out.println(a[3]);
} catch (ArrayIndexOutOfBoundsException e) {
System.out.println("Lỗi: " + e.getMessage());
}Cảnh báo: Lỗi "lệch một" (off-by-one) là lỗi mảng phổ biến nhất: viết
i <= a.lengththay vìi < a.length. Mảng 5 phần tử có chỉ số 0 đến 4, không cóa[5].
1.4. Duyệt mảng
Có hai cách duyệt chính. Dùng for với chỉ số khi bạn cần biết vị trí hoặc cần sửa phần tử; dùng for-each khi chỉ cần đọc từng giá trị.
int[] a = {4, 8, 15, 16, 23, 42};
int sum = 0;
for (int i = 0; i < a.length; i++) {
sum += a[i];
}
System.out.println("Tổng = " + sum);
int max = a[0];
for (int x : a) {
if (x > max) max = x;
}
System.out.println("Lớn nhất = " + max);Biến x trong for-each là bản sao của giá trị phần tử (với kiểu nguyên thủy), nên gán x = 0 không thay đổi mảng. Muốn sửa phần tử, dùng chỉ số.
int[] a = {1, 2, 3};
for (int x : a) {
x = x * 10; // chỉ sửa bản sao
}
System.out.println(a[0] + " " + a[1] + " " + a[2]);
for (int i = 0; i < a.length; i++) {
a[i] = a[i] * 10; // sửa thật trong mảng
}
System.out.println(a[0] + " " + a[1] + " " + a[2]);Mẹo: Với bài toán tìm giá trị lớn nhất hay nhỏ nhất, hãy khởi tạo biến kết quả bằng
a[0](không bằng0), vì mảng có thể chỉ toàn số âm.
1.5. Đọc mảng từ bàn phím
Trong bài tập chấm tự động, dữ liệu nhập thường có dạng "dòng đầu là n, dòng sau là n số". Mẫu đọc chuẩn:
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int min = a[0], pos = 0;
for (int i = 1; i < n; i++) {
if (a[i] < min) { min = a[i]; pos = i; }
}
System.out.println("min = " + min + " tại chỉ số " + pos);Chú ý bài tập thường đánh số vị trí từ 1 còn mảng Java từ 0; hãy đọc kỹ đề và cộng thêm 1 khi in nếu cần.
int[] a = new int[5]; a[5] = 1; // lỗi!
int[][] m = new int[3][2]; m[1][1] = 7;
Mảng là đối tượng nằm ở heap: biến chỉ giữ tham chiếu. Các ô liền kề, chỉ số từ 0 đến length-1; truy cập ngoài khoảng này ném ArrayIndexOutOfBoundsException lúc chạy.
Hình trên cho thấy biến mảng chỉ là một ô nhỏ trên stack, còn các phần tử nằm liền nhau trên heap. Hãy nhìn các chỉ số chạy từ 0 và độ dài ghi cạnh đối tượng mảng; đây chính là chủ đề của phần sau.
2. Mảng là đối tượng: tham chiếu, truyền tham số, sao chép
2.1. Biến mảng chỉ lưu địa chỉ
Trong Java, mảng là đối tượng. Lệnh int[] a = new int[3] tạo đối tượng mảng trên heap, còn a chỉ là một biến tham chiếu (reference) trên stack, giữ địa chỉ của đối tượng đó. Hệ quả quan trọng: gán b = a không sao chép mảng, mà chỉ sao chép địa chỉ, khiến a và b cùng trỏ vào một mảng.
int[] a = {1, 2, 3};
int[] b = a; // b và a cùng trỏ một mảng
b[0] = 99;
System.out.println(a[0] + " " + b[0]);
System.out.println(a == b);Toán tử == trên mảng so sánh địa chỉ, không so sánh nội dung. Hai mảng riêng biệt có cùng nội dung vẫn cho == là false; muốn so sánh nội dung dùng Arrays.equals (phần 4).
| Biểu thức | Ý nghĩa | Kết quả với a = {1,2}, b = a, c = {1,2} |
|---|---|---|
a == b |
Cùng một đối tượng? | true |
a == c |
Cùng một đối tượng? | false |
Arrays.equals(a, c) |
Cùng nội dung? | true |
a.equals(c) |
Với mảng chỉ là == |
false |
2.2. Truyền mảng vào phương thức
Java luôn truyền giá trị. Với mảng, giá trị được truyền là địa chỉ, nên phương thức nhận một "bản sao địa chỉ" nhưng vẫn trỏ cùng một mảng. Vì vậy phương thức có thể sửa nội dung mảng của người gọi, nhưng nếu nó gán một mảng mới cho tham số thì người gọi không bị ảnh hưởng.
public class Main {
static void doubleAll(int[] arr) {
for (int i = 0; i < arr.length; i++) arr[i] *= 2; // sửa mảng thật
}
static void replace(int[] arr) {
arr = new int[]{0, 0, 0}; // chỉ đổi biến cục bộ
}
public static void main(String[] args) {
int[] a = {1, 2, 3};
doubleAll(a);
System.out.println(a[0] + " " + a[1] + " " + a[2]);
replace(a);
System.out.println(a[0] + " " + a[1] + " " + a[2]);
}
}Lưu ý: Phương thức tĩnh được trình bày kỹ ở Buổi 4. Ở đây bạn chỉ cần nhớ: truyền mảng là truyền địa chỉ, nên sửa phần tử bên trong phương thức là sửa mảng gốc.
2.3. Sao chép mảng đúng cách
Muốn có một mảng độc lập, bạn phải tạo mảng mới và chép từng phần tử. Có ba cách thường dùng: vòng for, System.arraycopy và Arrays.copyOf (phần 4). Phương thức clone() của mảng cũng tạo một bản sao nông.
int[] a = {5, 6, 7};
int[] b = new int[a.length];
for (int i = 0; i < a.length; i++) b[i] = a[i];
int[] c = new int[a.length];
System.arraycopy(a, 0, c, 0, a.length); // nguồn, vị trí đầu, đích, vị trí đầu, số phần tử
int[] d = a.clone();
a[0] = -1;
System.out.println(a[0] + " " + b[0] + " " + c[0] + " " + d[0]);Cảnh báo: Với mảng đối tượng (như
String[]hayint[][]), sao chép nông chỉ chép các địa chỉ bên trong. Mảng mới và mảng cũ vẫn dùng chung các đối tượng phần tử. Vớiint[][]bạn phải sao chép từng hàng.
2.4. Hoán vị và đảo mảng tại chỗ
Do mảng sửa được tại chỗ, nhiều thuật toán không cần mảng phụ. Đảo ngược là ví dụ điển hình: dùng hai chỉ số i ở đầu và j ở cuối, hoán đổi rồi tiến vào giữa.
int[] a = {1, 2, 3, 4, 5};
for (int i = 0, j = a.length - 1; i < j; i++, j--) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
System.out.println(Arrays.toString(a));Kỹ thuật hai con trỏ (two-pointer) này sẽ còn xuất hiện ở tìm kiếm và sắp xếp. Đối với bài xoay mảng sang phải k bước, bạn có thể dùng ba lần đảo: đảo toàn bộ, đảo k phần tử đầu, đảo phần còn lại. Nhớ lấy k % n trước vì k có thể lớn hơn độ dài mảng.
public class Main {
static void reverse(int[] a, int l, int r) {
while (l < r) { int t = a[l]; a[l++] = a[r]; a[r--] = t; }
}
public static void main(String[] args) {
int[] a = {1, 2, 3, 4, 5, 6, 7};
int k = 10 % a.length; // k có thể lớn hơn n
reverse(a, 0, a.length - 1);
reverse(a, 0, k - 1);
reverse(a, k, a.length - 1);
System.out.println(Arrays.toString(a));
}
}Vừa học xong mảng một chiều và bản chất tham chiếu của mảng. Hãy làm các bài sau để luyện duyệt mảng, tìm giá trị cực trị kèm vị trí, đảo và xoay mảng tại chỗ.
3. Mảng hai chiều và mảng răng cưa
3.1. Mảng hai chiều là mảng của các mảng
Nhiều dữ liệu có dạng bảng: bảng điểm (sinh viên × môn học), sơ đồ ghế trong rạp, bàn cờ, ma trận trong đại số. Java biểu diễn bảng bằng mảng hai chiều, thực chất là mảng mà mỗi phần tử lại là một mảng một chiều. Vì thế int[][] là một đối tượng chứa các tham chiếu tới các đối tượng int[] (các hàng).
int[][] m = new int[3][4]; // 3 hàng, 4 cột, toàn số 0
m[1][2] = 7;
System.out.println(m.length); // số hàng
System.out.println(m[0].length); // số cột của hàng 0
System.out.println(m[1][2]);Quy ước: m.length là số hàng, m[i].length là số cột của hàng i, và phần tử ở hàng i cột j là m[i][j]. Bạn cũng có thể khởi tạo bằng danh sách lồng nhau.
int[][] grid = {
{1, 2, 3},
{4, 5, 6}
};
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
System.out.print(grid[i][j] + " ");
}
System.out.println();
}Hãy dùng grid[i].length thay vì gõ cứng số cột: cách này vẫn đúng cho cả mảng răng cưa ở mục sau. Để duyệt đơn giản bạn cũng có thể dùng for-each lồng nhau.
int[][] grade = {{8, 9}, {7, 6}, {10, 5}};
int total = 0;
for (int[] row : grade) {
for (int v : row) {
total += v;
}
}
System.out.println("Tổng = " + total);3.2. Các phép xử lý ma trận thường gặp
Ba kiểu bài ma trận xuất hiện lặp đi lặp lại: duyệt theo hàng, duyệt theo cột và duyệt đường chéo. Điểm mấu chốt là chọn đúng vòng lặp ngoài. Tổng từng hàng: vòng ngoài là hàng, cộng dồn các cột. Tổng từng cột: đổi vai trò hai vòng lặp. Đường chéo chính có i == j, đường chéo phụ của ma trận vuông n × n có i + j == n - 1.
| Yêu cầu | Cách duyệt | Công thức chỉ số |
|---|---|---|
| Tổng từng hàng | vòng ngoài theo i, trong theo j |
m[i][j] |
| Tổng từng cột | vòng ngoài theo j, trong theo i |
m[i][j] |
| Đường chéo chính | một vòng i |
m[i][i] |
| Đường chéo phụ | một vòng i |
m[i][n - 1 - i] |
| Chuyển vị | tạo mảng c × r |
t[j][i] = m[i][j] |
int[][] m = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int n = m.length;
int main = 0, anti = 0;
for (int i = 0; i < n; i++) {
main += m[i][i];
anti += m[i][n - 1 - i];
}
System.out.println("Chéo chính = " + main + ", chéo phụ = " + anti);
for (int i = 0; i < n; i++) {
int rowSum = 0;
for (int j = 0; j < n; j++) rowSum += m[i][j];
System.out.println("Hàng " + i + ": " + rowSum);
}Phép chuyển vị biến ma trận R × C thành C × R bằng cách đổi chỗ chỉ số. Chú ý kích thước mảng mới bị đảo.
int[][] m = {{1, 2, 3}, {4, 5, 6}};
int r = m.length, c = m[0].length;
int[][] t = new int[c][r];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
t[j][i] = m[i][j];
}
}
System.out.println(Arrays.deepToString(t));Với xoay ma trận vuông 90 độ theo chiều kim đồng hồ, phần tử ở m[i][j] chuyển tới r[j][n - 1 - i]. Bạn có thể dùng mảng phụ cho dễ hiểu, hoặc chuyển vị rồi đảo từng hàng để xoay mà không cần công thức nào khác. Còn bài duyệt xoắn ốc đòi hỏi bốn biên (top, bottom, left, right) thu hẹp dần sau mỗi vòng; hãy vẽ ma trận nhỏ 3 × 4 ra giấy để theo dõi trước khi viết code.
int[][] m = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int n = m.length;
int[][] r = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
r[j][n - 1 - i] = m[i][j]; // xoay 90 độ theo chiều kim đồng hồ
}
}
for (int[] row : r) System.out.println(Arrays.toString(row));Mẹo: Khi gặp bài ma trận, hãy tự hỏi: "vòng lặp nào ở ngoài?" và kiểm tra bằng ma trận
2 × 3(không vuông). Nhiều lỗi ẩn chỉ lộ ra khi số hàng khác số cột, vì lúc đó nhầmlengthcủa hàng và cột sẽ gâyArrayIndexOutOfBoundsException.
3.3. Mảng răng cưa (jagged array)
Vì mỗi hàng của int[][] là một mảng độc lập, các hàng không bắt buộc cùng độ dài. Mảng như vậy gọi là mảng răng cưa (jagged). Bạn chỉ cấp phát số hàng trước, rồi tạo từng hàng với độ dài riêng. Ví dụ tam giác Pascal hay danh sách môn học của từng sinh viên (mỗi người học số môn khác nhau).
int[][] jag = new int[3][]; // 3 hàng, chưa tạo hàng nào
jag[0] = new int[]{1};
jag[1] = new int[]{2, 3};
jag[2] = new int[]{4, 5, 6};
for (int i = 0; i < jag.length; i++) {
int sum = 0;
for (int v : jag[i]) sum += v;
System.out.println("Dòng " + i + " có " + jag[i].length + " phần tử, tổng " + sum);
}Nếu quên tạo hàng mà truy cập jag[0][0], bạn gặp NullPointerException vì jag[0] đang là null. In nhanh toàn bộ mảng nhiều chiều bằng Arrays.deepToString.
int n = 5;
int[][] pascal = new int[n][];
for (int i = 0; i < n; i++) {
pascal[i] = new int[i + 1];
pascal[i][0] = pascal[i][i] = 1;
for (int j = 1; j < i; j++) {
pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];
}
}
System.out.println(Arrays.deepToString(pascal));Ví dụ thực tế: Một ứng dụng quản lý lớp tín chỉ lưu điểm các bài kiểm tra của từng sinh viên: mỗi sinh viên nộp số bài khác nhau. Mảng răng cưa
double[][] marksphù hợp hơn ma trận chữ nhật vì không phải độn số 0 giả vào các ô không có dữ liệu.
Vừa học xong mảng hai chiều và mảng răng cưa, hãy làm các bài sau để quen với duyệt theo hàng, cột, chuyển vị, xoay và xoắn ốc, và để thấy rõ length của từng hàng.
4. Lớp tiện ích Arrays
Thư viện java.util.Arrays cung cấp các phương thức tĩnh xử lý mảng. Bạn không cần cài đặt lại những thao tác phổ biến: in, sắp xếp, điền giá trị, sao chép, so sánh, tìm nhị phân. Biết dùng thành thạo giúp code ngắn gọn, ít lỗi hơn và thường nhanh hơn tự viết. Các ví dụ dưới đây đã có sẵn import java.util.*.
4.1. In mảng: toString và deepToString
In trực tiếp một mảng bằng System.out.println(a) chỉ cho ra chuỗi kiểu [I@1b6d3586 (kiểu và mã băm), vô ích. Hãy dùng Arrays.toString cho mảng một chiều và Arrays.deepToString cho mảng nhiều chiều.
int[] a = {3, 1, 2};
String[] s = {"an", "bình"};
int[][] m = {{1, 2}, {3, 4}};
System.out.println(Arrays.toString(a));
System.out.println(Arrays.toString(s));
System.out.println(Arrays.deepToString(m));
System.out.println(Arrays.toString(m[1]));4.2. Sắp xếp: Arrays.sort
Arrays.sort(a) sắp xếp tăng dần tại chỗ. Với mảng kiểu nguyên thủy, Java dùng thuật toán Dual-Pivot Quicksort rất nhanh, thời gian trung bình O(n log n). Có thể sắp xếp một đoạn bằng Arrays.sort(a, from, to) (chỉ số to không bao gồm). Với mảng đối tượng như String[] hoặc Integer[], dùng sắp xếp ổn định (TimSort) và cho phép truyền bộ so sánh (Comparator).
int[] a = {5, 2, 9, 1, 7};
Arrays.sort(a);
System.out.println(Arrays.toString(a));
int[] b = {9, 8, 7, 6, 5, 4};
Arrays.sort(b, 1, 4); // chỉ sắp xếp chỉ số 1..3
System.out.println(Arrays.toString(b));
String[] names = {"Lan", "An", "Minh"};
Arrays.sort(names);
System.out.println(Arrays.toString(names));Muốn sắp xếp giảm dần hay theo tiêu chí riêng, bạn phải dùng mảng đối tượng (Integer[], không phải int[]) rồi đưa vào một Comparator. Kiểu nguyên thủy không dùng được Comparator.
Integer[] a = {5, 2, 9, 1, 7};
Arrays.sort(a, Collections.reverseOrder());
System.out.println(Arrays.toString(a));
String[] w = {"banana", "fig", "apple", "kiwi", "date"};
Arrays.sort(w, (x, y) -> x.length() != y.length()
? Integer.compare(x.length(), y.length())
: x.compareTo(y));
System.out.println(Arrays.toString(w));Biểu thức (x, y) -> ... là lambda sẽ được học kỹ ở Buổi 10; bây giờ chỉ cần hiểu nó cho biết "so sánh hai phần tử x, y thế nào". Trả về số âm nghĩa là x đứng trước y, số dương nghĩa là x đứng sau, 0 là bằng nhau. Ở ví dụ trên chuỗi ngắn đứng trước, cùng độ dài thì theo thứ tự chữ cái.
Lưu ý: Dùng
Integer.compare(x, y)thay vìx - ytrong comparator, vì phép trừ có thể tràn số khixrất lớn vàyrất âm, làm kết quả so sánh sai.
4.3. Điền và sao chép: fill, copyOf, copyOfRange
Arrays.fill(a, v) gán mọi ô bằng v; có dạng điền một đoạn fill(a, from, to, v). Arrays.copyOf(a, newLength) tạo mảng mới với độ dài mong muốn: nếu dài hơn thì thêm giá trị mặc định (0), nếu ngắn hơn thì cắt bớt. Arrays.copyOfRange(a, from, to) sao chép đoạn [from, to).
int[] a = new int[5];
Arrays.fill(a, 7);
System.out.println(Arrays.toString(a));
int[] src = {1, 2, 3, 4, 5};
int[] longer = Arrays.copyOf(src, 7);
int[] shorter = Arrays.copyOf(src, 3);
int[] part = Arrays.copyOfRange(src, 1, 4);
System.out.println(Arrays.toString(longer));
System.out.println(Arrays.toString(shorter));
System.out.println(Arrays.toString(part));Vì mảng có độ dài cố định, copyOf là cách chuẩn để "mở rộng" mảng: tạo mảng lớn hơn rồi chép phần tử cũ sang. Lớp ArrayList (Buổi 7) làm việc này tự động cho bạn.
4.4. So sánh: equals và deepEquals
Như đã thấy, == so sánh địa chỉ. Arrays.equals(a, b) so sánh độ dài và từng phần tử; với mảng hai chiều dùng Arrays.deepEquals.
int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
System.out.println(a == b);
System.out.println(Arrays.equals(a, b));
int[][] x = {{1}, {2}};
int[][] y = {{1}, {2}};
System.out.println(Arrays.equals(x, y));
System.out.println(Arrays.deepEquals(x, y));Dòng thứ ba cho false vì Arrays.equals chỉ so sánh các phần tử ở mức đầu (là các hàng, tức địa chỉ khác nhau), còn deepEquals đi sâu vào từng hàng.
4.5. Tìm nhị phân sẵn có: binarySearch
Arrays.binarySearch(a, key) tìm key trong mảng đã sắp xếp tăng dần. Nếu tìm thấy, trả về chỉ số; nếu không, trả về -(vị trí chèn) - 1, tức một số âm. Gọi trên mảng chưa sắp xếp cho kết quả không xác định.
int[] a = {2, 4, 6, 8, 10};
System.out.println(Arrays.binarySearch(a, 8));
int r = Arrays.binarySearch(a, 5);
System.out.println(r);
System.out.println("Chèn 5 vào chỉ số " + (-r - 1));4.6. Tổng hợp các phương thức
| Phương thức | Tác dụng | Ghi chú |
|---|---|---|
Arrays.toString(a) |
in mảng một chiều | deepToString cho nhiều chiều |
Arrays.sort(a) |
sắp xếp tăng dần tại chỗ | O(n log n), thêm Comparator cho mảng đối tượng |
Arrays.fill(a, v) |
gán mọi ô bằng v |
có dạng đoạn [from, to) |
Arrays.copyOf(a, n) |
mảng mới độ dài n |
thiếu thì thêm 0, thừa thì cắt |
Arrays.copyOfRange(a, i, j) |
sao chép đoạn [i, j) |
j có thể vượt độ dài, phần dư là 0 |
Arrays.equals(a, b) |
so sánh nội dung | deepEquals cho nhiều chiều |
Arrays.binarySearch(a, k) |
tìm nhị phân | mảng phải đã sắp xếp; trả số âm nếu thiếu |
Vừa học xong lớp Arrays, hãy làm các bài sau để thực hành in, cắt mảng con và sắp xếp bằng Comparator theo yêu cầu riêng.
5. Tìm kiếm tuần tự và tìm kiếm nhị phân
Tìm kiếm (search) là bài toán: cho mảng a và giá trị x, hãy cho biết x có trong mảng không, nếu có thì ở vị trí nào. Đây là thao tác nền tảng của mọi hệ thống: tra mã sinh viên, tìm sản phẩm theo mã vạch, kiểm tra tên đăng nhập đã tồn tại. Chọn thuật toán nào phụ thuộc vào việc mảng đã được sắp xếp hay chưa.
5.1. Tìm kiếm tuần tự (linear search)
Ý tưởng đơn giản nhất: duyệt từ đầu, so từng phần tử với x, gặp là dừng. Thuật toán chạy được trên mọi mảng (không cần sắp xếp). Trong trường hợp xấu nhất, bạn phải xem cả n phần tử, nên thời gian là O(n).
static int linearSearch(int[] a, int x) {
for (int i = 0; i < a.length; i++) {
if (a[i] == x) return i; // gặp đầu tiên thì trả về ngay
}
return -1; // quy ước: -1 nghĩa là không có
}Đoạn trên chỉ là hàm, chưa có main để chạy. Hãy xem phiên bản đầy đủ và đếm số phép so sánh để thấy "xấu nhất" xảy ra khi phần tử nằm ở cuối hoặc không có.
public class Main {
static int steps = 0;
static int linearSearch(int[] a, int x) {
for (int i = 0; i < a.length; i++) {
steps++;
if (a[i] == x) return i;
}
return -1;
}
public static void main(String[] args) {
int[] a = {7, 3, 9, 4, 1, 8};
System.out.println(linearSearch(a, 9) + " sau " + steps + " bước");
steps = 0;
System.out.println(linearSearch(a, 5) + " sau " + steps + " bước");
}
}Có hai điểm cần cẩn thận. Thứ nhất, quy ước giá trị trả về khi không tìm thấy (-1 vì chỉ số hợp lệ không bao giờ âm). Thứ hai, nếu có nhiều phần tử bằng x, thuật toán trả về vị trí đầu tiên; muốn vị trí cuối hoặc đếm tất cả, bạn không dừng sớm mà duyệt hết.
5.2. Tìm kiếm nhị phân (binary search)
Khi mảng đã sắp xếp tăng dần, bạn có thể làm tốt hơn nhiều. Giống như tra từ điển: mở giữa cuốn, nếu từ cần tìm đứng trước thì bỏ nửa sau, ngược lại bỏ nửa trước, rồi lặp lại trên nửa còn lại. Mỗi bước loại bỏ một nửa không gian tìm kiếm nên chỉ cần khoảng log2(n) bước. Với một triệu phần tử, tìm tuần tự có thể cần một triệu bước còn nhị phân chỉ khoảng 20 bước.
Thuật toán giữ hai chỉ số lo và hi của đoạn còn khả năng chứa x. Mỗi vòng tính mid, so a[mid] với x rồi thu hẹp đoạn.
public class Main {
static int binarySearch(int[] a, int x) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // tránh tràn số so với (lo + hi) / 2
if (a[mid] == x) return mid;
if (a[mid] < x) lo = mid + 1; // bỏ nửa trái
else hi = mid - 1; // bỏ nửa phải
}
return -1;
}
public static void main(String[] args) {
int[] a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
System.out.println(binarySearch(a, 23));
System.out.println(binarySearch(a, 50));
}
}Cảnh báo: Tìm nhị phân chỉ đúng khi mảng đã sắp xếp. Nếu mảng lộn xộn, thuật toán có thể bỏ nhầm nửa chứa đáp án mà không báo lỗi. Ngoài ra điều kiện vòng lặp phải là
lo <= hi(không phảilo < hi), nếu không bạn sẽ bỏ sót trường hợp đoạn chỉ còn một phần tử.
Hãy theo dõi từng bước để hiểu cơ chế. Ví dụ dưới in lo, hi, mid ở mỗi vòng khi tìm số 23.
int[] a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int x = 23, lo = 0, hi = a.length - 1, round = 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
System.out.println("Vòng " + round++ + ": lo=" + lo + " hi=" + hi + " mid=" + mid + " a[mid]=" + a[mid]);
if (a[mid] == x) { System.out.println("Thấy ở chỉ số " + mid); break; }
if (a[mid] < x) lo = mid + 1; else hi = mid - 1;
}5.3. So sánh hai thuật toán
| Tiêu chí | Tuần tự | Nhị phân |
|---|---|---|
| Yêu cầu mảng | không | phải sắp xếp |
| Thời gian xấu nhất | O(n) |
O(log n) |
| Mảng nhỏ hoặc tìm một lần | phù hợp | thừa công sắp xếp |
| Tìm rất nhiều lần trên mảng cố định | chậm | rất nhanh |
| Kết quả khi có phần tử lặp | vị trí đầu tiên | một trong các vị trí bằng |
Quy tắc chọn: nếu chỉ tìm một vài lần trên mảng chưa sắp xếp, cứ tìm tuần tự. Nếu cần trả lời hàng nghìn truy vấn trên cùng một mảng, hãy sắp xếp một lần (O(n log n)) rồi tìm nhị phân cho mỗi truy vấn (O(log n)).
5.4. Kỹ thuật hai con trỏ trên mảng đã sắp xếp
Khi mảng đã sắp xếp, còn một kỹ thuật tận dụng thứ tự: hai con trỏ. Bài "tìm hai số có tổng bằng S" đặt i ở đầu, j ở cuối. Nếu a[i] + a[j] nhỏ hơn S thì tăng i để tổng lớn lên; nếu lớn hơn thì giảm j. Mỗi bước loại một phần tử, tổng cộng O(n), rẻ hơn hẳn hai vòng lặp lồng O(n^2).
int[] a = {1, 3, 4, 6, 8, 11};
int s = 10, i = 0, j = a.length - 1;
while (i < j) {
int sum = a[i] + a[j];
if (sum == s) { System.out.println("Cặp chỉ số " + i + " và " + j); break; }
if (sum < s) i++; else j--;
}Mẹo: Khi một bài cho mảng "đã sắp xếp", hãy lập tức nghĩ đến nhị phân hoặc hai con trỏ. Đề bài cố tình cho thông tin đó để bạn dùng.
Vừa học xong tìm kiếm, hãy làm các bài sau để cài đặt tìm tuần tự, tìm nhị phân cho nhiều truy vấn và kỹ thuật hai con trỏ trên mảng đã sắp xếp.
6. Sắp xếp: chọn, nổi bọt, chèn
Sắp xếp (sorting) là sắp các phần tử theo thứ tự (tăng hoặc giảm). Sắp xếp là nền tảng của tìm kiếm nhị phân, xếp hạng điểm thi, loại trùng, thống kê. Trong thực tế bạn gần như luôn dùng Arrays.sort, nhưng việc tự cài đặt ba thuật toán đơn giản giúp bạn luyện tư duy thuật toán, hiểu độ phức tạp và nắm cách thao tác phần tử mảng tại chỗ. Cả ba thuật toán dưới đây đều có độ phức tạp trung bình và xấu nhất O(n^2), chỉ phù hợp mảng nhỏ.
Phép hoán đổi hai phần tử xuất hiện ở mọi thuật toán, nên ta viết một lần.
static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}6.1. Sắp xếp chọn (selection sort)
Ý tưởng: ở lượt thứ i, chọn phần tử nhỏ nhất trong đoạn chưa sắp xếp a[i..n-1] rồi đổi chỗ nó với a[i]. Sau lượt i, a[0..i] đã đúng vị trí cuối cùng. Thuật toán thực hiện ít phép hoán đổi (tối đa n - 1) nhưng luôn so sánh khoảng n^2 / 2 lần, dù mảng gần như đã sắp xếp.
public class Main {
static void selectionSort(int[] a) {
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 tmp = a[i]; a[i] = a[min]; a[min] = tmp;
System.out.println("Lượt " + i + ": " + Arrays.toString(a));
}
}
public static void main(String[] args) {
selectionSort(new int[]{29, 10, 14, 37, 13});
}
}6.2. Sắp xếp nổi bọt (bubble sort)
Ý tưởng: lần lượt so sánh hai phần tử kề nhau và đổi chỗ nếu sai thứ tự. Sau mỗi lượt, phần tử lớn nhất còn lại "nổi" về cuối như bọt khí. Nếu một lượt không có hoán đổi nào, mảng đã xếp xong và có thể dừng sớm; đây là tối ưu đáng giá, giúp mảng gần xếp sẵn chạy trong O(n).
Bubble sort từng bước
Vàng: đang so sánh · Đỏ: hoán đổi · Xanh lục: đã xongĐộ phức tạp O(n²). Thử mảng thứ 4 (gần đúng thứ tự): lượt không hoán đổi giúp dừng sớm.
Mô phỏng trên cho bạn chạy từng bước hoặc tự động: hãy quan sát cặp đang so sánh và phần tử lớn nhất tiến dần về cuối sau mỗi lượt. Thử lại với mảng đã sắp xếp để thấy cơ chế dừng sớm.
public class Main {
static int bubbleSort(int[] a) {
int swaps = 0;
for (int pass = 0; pass < a.length - 1; pass++) {
boolean swapped = false;
for (int j = 0; j < a.length - 1 - pass; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp;
swapped = true;
swaps++;
}
}
if (!swapped) break; // không đổi chỗ -> đã xong
}
return swaps;
}
public static void main(String[] args) {
int[] a = {5, 1, 4, 2, 8};
int s = bubbleSort(a);
System.out.println(Arrays.toString(a) + " sau " + s + " lần đổi chỗ");
}
}Lưu ý giới hạn vòng trong là a.length - 1 - pass: sau pass lượt, pass phần tử cuối đã đúng chỗ nên không cần so nữa.
6.3. Sắp xếp chèn (insertion sort)
Ý tưởng giống cách xếp bài trên tay: lấy từng lá bài key = a[i] và chèn vào đúng vị trí trong phần đầu đã sắp xếp a[0..i-1] bằng cách dịch các phần tử lớn hơn sang phải một ô. Với mảng gần như đã sắp xếp, sắp xếp chèn rất nhanh (gần O(n)), vì vậy nó là lựa chọn tốt cho dữ liệu nhỏ hoặc gần xếp sẵn, và là thành phần của thuật toán TimSort trong Java.
public class Main {
static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j]; // dịch sang phải
j--;
}
a[j + 1] = key;
System.out.println("Chèn " + key + ": " + Arrays.toString(a));
}
}
public static void main(String[] args) {
insertionSort(new int[]{12, 11, 13, 5, 6});
}
}6.4. So sánh ba thuật toán và Arrays.sort
| Thuật toán | So sánh (xấu nhất) | Hoán đổi / dịch chuyển | Dừng sớm khi đã xếp | Ổn định |
|---|---|---|---|---|
| Chọn | O(n^2) |
ít, tối đa n - 1 |
không | không |
| Nổi bọt | O(n^2) |
nhiều | có, nếu thêm cờ | có |
| Chèn | O(n^2) |
nhiều dịch chuyển | tự nhiên nhanh | có |
Arrays.sort (nguyên thủy) |
O(n log n) |
tối ưu | không cần | không đảm bảo |
Arrays.sort (đối tượng) |
O(n log n) |
tối ưu | tốt với dữ liệu gần xếp | có |
"Ổn định" nghĩa là hai phần tử bằng nhau giữ nguyên thứ tự tương đối ban đầu; điều này quan trọng khi sắp theo một khóa rồi theo khóa khác (xếp theo điểm, các bạn cùng điểm vẫn theo thứ tự tên đã có).
Một kiểm chứng đơn giản: sắp xếp cùng dữ liệu bằng tự cài đặt và bằng Arrays.sort rồi dùng Arrays.equals so sánh, đó cũng là cách kiểm thử thuật toán tự viết rất hữu ích.
public class Main {
static void insertionSort(int[] a) {
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;
}
}
public static void main(String[] args) {
int[] mine = {9, -3, 5, 0, 5, 2, -8, 7};
int[] ref = mine.clone();
insertionSort(mine);
Arrays.sort(ref);
System.out.println(Arrays.toString(mine));
System.out.println("Khớp với Arrays.sort: " + Arrays.equals(mine, ref));
}
}Lưu ý: Trong bài thi hay công việc thực tế, hãy dùng
Arrays.sorttrừ khi đề bài yêu cầu tự cài đặt. Nó nhanh hơn nhiều khinlớn: sắp xếp nổi bọt một triệu phần tử cần cỡ nghìn tỷ phép so sánh, cònArrays.sortchỉ cỡ hai chục triệu.
7. Độ phức tạp sơ lược và tổng kết
7.1. Đo "chi phí" của thuật toán
Hai chương trình cùng giải đúng một bài có thể chênh nhau hàng nghìn lần về tốc độ khi dữ liệu lớn. Để so sánh mà không phụ thuộc vào máy tính, ta đếm số phép toán cơ bản theo kích thước dữ liệu n và ghi bằng ký hiệu O lớn (Big-O), chỉ giữ lại thành phần tăng nhanh nhất và bỏ hằng số. Ví dụ 3n^2 + 5n + 7 được viết là O(n^2).
| Độ phức tạp | Tên gọi | Ví dụ trong buổi này | Với n = 1 000 000 (cỡ) |
|---|---|---|---|
O(1) |
hằng số | truy cập a[i] |
1 |
O(log n) |
logarit | tìm kiếm nhị phân | 20 |
O(n) |
tuyến tính | tìm tuần tự, duyệt tìm max | 1 triệu |
O(n log n) |
tuyến tính-logarit | Arrays.sort |
20 triệu |
O(n^2) |
bình phương | chọn, nổi bọt, chèn; hai vòng for lồng | 1 nghìn tỷ |
Cách ước lượng nhanh: một vòng lặp chạy n lần là O(n); hai vòng lồng nhau đều chạy n lần là O(n^2); một vòng mà mỗi bước giảm một nửa dữ liệu là O(log n). Máy tính hiện đại làm khoảng 10^8 phép toán đơn giản mỗi giây, nên với giới hạn thời gian vài giây và n = 10^5, thuật toán O(n^2) (khoảng 10^10) sẽ quá chậm còn O(n log n) thì thoải mái.
7.2. Từ O(n^2) xuống O(n): ví dụ dãy con liên tiếp có tổng lớn nhất
Bài "dãy con liên tiếp có tổng lớn nhất" minh họa rõ tác dụng của việc nghĩ lại thuật toán. Cách thô: thử mọi đoạn [i, j] và cộng, O(n^2) nếu cộng dồn thông minh. Cách của Kadane chỉ duyệt một lần: giữ cur là tổng lớn nhất của đoạn kết thúc tại vị trí hiện tại, nếu cur âm thì bỏ nó và bắt đầu lại.
int[] a = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int best = a[0], cur = a[0];
for (int i = 1; i < a.length; i++) {
cur = Math.max(a[i], cur + a[i]); // nối tiếp hoặc bắt đầu mới
best = Math.max(best, cur);
}
System.out.println("Tổng lớn nhất = " + best);Điểm cần nhớ: trước khi viết code hãy hỏi "có thể giải bằng một lượt duyệt không?" và "dữ liệu có thứ tự đặc biệt (đã sắp xếp) để tận dụng không?".
7.3. Sắp xếp trộn và đếm nghịch thế (xem thêm)
Sắp xếp trộn (merge sort) chia mảng làm hai nửa, sắp xếp từng nửa rồi trộn hai nửa đã sắp xếp thành một. Phép trộn hai mảng đã sắp xếp dùng hai con trỏ và chạy O(n), tổng cộng O(n log n). Đây là nền tảng của bài toán đếm cặp nghịch thế (i < j nhưng a[i] > a[j]): trong lúc trộn, mỗi lần lấy phần tử từ nửa phải trước, ta biết nó nghịch thế với toàn bộ phần tử còn lại của nửa trái. Bài toán này không bắt buộc, dành cho bạn muốn thử sức ở nhóm bài khó.
int[] a = {1, 4, 7};
int[] b = {2, 3, 9, 10};
int[] r = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length) {
r[k++] = a[i] <= b[j] ? a[i++] : b[j++];
}
while (i < a.length) r[k++] = a[i++];
while (j < b.length) r[k++] = b[j++];
System.out.println(Arrays.toString(r));Vừa học xong sắp xếp và độ phức tạp, hãy làm các bài sau để tự cài đặt sắp xếp, trộn hai mảng đã sắp xếp và nhận ra khi nào cần thuật toán nhanh hơn O(n^2).
Sai lầm thường gặp
| Sai lầm | Hậu quả | Cách đúng |
|---|---|---|
Duyệt với i <= a.length |
ArrayIndexOutOfBoundsException |
Dùng i < a.length; chỉ số cuối là length - 1 |
Viết b = a để sao chép mảng |
a và b cùng trỏ một mảng, sửa cái này đổi cái kia |
a.clone(), Arrays.copyOf, hoặc vòng for |
So sánh mảng bằng == hoặc equals |
Luôn false với hai mảng khác đối tượng |
Arrays.equals / Arrays.deepEquals |
System.out.println(a) cho mảng |
In ra mã kiểu [I@... |
Arrays.toString / Arrays.deepToString |
Quên [j] hoặc nhầm length của hàng và cột |
Lỗi biên hoặc kết quả sai trên ma trận không vuông | Dùng m.length cho hàng, m[i].length cho cột |
| Tìm nhị phân trên mảng chưa sắp xếp | Kết quả sai mà không báo lỗi | Sắp xếp trước, hoặc dùng tìm tuần tự |
Sắp xếp giảm dần int[] bằng Comparator |
Lỗi biên dịch | Dùng Integer[] hoặc sắp xếp tăng rồi đảo |
Comparator trả về x - y |
Có thể tràn số, thứ tự sai | Dùng Integer.compare(x, y) |
Khởi tạo max = 0 khi mọi số đều âm |
Kết quả sai | Khởi tạo bằng a[0] |
Quên lấy k % n khi xoay mảng |
Chỉ số vượt biên | k = k % n trước khi xoay |
Tóm tắt
- Mảng lưu các phần tử cùng kiểu, độ dài cố định, chỉ số từ
0;lengthlà thuộc tính, không có ngoặc. - Mảng là đối tượng trên heap; biến mảng là tham chiếu.
b = akhông sao chép; truyền mảng vào phương thức cho phép sửa mảng gốc. - Mảng hai chiều là mảng của các mảng; hàng có thể khác độ dài (răng cưa).
m.lengthlà số hàng,m[i].lengthlà số cột. Arrayscung cấptoString,sort,fill,copyOf,copyOfRange,equals,binarySearch; dùng Comparator trên mảng đối tượng.- Tìm tuần tự
O(n)dùng cho mọi mảng; tìm nhị phânO(log n)chỉ dùng cho mảng đã sắp xếp; hai con trỏ cho nhiều bài trên mảng đã sắp xếp. - Sắp xếp chọn, nổi bọt, chèn đều
O(n^2);Arrays.sortlàO(n log n)và nên là lựa chọn mặc định. - Ước lượng bằng Big-O trước khi code: chọn thuật toán sao cho số phép toán vừa với giới hạn thời gian.