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 实现的详细讲解了。希望对您有所帮助!

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:PHP 各种排序算法实现代码 - Python技术站

(0)
上一篇 2023年5月19日
下一篇 2023年5月19日

相关文章

  • php通过ksort()函数给关联数组按照键排序的方法

    如果需要将PHP关联数组按照键进行排序,可以使用ksort()函数。以下是使用ksort()函数给关联数组按照键排序的完整攻略: 第一步:创建一个关联数组 首先,创建一个包含多个元素的关联数组,这些元素都是键/值对。 $assoc_array = array( "name" => "John", "ag…

    算法与数据结构 2023年5月19日
    00
  • Python中利用sorted()函数排序的简单教程

    下面是我为您准备的Python中利用sorted()函数排序的简单教程。 1. sorted()函数的简介 sorted()函数是Python内置函数之一,用于对一个可迭代对象进行排序操作。这个函数返回一个新的列表,而不会修改原来的列表本身。 sorted()函数的基本语法如下所示: sorted(iterable, key=None, reverse=Fa…

    算法与数据结构 2023年5月19日
    00
  • JS实现数组按升序及降序排列的方法

    JS实现数组按升序和降序排列的方法有很多种,下面我将从简单到复杂分享几种方法。 sort()方法 sort()方法是JS的一个数组方法,可以对数组排序。它有一个可选的排序函数,用于规定排序规则。 升序排列: let arr = [3, 1, 4, 7, 2]; arr.sort((a, b) => a – b); console.log(arr); /…

    算法与数据结构 2023年5月19日
    00
  • 基于python进行桶排序与基数排序的总结

    基于python进行桶排序与基数排序的总结 桶排序 桶排序是一种稳定的排序算法,利用预先定义的桶按照一定的映射关系将待排序的元素分配到不同的桶中,并对每个桶中的元素进行排序,最后将所有桶中的结果合并起来即可。 具体的步骤如下: 找出待排序数组中的最大值max和最小值min,确定所需桶的数量,建立一个包含顺序桶的桶(列表)bucket和一个空列表result。…

    算法与数据结构 2023年5月19日
    00
  • 关于Python排序问题(冒泡/选择/插入)

    关于Python排序问题,一般包括冒泡排序、选择排序和插入排序。下面分别进行介绍。 冒泡排序 冒泡排序就是重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。重复地进行以上操作,直到没有可以交换的元素为止。 示例代码: def bubble_sort(arr): n = len(arr) for i in range(n-1): …

    算法与数据结构 2023年5月19日
    00
  • C/C++实现三路快速排序算法原理

    C/C++实现三路快速排序算法原理 算法概述 三路快速排序算法是一种优化版本的快速排序算法,能够处理含有大量重复元素的数组,避免了快速排序中大量递归处理相等元素的繁琐工作。 三路快速排序的原理是采用三个指针将数组分成小于、等于和大于三个部分,递归地向下快速排序,最终将整个数组排序。 实现步骤 首先选取数组中的一个元素作为标志物,通常是数组的第一个元素。 定义…

    算法与数据结构 2023年5月19日
    00
  • javascript冒泡排序小结

    JavaScript冒泡排序小结 什么是冒泡排序 冒泡排序是一种经典排序算法,它重复地走访过要排序的数列,每次比较相邻的两个元素,如果顺序不对则交换它们,直到没有需要交换的元素为止。 冒泡排序的步骤 冒泡排序的主要步骤如下: 比较相邻的元素。如果第一个比第二个大,就交换它们; 对每一对相邻的元素做同样的工作,从开始的第一对到结尾的最后一对,这样在最后的元素应…

    算法与数据结构 2023年5月19日
    00
  • 设计师灵感来源 细数上市公司LOGO背后的含义

    设计师灵感来源 作为设计师,找灵感是创作过程中的一项重要任务,而且好的设计往往都来自于深度的思考和充足的灵感。那么,设计师在哪里寻找灵感呢? 灵感来源 1. 观察 设计师可以通过观察日常生活中的事物来获取灵感,例如自然风光、建筑、图形等。观察中的选择与细节是关键,需要有敏锐的观察力和审美能力。 2. 学习 学习可以让设计师积累更多知识与思想,这也为他们提供了…

    算法与数据结构 2023年5月19日
    00
合作推广
合作推广
分享本页
返回顶部