Thuật toán sắp xếp chèn (Insertion Sort) là một thuật toán sắp xếp đơn giản và trực quan, hoạt động theo cách tương tự như cách mà bạn có thể sắp xếp các thẻ bài trong tay. Thuật toán này rất hiệu quả với các dãy dữ liệu nhỏ hoặc gần như đã được sắp xếp. Dưới đây là hướng dẫn chi tiết về thuật toán sắp xếp chèn, bao gồm giải thích và mã PHP.
Thuật toán sắp xếp chèn làm việc bằng cách chia dãy dữ liệu thành hai phần: phần đã được sắp xếp và phần chưa được sắp xếp. Nó liên tục lấy phần tử từ phần chưa được sắp xếp và chèn nó vào vị trí chính xác trong phần đã được sắp xếp.
Thuật toán Sắp xếp Chèn:
Mã PHP:
function insertionSort($array) {
$n = count($array);
// Duyệt từ phần tử thứ hai đến cuối dãy
for ($i = 1; $i < $n; $i++) {
$key = $array[$i]; // Lưu giá trị hiện tại
$j = $i - 1;
// Di chuyển các phần tử lớn hơn $key sang bên phải
while ($j >= 0 && $array[$j] > $key) {
$array[$j + 1] = $array[$j];
$j--;
}
// Chèn $key vào đúng vị trí
$array[$j + 1] = $key;
}
return $array;
}
// Ví dụ sử dụng
$numbers = [12, 11, 13, 5, 6];
$sortedNumbers = insertionSort($numbers);
echo "Sắp xếp chèn: " . implode(", ", $sortedNumbers);
Thuật toán sắp xếp chèn là một phương pháp đơn giản và hiệu quả cho việc sắp xếp các dãy nhỏ hoặc gần như đã được sắp xếp. Mặc dù có độ phức tạp thời gian cao hơn so với các thuật toán sắp xếp khác như Merge Sort hoặc Quick Sort, nó vẫn là một công cụ hữu ích trong nhiều tình huống thực tế. Việc hiểu và áp dụng thuật toán này có thể giúp cải thiện kỹ năng lập trình của bạn và giải quyết các bài toán sắp xếp một cách hiệu quả.
