1. Sắp Xếp Chèn (Insertion Sort) - O(n²)
Sắp xếp chèn hoạt động dựa trên ý tưởng chia mảng ban đầu thành hai phần: một phần đã được sắp xếp và một phần chưa được sắp xếp. Thuật toán sẽ lấy lần lượt từng phần tử từ phần chưa sắp xếp và chèn nó vào đúng vị trí trong phần đã sắp xếp.
public class InsertSorter {
public static void main(String[] args) {
int[] numbers = {101, 34, 119, 1, -1, 89};
System.out.println("Trước khi sắp xếp: " + Arrays.toString(numbers));
insertionSort(numbers);
System.out.println("Sau khi sắp xếp: " + Arrays.toString(numbers));
}
public static void insertionSort(int[] arr) {
int currentValue, insertIndex;
for (int i = 1; i < arr.length; i++) {
currentValue = arr[i];
insertIndex = i - 1;
while (insertIndex >= 0 && currentValue < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
if (insertIndex + 1 != i) {
arr[insertIndex + 1] = currentValue;
}
}
}
}
2. Sắp Xếp Shell (Shell Sort) - O(n log n)
Sắp xếp Shell là một cải tiến của sắp xếp chèn, còn được gọi là "sắp xếp tăng dần thu hẹp". Nó so sánh và hoán đổi các phần tử cách xa nhau bằng cách chia mảng thành các nhóm con dựa trên một khoảng cách (gap) nhất định.
Vấn đề của sắp xếp chèn: Khi các phần tử nhỏ nằm ở cuối mảng, số lần dịch chuyển sẽ rất lớn, làm giảm hiệu suất.
public class ShellSorter {
public static void main(String[] args) {
int[] data = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
System.out.println("Trước: " + Arrays.toString(data));
shellSort(data);
System.out.println("Sau: " + Arrays.toString(data));
}
public static void shellSort(int[] array) {
// Phương pháp dịch chuyển (hiệu quả hơn so với hoán đổi)
for (int gap = array.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < array.length; i++) {
int currentIndex = i;
int temp = array[i];
while (currentIndex - gap >= 0 && temp < array[currentIndex - gap]) {
array[currentIndex] = array[currentIndex - gap];
currentIndex -= gap;
}
array[currentIndex] = temp;
}
}
}
}
3. Sắp Xếp Nhanh (Quick Sort) - O(n log n)
Sắp xếp nhanh hoạt động dựa trên nguyên lý chia để trị. Nó chọn một phần tử làm "chốt" (pivot) và phân chia mảng thành hai phần: phần nhỏ hơn chốt và phần lớn hơn chốt. Quá trình này được lặp lại đệ quy cho đến khi mảng được sắp xếp hoàn toàn.
public class QuickSorter {
public static void main(String[] args) {
int[] arr = {-9, 78, 0, 23, -567, 70};
System.out.println("Trước: " + Arrays.toString(arr));
quickSort(arr, 0, arr.length - 1);
System.out.println("Sau: " + Arrays.toString(arr));
}
public static void quickSort(int[] array, int left, int right) {
int l = left;
int r = right;
int pivot = array[(left + right) / 2];
int temp;
while (l < r) {
while (array[l] < pivot) l++;
while (array[r] > pivot) r--;
if (l >= r) break;
temp = array[l];
array[l] = array[r];
array[r] = temp;
if (array[l] == pivot) r--;
if (array[r] == pivot) l++;
}
if (l == r) {
l++;
r--;
}
if (left < r) quickSort(array, left, r);
if (right > l) quickSort(array, l, right);
}
}
4. Sắp Xếp Trộn (Merge Sort) - O(n log n)
Sắp xếp trộn cũng sử dụng chiến lược chia để trị. Nó liên tục chia mảng thành các nửa nhỏ hơn cho đến khi mỗi nửa chỉ còn một phần tử, sau đó hợp nhất các nửa đó lại theo đúng thứ tự để tạo thành mảng đã sắp xếp.
public class MergeSorter {
public static void main(String[] args) {
int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
int[] temp = new int[arr.length];
System.out.println("Trước: " + Arrays.toString(arr));
mergeSort(arr, temp, 0, arr.length - 1);
System.out.println("Sau: " + Arrays.toString(arr));
}
public static void mergeSort(int[] array, int[] temp, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(array, temp, left, mid);
mergeSort(array, temp, mid + 1, right);
merge(array, temp, left, mid, right);
}
}
private static void merge(int[] array, int[] temp, int left, int mid, int right) {
int i = left, j = mid + 1, t = 0;
while (i <= mid && j <= right) {
if (array[i] < array[j]) temp[t++] = array[i++];
else temp[t++] = array[j++];
}
while (i <= mid) temp[t++] = array[i++];
while (j <= right) temp[t++] = array[j++];
t = 0;
int tempLeft = left;
while (tempLeft <= right) array[tempLeft++] = temp[t++];
}
}
5. Sắp Xếp Cơ Số (Radix Sort) - O(d*(n+k))
Sắp xếp cơ số là một thuật toán "phân phối", trong đó nó sắp xếp các số dựa trên từng chữ số, từ hàng đơn vị đến hàng cao nhất. Nó sử dụng các "thùng" (bucket) để nhóm các số dựa trên giá trị của chữ số đang xét.
Lưu ý: Radix Sort tốn nhiều bộ nhớ và không phù hợp với các mảng chứa số âm (trừ khi có xử lý đặc biệt).
public class RadixSorter {
public static void main(String[] args) {
int[] arr = {833, 42, 5, 71, 1, 3, 6332, 28};
System.out.println("Trước: " + Arrays.toString(arr));
radixSort(arr);
System.out.println("Sau: " + Arrays.toString(arr));
}
public static void radixSort(int[] array) {
int[][] bucket = new int[10][array.length];
int[] bucketCounts = new int[10];
int max = array[0];
for (int val : array) if (val > max) max = val;
int maxLength = String.valueOf(max).length();
for (int digitPlace = 0; digitPlace < maxLength; digitPlace++) {
for (int value : array) {
int digit = value / (int) Math.pow(10, digitPlace) % 10;
bucket[digit][bucketCounts[digit]] = value;
bucketCounts[digit]++;
}
int index = 0;
for (int i = 0; i < 10; i++) {
if (bucketCounts[i] > 0) {
for (int j = 0; j < bucketCounts[i]; j++) {
array[index++] = bucket[i][j];
}
bucketCounts[i] = 0;
}
}
}
}
}
6. Thuật Toán Tìm Kiếm
Tìm Kiếm Tuyến Tính
Duyệt qua từng phần tử của mảng cho đến khi tìm thấy giá trị cần tìm. Mảng không cần phải được sắp xếp.
public class LinearSearch {
public static int search(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;
}
}
Tìm Kiếm Nhị Phân
Yêu cầu mảng đã được sắp xếp. Thuật toán liên tục chia đôi phạm vi tìm kiếm để thu hẹp vị trí của giá trị cần tìm.
public class BinarySearch {
public static int search(int[] arr, int left, int right, int target) {
if (left > right) return -1;
int mid = (left + right) / 2;
if (target > arr[mid]) return search(arr, mid + 1, right, target);
else if (target < arr[mid]) return search(arr, left, mid - 1, target);
else return mid;
}
}
Tìm Kiếm Nội Suy
Tương tự tìm kiếm nhị phân, nhưng vị trí mid được xác định dựa trên giá trị cần tìm, hoạt động tốt với mảng có dữ liệu phân bố đều.
Tìm Kiếm Fibonacci
Sử dụng dãy Fibonacci để xác định vị trí chia, dựa trên tỷ lệ vàng (0.618), hiệu quả cho các mảng lớn.
7. Bảng Băm (Hash Table)
Bảng băm là cấu trúc dữ liệu cho phép truy cập dữ liệu nhanh chóng dựa trên khóa (key). Nó sử dụng hàm băm (hash function) để ánh xạ khóa đến một chỉ mục trong mảng. Các phần tử có cùng chỉ mục được lưu trữ trong một danh sách liên kết (hoặc cây đỏ-đen trong Java 8+).
// Ví dụ đơn giản về bảng băm với phương thức thêm và tìm kiếm
public class SimpleHashTable<K, V> {
private static class Entry<K, V> {
K key;
V value;
Entry<K, V> next;
Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
private Entry<K, V>[] table;
private int capacity;
public SimpleHashTable(int capacity) {
this.capacity = capacity;
table = new Entry[capacity];
}
private int hash(K key) {
return Math.abs(key.hashCode()) % capacity;
}
public void put(K key, V value) {
int index = hash(key);
Entry<K, V> current = table[index];
if (current == null) {
table[index] = new Entry<>(key, value);
return;
}
while (current.next != null) {
if (current.key.equals(key)) {
current.value = value;
return;
}
current = current.next;
}
if (current.key.equals(key)) {
current.value = value;
} else {
current.next = new Entry<>(key, value);
}
}
public V get(K key) {
int index = hash(key);
Entry<K, V> current = table[index];
while (current != null) {
if (current.key.equals(key)) return current.value;
current = current.next;
}
return null;
}
}
8. Cây (Tree)
Cấu trúc cây khắc phục nhược điểm của mảng (chèn/xóa chậm) và danh sách liên kết (tìm kiếm chậm). Cây nhị phân là dạng cơ bản, mỗi nút tối đa có hai nút con.
Duyệt Cây Nhị Phân
- Tiền thứ tự (Preorder): Nút cha -> Cây con trái -> Cây con phải.
- Trung thứ tự (Inorder): Cây con trái -> Nút cha -> Cây con phải.
- Hậu thứ tự (Postorder): Cây con trái -> Cây con phải -> Nút cha.
class BinaryTreeNode<T> {
T value;
BinaryTreeNode<T> left;
BinaryTreeNode<T> right;
BinaryTreeNode(T value) {
this.value = value;
}
void preOrder() {
System.out.print(value + " ");
if (left != null) left.preOrder();
if (right != null) right.preOrder();
}
void inOrder() {
if (left != null) left.inOrder();
System.out.print(value + " ");
if (right != null) right.inOrder();
}
void postOrder() {
if (left != null) left.postOrder();
if (right != null) right.postOrder();
System.out.print(value + " ");
}
}
9. Cây Nhị Phân Lưu Trữ Tuần Tự (Array Binary Tree)
Với cây nhị phân hoàn chỉnh, ta có thể lưu trữ nó dưới dạng mảng. Các công thức xác định quan hệ cha-con:
- Nút con trái của nút thứ
n(chỉ số bắt đầu từ 0) là:2*n + 1 - Nút con phải của nút thứ
nlà:2*n + 2 - Nút cha của nút thứ
nlà:(n-1) / 2
10. Cây Nhị Phân Suy Diễn (Threaded Binary Tree)
Tận dụng các con trỏ null trong cây nhị phân để trỏ đến nút tiền nhiệm (predecessor) hoặc kế nhiệm (successor) trong một thứ tự duyệt nhất định, giúp việc duyệt cây hiệu quả hơn mà không cần đệ quy hoặc stack.
11. Sắp Xếp Vun Đống (Heap Sort) - O(n log n)
Heap Sort là một cải tiến của sắp xếp chọn. Nó sử dụng cấu trúc dữ liệu "đống" (heap), thường là đống nhị phân. Để sắp xếp tăng dần, ta xây dựng một đống lớn (max-heap) và liên tục đưa phần tử lớn nhất (gốc) về cuối mảng.
public class HeapSorter {
public static void sort(int[] arr) {
int n = arr.length;
// Xây dựng đống lớn từ các nút không phải lá
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Trích xuất từng phần tử từ đống
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
}
12. Cây Huffman Và Mã Hóa Huffman
Cây Huffman là một cây nhị phân có trọng số (dựa trên tần suất xuất hiện của các ký tự). Mã Huffman là mã có độ dài thay đổi, sử dụng cây Huffman để biểu diễn các ký tự bằng các dãy nhị phân, giúp nén dữ liệu một cách tối ưu.
Các mã được tạo ra là mã tiền tố (prefix code), nghĩa là không có mã nào là tiền tố của mã khác, đảm bảo việc giải mã không bị nhầm lẫn.