Sắp Xếp Chèn (Insertion Sort)

Giải thuật xây dựng mảng có thứ tự bằng cách chèn từng phần tử vào vị trí thích hợp:

public class SapXepChen {
    public static int[] sapXep(int[] arr) {
        for (int i=1; i=0 && arr[j]>key) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = key;
        }
        return arr;
    }
}

Sắp Xếp Khoảng Cách Giảm Dần (Shell Sort)

Phiên bản cải tiến của Insertion Sort với việc sử dụng khoảng cách giảm dần:

public class SapXepKhoangCach {
    public static int[] sapXep(int[] arr) {
        int n = arr.length;
        for (int gap=n/2; gap>0; gap/=2) {
            for (int i=gap; i= gap && arr[j-gap] > temp) {
                    arr[j] = arr[j-gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
        return arr;
    }
}

Sắp Xếp Trộn (Merge Sort)

Thuật toán chia để trị hoạt động qua hai giai đoạn:

1. Chia mảng thành các nửa nhỏ và sắp xếp đệ quy
2. Trộn các nửa đã sắp xếp thành mảng hoàn chỉnh

public class SapXepTron {
    public static int[] sapXep(int[] arr) {
        if (arr.length <= 1) return arr;
        int mid = arr.length / 2;
        return tron(
            sapXep(Arrays.copyOfRange(arr, 0, mid)),
            sapXep(Arrays.copyOfRange(arr, mid, arr.length))
        );
    }

    private static int[] tron(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        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++];
        return result;
    }
}

Sắp Xếp Nhanh (Quick Sort)

Giải thuật chia mảng thành các phần nhỏ hơn dựa trên phần tử trục (pivot):

public class SapXepNhanh {
    public static int[] sapXep(int[] arr, int left, int right) {
        if (left < right) {
            int pivot = timPivot(arr, left, right);
            sapXep(arr, left, pivot-1);
            sapXep(arr, pivot+1, right);
        }
        return arr;
    }

    private static int timPivot(int[] arr, int left, int right) {
        int pivot = left + (int)(Math.random()*(right-left+1));
        int value = arr[pivot];
        swap(arr, pivot, right);
        int index = left;
        for (int i=left; i

public class SapXepVunDong {
    public static int[] sapXep(int[] arr) {
        int n = arr.length;
        for (int i=n/2-1; i>=0; i--) {
            vunDong(arr, n, i);
        }
        for (int i=n-1; i>0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            vunDong(arr, i, 0);
        }
        return arr;
    }

    private static void vunDong(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;
            vunDong(arr, n, largest);
        }
    }
}