Sắp xếp (Sorting)

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 6)

Sắp xếp (Sorting)

Bubble Sort

Thời gian (Time) O(n²)
Không gian (Space) O(1)

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;
}
Sắp xếp (Sorting)

Heap Sort

Thời gian (Time) O(n log n)
Không gian (Space) O(1)

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);
    }
}
Sắp xếp (Sorting)

Insertion Sort

Thời gian (Time) O(n²)
Không gian (Space) O(1)

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;
}
Sắp xếp (Sorting)

Merge Sort

Thời gian (Time) O(n log n)
Không gian (Space) O(n)

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);
}
Sắp xếp (Sorting)

Quick Sort

Thời gian (Time) O(n log n) trung bình, O(n²) tồi nhất
Không gian (Space) O(log n)

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));
}
Sắp xếp (Sorting)

Selection Sort

Thời gian (Time) O(n²)
Không gian (Space) O(1)

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