Thuật Toán Sắp Xếp Chọn (Selection Sort) Trong PHP
Thời gian đọc: 9 phút
Thời gian đọc: 9 phút
Thuật toán sắp xếp chọn (Selection Sort) là một thuật toán sắp xếp đơn giản và trực quan, hoạt động bằng cách tìm phần tử nhỏ nhất (hoặc lớn nhất, tùy thuộc vào thứ tự sắp xếp) trong dãy chưa được sắp xếp và chuyển nó vào vị trí đúng trong dãy đã 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 cách hoạt động và mã PHP minh họa.
Thuật toán Sắp xếp Chọn:
Thuật toán Sắp xếp Chọn:
Mã PHP:
function selectionSort($array) {
$n = count($array);
// Duyệt qua toàn bộ danh sách
for ($i = 0; $i < $n - 1; $i++) {
// Tìm chỉ số phần tử nhỏ nhất trong phần chưa sắp xếp
$minIndex = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($array[$j] < $array[$minIndex]) {
$minIndex = $j;
}
}
// Đổi chỗ phần tử nhỏ nhất với phần tử đầu tiên trong phần chưa sắp xếp
if ($minIndex != $i) {
$temp = $array[$i];
$array[$i] = $array[$minIndex];
$array[$minIndex] = $temp;
}
}
return $array;
}
// Ví dụ sử dụng
$numbers = [64, 25, 12, 22, 11];
$sortedNumbers = selectionSort($numbers);
echo "Sắp xếp chọn: " . implode(", ", $sortedNumbers);
Trước khi sắp xếp:
[64, 25, 12, 22, 11]
Sau khi sắp xếp:
[11, 12, 22, 25, 64]
Thuật toán sắp xếp chọn là một trong những thuật toán sắp xếp cơ bản và đơn giản, hoạt động bằng cách tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đưa nó vào vị trí chính xác trong phần đã 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ư Quick Sort hoặc Merge Sort, nó vẫn là một công cụ hữu ích trong các tình huống cụ thể và giúp nâng cao hiểu biết về các thuật toán sắp xếp cơ bản.
Sắp xếp tăng dần và sắp xếp giảm dần là hai yêu cầu phổ biến khi sử dụng thuật toán sắp xếp. Thuật toán sắp xếp chọn có thể dễ dàng được điều chỉnh để thực hiện cả hai loại sắp xếp này.
Đây là cách sắp xếp phổ biến nhất, trong đó các phần tử trong danh sách được sắp xếp từ nhỏ nhất đến lớn nhất.
Mã PHP để sắp xếp tăng dần:
function selectionSortAsc($array) {
$n = count($array);
// Duyệt qua toàn bộ danh sách
for ($i = 0; $i < $n - 1; $i++) {
// Tìm chỉ số phần tử nhỏ nhất trong phần chưa sắp xếp
$minIndex = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($array[$j] < $array[$minIndex]) {
$minIndex = $j;
}
}
// Đổi chỗ phần tử nhỏ nhất với phần tử đầu tiên trong phần chưa sắp xếp
if ($minIndex != $i) {
$temp = $array[$i];
$array[$i] = $array[$minIndex];
$array[$minIndex] = $temp;
}
}
return $array;
}
// Ví dụ sử dụng
$numbersAsc = [64, 25, 12, 22, 11];
$sortedNumbersAsc = selectionSortAsc($numbersAsc);
echo "Sắp xếp tăng dần: " . implode(", ", $sortedNumbersAsc);
Trong trường hợp này, các phần tử trong danh sách sẽ được sắp xếp từ lớn nhất đến nhỏ nhất.
Mã PHP để sắp xếp giảm dần:
function selectionSortDesc($array) {
$n = count($array);
// Duyệt qua toàn bộ danh sách
for ($i = 0; $i < $n - 1; $i++) {
// Tìm chỉ số phần tử lớn nhất trong phần chưa sắp xếp
$maxIndex = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($array[$j] > $array[$maxIndex]) {
$maxIndex = $j;
}
}
// Đổi chỗ phần tử lớn nhất với phần tử đầu tiên trong phần chưa sắp xếp
if ($maxIndex != $i) {
$temp = $array[$i];
$array[$i] = $array[$maxIndex];
$array[$maxIndex] = $temp;
}
}
return $array;
}
// Ví dụ sử dụng
$numbersDesc = [64, 25, 12, 22, 11];
$sortedNumbersDesc = selectionSortDesc($numbersDesc);
echo "Sắp xếp giảm dần: " . implode(", ", $sortedNumbersDesc);
Tìm kiếm phần tử lớn nhất và nhỏ nhất trong một mảng là các bài toán cơ bản trong lập trình và rất quan trọng trong nhiều thuật toán và ứng dụng thực tế. Dưới đây là hướng dẫn chi tiết về cách thực hiện các bài toán này bằng PHP.
Mục tiêu: Xác định phần tử nhỏ nhất trong một mảng.
Cách thực hiện:
Mã PHP để tìm phần tử nhỏ nhất:
function findMin($array) {
if (empty($array)) {
return null; // Trả về null nếu mảng rỗng
}
$min = $array[0]; // Khởi tạo giá trị nhỏ nhất bằng phần tử đầu tiên
// Duyệt qua mảng để tìm giá trị nhỏ nhất
foreach ($array as $value) {
if ($value < $min) {
$min = $value;
}
}
return $min;
}
// Ví dụ sử dụng
$numbers = [64, 25, 12, 22, 11];
$minNumber = findMin($numbers);
echo "Phần tử nhỏ nhất: " . $minNumber;
Giải thích:
empty($array): Kiểm tra nếu mảng là rỗng.$min = $array[0]: Khởi tạo biến $min với phần tử đầu tiên trong mảng.foreach ($array as $value): Duyệt qua từng phần tử của mảng.if ($value < $min): Cập nhật giá trị của biến $min nếu phần tử hiện tại nhỏ hơn giá trị hiện tại của $min.Mục tiêu: Xác định phần tử lớn nhất trong một mảng.
Cách thực hiện:
Mã PHP để tìm phần tử lớn nhất:
function findMax($array) {
if (empty($array)) {
return null; // Trả về null nếu mảng rỗng
}
$max = $array[0]; // Khởi tạo giá trị lớn nhất bằng phần tử đầu tiên
// Duyệt qua mảng để tìm giá trị lớn nhất
foreach ($array as $value) {
if ($value > $max) {
$max = $value;
}
}
return $max;
}
// Ví dụ sử dụng
$numbers = [64, 25, 12, 22, 11];
$maxNumber = findMax($numbers);
echo "Phần tử lớn nhất: " . $maxNumber;
Giải thích:
empty($array): Kiểm tra nếu mảng là rỗng.$max = $array[0]: Khởi tạo biến $max với phần tử đầu tiên trong mảng.foreach ($array as $value): Duyệt qua từng phần tử của mảng.if ($value > $max): Cập nhật giá trị của biến $max nếu phần tử hiện tại lớn hơn giá trị hiện tại của $max.
