Bubble Sort
Mô tả nguyên lý
Thuật toán sắp xếp nổi bọt đơn giản, lặp qua danh sách, so sánh các cặp liền kề và tráo đổi nếu sai thứ tự.
Cài đặt mẫu (Implementation)
function bubbleSort(&$arr) {
$n = count($arr);
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $n - $i - 1; $j++) {
if ($arr[$j] > $arr[$j+1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $temp;
}
}
}
return $arr;
}
Heap Sort
Mô tả nguyên lý
Sử dụng cấu trúc dữ liệu Binary Heap để sắp xếp các phần tử bằng cách trích xuất giá trị lớn nhất.
Cài đặt mẫu (Implementation)
function heapify(&$arr, $n, $i) {
$largest = $i;
$l = 2 * $i + 1;
$r = 2 * $i + 2;
if ($l < $n && $arr[$l] > $arr[$largest]) $largest = $l;
if ($r < $n && $arr[$r] > $arr[$largest]) $largest = $r;
if ($largest != $i) {
$swap = $arr[$i]; $arr[$i] = $arr[$largest]; $arr[$largest] = $swap;
heapify($arr, $n, $largest);
}
}
Insertion Sort
Mô tả nguyên lý
Xây dựng mảng sắp xếp từng phần tử một bằng cách chèn phần tử tiếp theo vào đúng vị trí trong phần đã sắp xếp.
Cài đặt mẫu (Implementation)
function insertionSort(&$arr) {
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= 0 && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
return $arr;
}
Merge Sort
Mô tả nguyên lý
Thuật toán sắp xếp trộn dựa trên nguyên lý chia để trị, chia đôi mảng liên tục cho đến khi còn 1 phần tử rồi trộn lại.
Cài đặt mẫu (Implementation)
function mergeSort($arr) {
if (count($arr) <= 1) return $arr;
$mid = floor(count($arr) / 2);
$left = mergeSort(array_slice($arr, 0, $mid));
$right = mergeSort(array_slice($arr, $mid));
return merge($left, $right);
}
function merge($left, $right) {
$res = [];
while (count($left) > 0 && count($right) > 0) {
if ($left[0] <= $right[0]) $res[] = array_shift($left);
else $res[] = array_shift($right);
}
return array_merge($res, $left, $right);
}
Quick Sort
Mô tả nguyên lý
Thuật toán chia để trị (Divide and Conquer), chọn một phần tử làm chốt (pivot) và phân hoạch mảng.
Cài đặt mẫu (Implementation)
function quickSort(&$arr) {
if (count($arr) < 2) return $arr;
$left = $right = [];
$pivot = $arr[0];
for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] < $pivot) $left[] = $arr[$i];
else $right[] = $arr[$i];
}
return array_merge(quickSort($left), [$pivot], quickSort($right));
}
Selection Sort
Mô tả nguyên lý
Liên tục tìm phần tử nhỏ nhất từ phần chưa sắp xếp và đưa nó về đầu danh sách.
Cài đặt mẫu (Implementation)
function selectionSort(&$arr) {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
$min = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($arr[$j] < $arr[$min]) $min = $j;
}
if ($min != $i) {
$t = $arr[$i]; $arr[$i] = $arr[$min]; $arr[$min] = $t;
}
}
return $arr;
}