Trong lập trình, việc hiểu và triển khai các thuật toán sắp xếp là kỹ năng thiết yếu. Dưới đây là 8 thuật toán tiêu biểu được phân loại theo cơ chế hoạt động, kèm theo minh họa code Java đã được viết lại để dễ đọc và tối ưu hơn.

1. Sắp xếp chèn trực tiếp

Ý tưởng: Duyệt từng phần tử, chèn nó vào đúng vị trí trong dãy đã sắp xếp phía trước.

public class InsertionSort {
    public static void sort(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;
        }
    }
}

2. Sắp xếp Shell

Ý tưởng: Mở rộng sắp xếp chèn bằng cách chia mảng thành các nhóm với khoảng cách giảm dần.

public class ShellSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j;
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp;
            }
        }
    }
}

3. Sắp xếp chọn

Ý tưởng: Tìm phần tử nhỏ nhất trong đoạn chưa sắp xếp, đổi chỗ với phần tử đầu tiên của đoạn đó.

public class SelectionSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }
}

4. Sắp xếp vun đống (Heap Sort)

Ý tưởng: Xây dựng heap max, lần lượt đưa phần tử gốc (lớn nhất) về cuối mảng và tái cấu trúc heap.

public class HeapSort {
    public static void sort(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);
        }
    }

    private static void heapify(int[] arr, int n, int root) {
        int largest = root;
        int left = 2 * root + 1;
        int right = 2 * root + 2;

        if (left < n && arr[left] > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;

        if (largest != root) {
            int swap = arr[root];
            arr[root] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }
}

5. Sắp xếp nổi bọt

Ý tưởng: So sánh liên tiếp các cặp phần tử liền kề, hoán đổi nếu sai thứ tự, lặp đến khi không còn cần hoán đổi.

public class BubbleSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            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;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
}

6. Sắp xếp nhanh (Quick Sort)

Ý tưởng: Chọn pivot, phân vùng mảng sao cho phần tử nhỏ hơn pivot nằm bên trái, lớn hơn nằm bên phải, rồi đệ quy.

public class QuickSort {
    public static void sort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            sort(arr, low, pi - 1);
            sort(arr, pi + 1, high);
        }
    }

    private 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;
    }
}

7. Sắp xếp trộn (Merge Sort)

Ý tưởng: Chia mảng thành hai nửa, sắp xếp đệ quy từng nửa, sau đó trộn hai nửa đã sắp xếp lại.

public class MergeSort {
    public static void sort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            sort(arr, left, mid);
            sort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

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

        System.arraycopy(temp, 0, arr, left, temp.length);
    }
}

8. Sắp xếp theo cơ số (Radix Sort)

Ý tưởng: Sắp xếp theo từng chữ số, từ hàng đơn vị đến hàng cao nhất, dùng bucket để nhóm giá trị.

import java.util.*;

public class RadixSort {
    public static void sort(int[] arr) {
        int max = Arrays.stream(arr).max().orElse(0);
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    private static void countingSortByDigit(int[] arr, int exp) {
        List buckets = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            buckets.add(new LinkedList<>());
        }

        for (int value : arr) {
            int digit = (value / exp) % 10;
            buckets.get(digit).add(value);
        }

        int index = 0;
        for (Queue<Integer> bucket : buckets) {
            while (!bucket.isEmpty()) {
                arr[index++] = bucket.poll();
            }
        }
    }
}