Nếu học lập trình mà chưa từng:

• bubble sort,
• quick sort,
• merge sort,

thì gần như chưa trải qua “tuổi thơ dữ dội” của thuật toán.

Thuật toán sắp xếp là một trong những chủ đề kinh điển nhất của khoa học máy tính.

Nghe thì có vẻ đơn giản:

“Sắp xếp dãy số từ bé đến lớn.”

Nhưng phía sau đó lại là:

• tối ưu hiệu năng,
• xử lý dữ liệu lớn,
• tư duy recursion,
• chia để trị,
• và cả những màn benchmark khiến CPU nóng như chơi game.

Điều thú vị là:

mỗi thuật toán đều có “tính cách” riêng.

Có thuật toán:

• cực dễ hiểu,
• nhưng chậm.

Có thuật toán:

• siêu nhanh,
• nhưng code nhìn như bùa chú.

Và có thuật toán:

• gần như sinh ra để đi phỏng vấn.

1. Bubble Sort — thuật toán “quốc dân” cho người mới học

Bubble Sort gần như là thuật toán đầu tiên mà mọi sinh viên IT đều gặp.

Nó hoạt động kiểu:

• so sánh 2 phần tử cạnh nhau,
• nếu sai thứ tự thì đổi chỗ,
• lặp đi lặp lại cho tới khi mảng được sắp xếp.

Tên “Bubble” đến từ việc:

phần tử lớn nhất sẽ “nổi lên” cuối mảng như bong bóng.

Ví dụ

Mảng:

5 3 8 2

Sau vòng đầu:

3 5 2 8

Số 8 nổi lên cuối.

Code Java

public class BubbleSort {
 public static void bubbleSort(int[] arr) {
 int n = arr.length;

 for (int i = 0; i < n - 1; i++) {
 for (int j = 0; j < n - i - 1; j++) {
 if (arr[j] > arr[j + 1]) {
 int temp = arr[j];
 arr[j] = arr[j + 1];
 arr[j + 1] = temp;
 }
 }
 }
 }
}

Độ phức tạp

Ưu điểm

• Dễ hiểu
• Dễ code
• Phù hợp người mới học

Nhược điểm

• Chậm
• Không phù hợp dữ liệu lớn
• CPU “khóc thét” khi mảng quá to

2. Selection Sort — kiểu “tìm boss mạnh nhất mỗi vòng”

Selection Sort hoạt động theo cách:

• tìm phần tử nhỏ nhất,
• đưa lên đầu,
• lặp lại với phần còn lại.

Nó giống kiểu:

mỗi vòng đi tìm “ứng viên mạnh nhất” rồi kéo lên trước.

Code Java

public class SelectionSort {
 public static void selectionSort(int[] arr) {
 int n = arr.length;

 for (int i = 0; i < n - 1; i++) {
 int minIndex = i;

 for (int j = i + 1; j < n; j++) {
 if (arr[j] < arr[minIndex]) {
 minIndex = j;
 }
 }

 int temp = arr[minIndex];
 arr[minIndex] = arr[i];
 arr[i] = temp;
 }
 }
}

Độ phức tạp

Ưu điểm

• Ít swap hơn Bubble Sort
• Dễ hiểu

Nhược điểm

• Vẫn khá chậm
• Không tối ưu cho dữ liệu lớn

3. Insertion Sort — thuật toán “xếp bài poker”

Nếu từng chơi bài poker ngoài đời thì bạn đã dùng Insertion Sort rồi.

Cách hoạt động:

• lấy từng phần tử,
• chèn vào đúng vị trí trong phần đã sắp xếp.

Nó giống hệt cách:

cầm lá bài mới rồi chèn vào bộ bài trên tay.

Code Java

public class InsertionSort {
 public static void insertionSort(int[] arr) {
 for (int i = 1; i < arr.length; i++) {
 int key = arr[i];
 int j = i - 1;

 while (j >= 0 && arr[j] > key) {
 arr[j + 1] = arr[j];
 j--;
 }

 arr[j + 1] = key;
 }
 }
}

Độ phức tạp

Ưu điểm

• Nhanh với mảng nhỏ
• Hiệu quả khi dữ liệu gần sắp xếp
• Code ngắn gọn

Nhược điểm

• Không phù hợp dữ liệu lớn

4. Merge Sort — ông hoàng chia để trị

Merge Sort là lúc mọi thứ bắt đầu “ngầu” hơn.

Thuật toán này dùng chiến thuật:

chia để trị.

Nó sẽ:

1. Chia mảng thành 2 nửa
2. Sắp xếp từng nửa
3. Gộp lại

Nghe giống kiểu:

“chia quân ra xử lý từng mặt trận rồi hợp nhất.”

Code Java

public class MergeSort {

 public static void mergeSort(int[] arr, int left, int right) {
 if (left < right) {
 int mid = (left + right) / 2;

 mergeSort(arr, left, mid);
 mergeSort(arr, mid + 1, right);

 merge(arr, left, mid, right);
 }
 }

