PHP 各种排序算法实现代码

下面我将详细讲解“PHP 各种排序算法实现代码”的完整攻略。

简介

排序算法是计算机科学最常用的算法之一，它可以将一组数据按照特定的排序规则进行排序。在实际的开发中，我们经常需要对数据进行排序，比如搜索引擎对搜索结果页的排序，电商网站对商品列表页的排序等。

目前常见的排序算法有插入排序、选择排序、希尔排序、归并排序、快速排序、堆排序等。下面我们将会分别介绍这些排序算法以及它们的 PHP 实现。

1. 插入排序

插入排序的思想是将一个待排序的元素，插入到已经排好序的子序列中，使插入后仍保持有序状态。具体实现可以参考以下代码：

function insertionSort($arr) {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $temp = $arr[$i]; // 待排序的元素
        $j = $i - 1; // 已排序序列的最后一个元素的下标
        while ($j >= 0 && $arr[$j] > $temp) {
            // 将大于待排序元素的元素向后移动
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        // 待排序元素插入到正确的位置
        $arr[$j + 1] = $temp;
    }
    return $arr;
}

示例：

$arr = [5, 2, 4, 6, 1, 3];
echo implode(', ', insertionSort($arr)); // 1, 2, 3, 4, 5, 6

2. 选择排序

选择排序的思想是每次从待排序的元素中选出最小（或最大）的元素，放入已排序序列的最后面。具体实现可以参考以下代码：

function selectionSort($arr) {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        $minIndex = $i; // 最小元素的下标
        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }
        // 将最小元素交换到已排序序列的末尾
        list($arr[$i], $arr[$minIndex]) = [$arr[$minIndex], $arr[$i]];
    }
    return $arr;
}

示例：

$arr = [5, 2, 4, 6, 1, 3];
echo implode(', ', selectionSort($arr)); // 1, 2, 3, 4, 5, 6

3. 希尔排序

希尔排序是插入排序的变种，它先将待排序序列分成若干子序列，对每个子序列进行插入排序，然后再对整个序列进行一次插入排序。具体实现可以参考以下代码：

function shellSort($arr) {
    $len = count($arr);
    $gap = $len;
    while ($gap > 1) {
        $gap = intval($gap / 2);
        for ($i = $gap; $i < $len; $i++) {
            $temp = $arr[$i];
            $j = $i - $gap;
            while ($j >= 0 && $arr[$j] > $temp) {
                $arr[$j + $gap] = $arr[$j];
                $j -= $gap;
            }
            $arr[$j + $gap] = $temp;
        }
    }
    return $arr;
}

示例：

$arr = [5, 2, 4, 6, 1, 3];
echo implode(', ', shellSort($arr)); // 1, 2, 3, 4, 5, 6

4. 归并排序

归并排序的思路是将待排序序列分成若干个子序列，对子序列进行递归地排序，然后再将排序后的子序列合并成有序序列。具体实现可以参考以下代码：

function mergeSort($arr) {
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }
    $midIndex = intval($len / 2);
    $leftArr = array_slice($arr, 0, $midIndex);
    $rightArr = array_slice($arr, $midIndex);
    $leftArr = mergeSort($leftArr);
    $rightArr = mergeSort($rightArr);
    return merge($leftArr, $rightArr);
}

function merge($arr1, $arr2) {
    $i = $j = 0;
    $result = [];
    while ($i < count($arr1) && $j < count($arr2)) {
        if ($arr1[$i] < $arr2[$j]) {
            $result[] = $arr1[$i];
            $i++;
        } else {
            $result[] = $arr2[$j];
            $j++;
        }
    }
    while ($i < count($arr1)) {
        $result[] = $arr1[$i];
        $i++;
    }
    while ($j < count($arr2)) {
        $result[] = $arr2[$j];
        $j++;
    }
    return $result;
}

示例：

$arr = [5, 2, 4, 6, 1, 3];
echo implode(', ', mergeSort($arr)); // 1, 2, 3, 4, 5, 6

5. 快速排序

快速排序的思路是选择一个基准元素，将比它小的元素放在它的左侧，将比它大的元素放在它的右侧，然后对左右两侧的元素进行递归排序。具体实现可以参考以下代码：

function quickSort($arr) {
    $len = count($arr);
    if ($len < 2) {
        return $arr;
    }
    $leftArr = $rightArr = [];
    $pivotIndex = intval($len / 2);
    $pivot = $arr[$pivotIndex];
    unset($arr[$pivotIndex]);
    foreach ($arr as $value) {
        if ($value < $pivot) {
            $leftArr[] = $value;
        } else {
            $rightArr[] = $value;
        }
    }
    return array_merge(quickSort($leftArr), [$pivot], quickSort($rightArr));
}

示例：

$arr = [5, 2, 4, 6, 1, 3];
echo implode(', ', quickSort($arr)); // 1, 2, 3, 4, 5, 6

6. 堆排序

堆排序使用了堆这种数据结构，它的思路是将待排序序列建成一个堆，然后将堆的根节点（最大或最小值）与最后一个节点交换，并把堆大小减一，并重新调整堆，重复这个过程直到堆大小为1。具体实现可以参考以下代码：

function heapSort(&$arr) {
    $len = count($arr);
    // 构建最大堆
    buildMaxHeap($arr);
    for ($i = $len - 1; $i > 0; $i--) {
        // 最大值（堆的根节点）与最后一个节点交换
        list($arr[0], $arr[$i]) = [$arr[$i], $arr[0]];
        // 调整堆
        adjustHeap($arr, 0, $i);
    }
    return $arr;
}

function buildMaxHeap(&$arr) {
    $len = count($arr);
    for ($i = intval($len / 2) - 1; $i >= 0; $i--) {
        adjustHeap($arr, $i, $len);
    }
}

function adjustHeap(&$arr, $i, $len) {
    $childIndex = $i * 2 + 1;
    $temp = $arr[$i];
    while ($childIndex < $len) {
        if ($childIndex + 1 < $len && $arr[$childIndex + 1] > $arr[$childIndex]) {
            $childIndex++;
        }
        if ($arr[$childIndex] > $temp) {
            $arr[$i] = $arr[$childIndex];
            $i = $childIndex;
            $childIndex = $i * 2 + 1;
        } else {
            break;
        }
    }
    $arr[$i] = $temp;
}

示例：

$arr = [5, 2, 4, 6, 1, 3];
echo implode(', ', heapSort($arr)); // 1, 2, 3, 4, 5, 6

以上就是对常见排序算法的 PHP 实现的详细讲解了。希望对您有所帮助！