Skip to main content

经典排序算法

一、冒泡排序

思路:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 [1]

代码:

<?php
$arr = [1, 3, 6, 87, 8, 9, 23];
function BubbleSort($arr)
{
    $cnt = count($arr);
    for ($i = 0; $i < $cnt; $i++) {
        for ($j = $i + 1; $j < $cnt; $j++) {
            if ($arr[$i] > $arr[$j]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$i];
                $arr[$i] = $tmp;
            }
        }
    }
    return $arr;
}

var_dump(BubbleSort($arr));

二、快速排序

思路:

到当前数组中的任意一个元素(一般选择第一个元素),作为标准,新建两个空数组,遍历整个数组元素,

如果遍历到的元素比当前的元素要小,那么就放到左边的数组,否则放到右面的数组,然后再对新数组进行同样的操作,

不难发现,这里符合递归的原理,所以我们可以用递归来实现。

递归点:如果数组的元素大于1,就需要再进行分解,所以我们的递归点就是新构造的数组元素个数大于1

递归出口:我们什么时候不需要再对新数组不进行排序了呢?就是当数组元素个数变成1的时候,所以这就是我们的出口。

代码:

<?php
$arr = [1, 3, 6, 87, 8, 9, 23];
function quick($arr)
{
    $cnt = count($arr);
    if ($cnt <= 1) return $arr;
    $index = $arr[0];
    $left = $right = array();
    for ($i = 1; $i < $cnt; $i++) {
        if ($index >= $arr[$i]) {
            $left[] = $arr{$i};
        } else {
            $right[] = $arr{$i};
        }
    }
    $arrLeft = quick($left);
    $arrRight = quick($right);
    return array_merge(
        $arrLeft,
        [$index],
        $arrRight
    );
}

var_dump(quick($arr));

 

三、选择排序

思路:

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

代码如下:

<?php
$arr = [1, 3, 6, 87, 8, 9, 23];
function selectSort($arr)
{
    $cnt = count($arr);
    for ($i = $cnt - 1; $i > 0; $i--) {
        $pos = $i;//假设的基准点
        for ($j = 0; $j < $i; $j++) {
            if ($arr[$j] > $arr[$pos]) {
                $pos = $j;
            }
        }
        if ($pos != $i) {
            $tmp = $arr[$pos];
            $arr[$pos] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
    return $arr;
}

var_dump(selectSort($arr));

 

四、插入排序

思路:

每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。

代码:

<?php
$arr = [1, 3, 6, 87, 8, 9, 23];
function insertSort($arr)
{
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) { //从第二个元素开始插入
        for ($j = $i - 1; $j >= 0; $j--) { //与前面的数比较,找到插入的位置
            if ($arr[$j] > $arr[$j + 1]) { //比前面的数小,交换位置
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $tmp;
            } else { //大于或等于前面的数,表示已找到插入的位置
                break;
            }
        }
    }
    return $arr;
}

var_dump(insertSort($arr));

 

五、二分法查找

思路:二分法查找适用于数据量较大时,但是数据需要先排好顺序。

<?php
$arr = [1, 3, 6, 87, 8, 9, 23];
function search($arr, $val)
{
    $max = count($arr) - 1;
    $min = 0;
    while ($min <= $max) {
        $mid = intval(($max + $min) / 2);
        if ($val == $arr[$mid]) return $mid;
        if ($val > $arr[$mid]) $max = $mid - 1;
        if ($val < $arr[$mid]) $max = $mid + 1;
    }
    return false;
}

var_dump(search($arr, 65));

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

+ 63 = 65