Các thuật toán sắp xếp thường được sử dụng trong lập trình bao gồm nhiều phương pháp khác nhau, mỗi phương pháp có ưu và nhược điểm riêng. Dưới đây là các thuật toán sắp xếp chính được thực hiện bằng ngôn ngữ Java:

1. Chèn trực tiếp (Insertion Sort)

Ý tưởng cơ bản của thuật toán này là chèn từng phần tử vào đúng vị trí trong mảng đã sắp xếp trước đó.

public class InsertionSort {
    public static void main(String[] args) {
        int[] data = {49, 38, 65, 97, 76, 13, 27, 49};
        for (int i = 1; i < data.length; i++) {
            int key = data[i];
            int j = i - 1;
            while (j >= 0 && data[j] > key) {
                data[j + 1] = data[j];
                j--;
            }
            data[j + 1] = key;
        }
        for (int num : data) {
            System.out.println(num);
        }
    }
}

2. Sắp xếp Shell (Shell Sort)

Shell sort cải thiện hiệu suất bằng cách so sánh các phần tử cách đều thay vì chỉ so sánh các phần tử liền kề.

public class ShellSort {
    public static void main(String[] args) {
        int[] array = {1, 54, 6, 3, 78, 34, 12, 45};
        int n = array.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = array[i];
                int j = i;
                while (j >= gap && array[j - gap] > temp) {
                    array[j] = array[j - gap];
                    j -= gap;
                }
                array[j] = temp;
            }
        }
        for (int value : array) {
            System.out.println(value);
        }
    }
}

3. Sắp xếp chọn lọc đơn giản (Selection Sort)

Phương pháp này tìm phần tử nhỏ nhất và hoán đổi nó với phần tử đầu tiên chưa được sắp xếp.

public class SelectionSort {
    public static void main(String[] args) {
        int[] numbers = {1, 54, 6, 3, 78, 34, 12, 45};
        for (int i = 0; i < numbers.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[j] < numbers[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = numbers[minIndex];
            numbers[minIndex] = numbers[i];
            numbers[i] = temp;
        }
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

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

Heap sort sử dụng cấu trúc dữ liệu Heap để đảm bảo phần tử lớn nhất luôn ở đỉnh.

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

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

    public static void main(String[] args) {
        int[] data = {49, 38, 65, 97, 76, 13, 27, 49};
        sort(data);
        for (int num : data) {
            System.out.println(num);
        }
    }
}

5. Sắp xếp nổi bọt (Bubble Sort)

Bubble sort liên tục so sánh hai phần tử liền kề và hoán đổi chúng nếu không đúng thứ tự.

public class BubbleSort {
    public static void main(String[] args) {
        int[] elements = {49, 38, 65, 97, 76, 13, 27, 49};
        for (int i = 0; i < elements.length - 1; i++) {
            for (int j = 0; j < elements.length - i - 1; j++) {
                if (elements[j] > elements[j + 1]) {
                    int temp = elements[j];
                    elements[j] = elements[j + 1];
                    elements[j + 1] = temp;
                }
            }
        }
        for (int element : elements) {
            System.out.println(element);
        }
    }
}

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

Quick sort chọn một phần tử làm chốt và phân chia mảng thành hai nửa dựa trên giá trị chốt.

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

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

    public static void main(String[] args) {
        int[] data = {49, 38, 65, 97, 76, 13, 27, 49};
        quickSort(data, 0, data.length - 1);
        for (int num : data) {
            System.out.println(num);
        }
    }
}

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

Merge sort chia mảng thành các phần nhỏ hơn, sau đó hợp nhất chúng lại theo thứ tự.

public class MergeSort {
    public static void mergeSort(int[] array) {
        if (array.length < 2) {
            return;
        }
        int mid = array.length / 2;
        int[] left = new int[mid];
        int[] right = new int[array.length - mid];

        System.arraycopy(array, 0, left, 0, mid);
        if (mid < array.length) {
            System.arraycopy(array, mid, right, 0, array.length - mid);
        }

        mergeSort(left);
        mergeSort(right);

        merge(array, left, right);
    }

    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        while (i < left.length) {
            result[k++] = left[i++];
        }
        while (j < right.length) {
            result[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        int[] data = {49, 38, 65, 97, 76, 13, 27, 49};
        mergeSort(data);
        for (int num : data) {
            System.out.println(num);
        }
    }
}

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

Radix sort xử lý từng chữ số của các phần tử từ hàng đơn vị lên đến hàng cao nhất.

import java.util.ArrayList;
import java.util.List;

public class RadixSort {
    public static void radixSort(int[] array) {
        int max = getMax(array);
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countSort(array, exp);
        }
    }

    private static void countSort(int[] array, int exp) {
        int[] output = new int[array.length];
        int[] count = new int[10];
        for (int i = 0; i < array.length; i++) {
            count[(array[i] / exp) % 10]++;
        }
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        for (int i = array.length - 1; i >= 0; i--) {
            output[count[(array[i] / exp) % 10] - 1] = array[i];
            count[(array[i] / exp) % 10]--;
        }
        System.arraycopy(output, 0, array, 0, array.length);
    }

    private static int getMax(int[] array) {
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] data = {49, 38, 65, 97, 76, 13, 27, 49};
        radixSort(data);
        for (int num : data) {
            System.out.println(num);
        }
    }
}