Sắp Xếp Chèn
Phương pháp chèn duy trì mảng con đã sắp xếp và chèn từng phần tử vào vị trí thích hợp. Độ phức tạp trung bình O(n²), nhưng hiệu quả với mảng nhỏ hoặc gần sắp xếp.
Thực hiện tối ưu
public static void insertionSort(int[] data) {
int size = data.length;
for (int pos = 1; pos < size; pos++) {
int current = data[pos];
int index = pos - 1;
while (index >= 0 && data[index] > current) {
data[index + 1] = data[index];
index--;
}
data[index + 1] = current;
}
}Sắp Xếp Chọn
Chọn phần tử nhỏ nhất trong mảng chưa sắp xếp và hoán đổi với phần tử đầu tiên của mảng con chưa sắp xếp. Heap sort là phiên bản cải tiến với độ phức tạp O(n log n).
Heap Sort
public static void heapSort(int[] array) {
int n = array.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
for (int i = n - 1; i > 0; i--) {
int temp = array[0];
array[0] = array[i];
array[i] = temp;
heapify(array, i, 0);
}
}
private static void heapify(int[] arr, int size, int root) {
int largest = root;
int left = 2 * root + 1;
int right = 2 * root + 2;
if (left < size && arr[left] > arr[largest]) largest = left;
if (right < size && arr[right] > arr[largest]) largest = right;
if (largest != root) {
int swap = arr[root];
arr[root] = arr[largest];
arr[largest] = swap;
heapify(arr, size, largest);
}
}Sắp Xếp Đổi Chỗ
Quick sort chia mảng thành hai phần dựa trên pivot, trong khi bubble sort liên tục hoán đổi các phần tử kề nhau nếu sai thứ tự.
Quick Sort (Phiên bản không đệ quy)
import java.util.Stack;
public static void quickSortNonRecursive(int[] data) {
Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(data.length - 1);
while (!stack.isEmpty()) {
int high = stack.pop();
int low = stack.pop();
if (low >= high) continue;
int pivot = partition(data, low, high);
if (pivot - 1 > low) {
stack.push(low);
stack.push(pivot - 1);
}
if (pivot + 1 < high) {
stack.push(pivot + 1);
stack.push(high);
}
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; 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[right];
arr[right] = temp;
return i + 1;
}Bubble Sort (Tối ưu)
public static void bubbleSortOptimized(int[] data) {
int n = data.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (data[j] > data[j + 1]) {
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}