 public static void merge(int[] arr, int left, int mid, int right) {
 int[] temp = new int[right - left + 1];

 int i = left;
 int j = mid + 1;
 int k = 0;

 while (i <= mid && j <= right) {
 if (arr[i] <= arr[j]) {
 temp[k++] = arr[i++];
 } else {
 temp[k++] = arr[j++];
 }
 }

 while (i <= mid) {
 temp[k++] = arr[i++];
 }

 while (j <= right) {
 temp[k++] = arr[j++];
 }

 for (i = left, k = 0; i <= right; i++, k++) {
 arr[i] = temp[k];
 }
 }
}

Độ phức tạp

Ưu điểm

• Rất ổn định
• Hiệu năng mạnh
• Phù hợp dữ liệu lớn

Nhược điểm

• Tốn thêm bộ nhớ
• Code khó hơn Bubble Sort nhiều

5. Quick Sort — chiến thần phỏng vấn thuật toán

Quick Sort gần như là thuật toán nổi tiếng nhất.

Nó cực nhanh trong thực tế.

Ý tưởng chính:

• chọn một pivot,
• đưa số nhỏ hơn sang trái,
• số lớn hơn sang phải,
• rồi đệ quy tiếp.

Code Java

public class QuickSort {

 public static void quickSort(int[] arr, int low, int high) {
 if (low < high) {
 int pi = partition(arr, low, high);

 quickSort(arr, low, pi - 1);
 quickSort(arr, pi + 1, high);
 }
 }

 public static int partition(int[] arr, int low, int high) {
 int pivot = arr[high];
 int i = low - 1;

 for (int j = low; j < high; j++) {
 if (arr[j] < pivot) {
 i++;

 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }
 }

 int temp = arr[i + 1];
 arr[i + 1] = arr[high];
 arr[high] = temp;

 return i + 1;
 }
}

Độ phức tạp

Ưu điểm

• Rất nhanh trong thực tế
• Hiệu năng mạnh
• Dùng phổ biến

Nhược điểm

• Worst case khá đau
• Dễ stack overflow nếu xử lý không tốt

6. Heap Sort — dùng cấu trúc Heap để tối ưu

Heap Sort sử dụng:

Binary Heap.

Nó sẽ:

• tạo Max Heap,
• lấy phần tử lớn nhất đưa xuống cuối,
• lặp lại.

Nghe hơi học thuật.

Nhưng thật ra khá mạnh.

Code Java

public class HeapSort {

 public static void heapSort(int[] arr) {
 int n = arr.length;

 for (int i = n / 2 - 1; i >= 0; i--) {
 heapify(arr, n, i);
 }

 for (int i = n - 1; i > 0; i--) {
 int temp = arr[0];
 arr[0] = arr[i];
 arr[i] = temp;

 heapify(arr, i, 0);
 }
 }

 public 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);
 }
 }
}

Độ phức tạp

Ưu điểm

• Không bị worst case như Quick Sort
• Hiệu năng ổn định

Nhược điểm

• Khó hiểu hơn
• Cache performance không tốt bằng Quick Sort

7. Counting Sort — tốc độ ánh sáng nhưng có điều kiện

Counting Sort rất đặc biệt.

Nó không so sánh phần tử như các thuật toán khác.

Thay vào đó:

• đếm số lần xuất hiện,
• rồi dựng lại mảng.

Nếu dữ liệu phù hợp:

nó nhanh cực kỳ.

Code Java

public class CountingSort {

 public static void countingSort(int[] arr) {
 int max = arr[0];

 for (int num : arr) {
 if (num > max) {
 max = num;
 }
 }

 int[] count = new int[max + 1];

 for (int num : arr) {
 count[num]++;
 }

 int index = 0;

 for (int i = 0; i < count.length; i++) {
 while (count[i] > 0) {
 arr[index++] = i;
 count[i]--;
 }
 }
 }
}

Độ phức tạp

k là giá trị lớn nhất trong mảng

Ưu điểm

• Rất nhanh
• Không dùng comparison
• Tốc độ cực mạnh với dữ liệu phù hợp

Nhược điểm

• Tốn bộ nhớ
• Không phù hợp dữ liệu quá lớn
• Chỉ phù hợp số nguyên trong phạm vi nhỏ

So sánh tổng thể các thuật toán

Kết luận

Nếu phải tóm tắt ngắn gọn:

• Bubble Sort → học tư duy cơ bản.
• Selection Sort → tối ưu swap.
• Insertion Sort → tốt với dữ liệu nhỏ.
• Merge Sort → ổn định và mạnh.
• Quick Sort → vua hiệu năng thực tế.
• Heap Sort → ổn định, ít sợ worst case.
• Counting Sort → siêu nhanh nhưng có điều kiện.

Trong thực tế:

• Quick Sort và Merge Sort được dùng rất nhiều.
• Java cũng dùng nhiều thuật toán lai để tối ưu hiệu năng.
• Không có thuật toán nào “best cho mọi trường hợp”.

Giống như developer chọn framework vậy.

Quan trọng nhất vẫn là:

đúng bài toán thì mới tối ưu được hiệu năng.