吴耿龙

Web开发技术分享

首页 归档 标签 关于

PHP算法学习笔记

2015-12-02 5 min read

桶排序

申请同样大小的数组，遇见键值等于数值就数值就加1，然后数值是有多少就打印多少个键值，复杂度O(M+N)。

<?php
    $input = [5, 3, 5, 2, 8];    //待排序数组

    /*申请空间*/
    for ($i = 0; $i <= 10; $i++) {
        $arr[] = 0;
    }

    $count = count($input);   //记录数组的大小

    /*桶排序*/
    for ($i = 0; $i < $count; $i++) {
        $j = $input[$i];  //将每一个数记录到$j中
        $arr[$j]++;     //计数
    }


    /*输出*/
    for ($i = 10; $i >= 0; $i--) {
        for ($j = 1; $j <= $arr[$i]; $j++) {
            echo "$i\n";
        }
    }

冒泡排序

两两对比，位置错误就交换顺序，复杂度O(N²)。

<?php
    $input = [12, 35, 99, 18, 76];
    $count = count($input);
    for ($i = 0; $i <= $count; $i++) {        //外循环次数
        for ($j = 0; $j < $count - $i - 1; $j++) {   //内循环少一次
            $z = $j + 1;                        //往后一位对比，这就是内循环少一次的原因
            if ($input[$j] < $input[$z]) {      //前面一位小于后一位，则调换顺序
                $t = $input[$j];
                $input[$j] = $input[$z];
                $input[$z] = $t;
            }
        }
    }
    var_dump($input);

快速排序

选择一个基准元素，通常选择第一个元素或者最后一个元素。扫描一趟，将待排序列分成两部分，一部分小于基准元素小，一部分大于等于基准元素。此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分。

var $input = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8, 9];

public function run()
{
    $n = count($this->input);
    $this->quickSort(0, $n - 1);
}

public function quickSort($left, $right)
{
    if ($left > $right) {
        return;
    }
    $i = $left;
    $j = $right;

    $target = $this->input[$left];
    while ($i != $j) {
        //右指针开始
        if ($this->input[$j] >= $target && $i < $j) {
            $j--;
        }

        if ($this->input[$i] <= $target && $i < $j) {
            $i++;
        }

        //交换位置
        if ($i < $j) {
            $temp = $this->input[$i];
            $this->input[$i] = $this->input[$j];
            $this->input[$j] = $temp;
        }
    }

    //将判断的基数放到中间归为
    $this->input[$left] = $this->input[$i];
    $this->input[$i] = $target;

    $this->quickSort($left, $i - 1);
    $this->quickSort($i + 1, $right);

    return;
}

归并排序

归并排序：就是利用归并（合并）的思想实现的排序方法。它的原理是假设初始序列含有 n 个元素，则可以看成是 n 个有序的子序列，每个子序列的长度为 1，然后两两归并，得到 ⌈ n / 2⌉ （⌈ x ⌉ 表示不小于 x 的最小整数）个长度为 2 或 1 的有序序列；再两两归并，······，如此重复，直至得到一个长度为 n 的有序序列为止，这种排序方法就成为 2 路归并排序。

public function run()
{
    $array = [34, 5, 555, 14, 88, 5];
    $this->mergeSort($array, 0, count($array) - 1);
    var_dump($array);
}

public function mergeSort(array &$array, $left, $right)
{
    if ($left < $right) {
        $mid = ($left + $right) >> 1;
        $this->mergeSort($array, $left, $mid);
        $this->mergeSort($array, $mid + 1, $right);
        $this->merge($array, $left, $mid, $right);
    }
}

public function merge(array &$array, $left, $mid, $right)
{
    $i = $left;
    $j = $mid + 1;
    $k = $left;
    $temp = [];

    while ($i != $mid + 1 && $j != $right + 1) {
        if ($array[$i] >= $array[$j]) {
            $temp[$k++] = $array[$j++];
        } else {
            $temp[$k++] = $array[$i++];
        }
    }

    //将左边的剩余部分添加到temp数组中
    while ($i != $mid + 1) {
        $temp[$k++] = $array[$i++];
    }

    //将右边的剩余部分添加到temp数组中
    while ($j != $right + 1) {
        $temp[$k++] = $array[$j++];
    }

    //将临时数组覆盖到array
    for ($i = $left; $i <= $right; $i++) {
        $array[$i] = $temp[$i];
    }
}

二分查找算法

public function run()
{
    $array = [0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99];
    $result = $this->binarySearch($array, 99);
    var_dump($result);
}

public function binarySearch($array, $target)
{
    $length = count($array);
    $low = 0;
    $high = $length - 1;

    while ($low <= $high) {
        $mid = ($high + $low) >> 1;
        if ($target < $array[$mid]) {
            $high = $mid - 1;
        } elseif ($target > $array[$mid]) {
            $low = $mid + 1;
        } else {
            return $mid;
        }
    }

    return false;
}
RSS