php 冒泡排序，插入排序，快速排序，计数排序，反转链表

女爷i 2022-12-29 00:18 111阅读 0赞

# 冒泡排序，插入排序，快速排序，计数排序。反转链表 #

## 1.冒泡排序 ##

复杂度o(n²),稳定排序，原地排序不需要额外空间  
从第一个数据和下一个数据比较，如果第一个大于第二个，进行交换。以此类推

$arr = ['1', '5', '6', '3', '2', '4', '4', '7', '8', '2'];
     for ($i = 0; $i <= count($arr); $i++) {
            for ($j = 0; $j <= 5 - $i - 1; $j++) {
                if ($arr[$j] > $arr[$j + 1]) {
                    $v = $arr[$j + 1];
                    $arr[$j + 1] = $arr[$j];
                    $arr[$j] = $v;
                }
            }
        }

## 2.插入排序 ##

插入排序，复杂度o(n²),稳定排序，原地排序不需要额外空间，比冒泡排序少两次赋值。  
从第二个数据作比较，第一个数据大于第二个数据，第一个数据下标后移，依次前推。最后把第二个值赋值到第一个值上

$arr = ['1', '5', '6', '3', '2', '4', '4', '7', '8', '2'];
    for ($i = 1; $i < count($arr); $i++) {
            $value = $arr[$i];//当前比较的值
            $j = $i - 1;//上一个值
            for (; $j >= 0; $j--) {//循环，下标不会小于0
                if ($arr[$j] > $value) {
                    $arr[$j + 1] = $arr[$j];
                } else {//前面的值都排好了，无需判断到最前面
                    break;
                }
            }
            $arr[$j + 1] = $value;//当前比较值赋值
        }

## 3.快速排序 ##

复杂度o(nlogn),不稳定排序，原地排序不需要额外空间，  
需要递归，每次取数组最后一个值（哨兵值），从头遍历，如果当前值小于哨兵值，讲当前值插入到最左面，大于哨兵值在最右面，依次类推。

demo2，游标sign对应的值不关心，他只是个分界线，游标前面都是小于哨兵值，遍历到当前值大于哨兵值的，游标值和当前值进行交换。当遍历完成，把哨兵值放在游标位置上。

$arr = ['1', '5', '6', '3', '2', '4', '4', '7', '8', '2'];
    $this->demo($arr, 0, count($arr));
    
    public function demo(&$arr, $top, $last)
     {
            if ($top >= $last) {
                return $arr;
            }
            $q = $this->demo2($arr, $top, $last);
            $this->demo($arr, $top, $q);
            $this->demo($arr, $q + 1, $last);
     }
    
    public function demo2(&$arr, $top, $last)
    {
        $tmp_value = $arr[$last - 1];//比较值
        $sign = $top;//游标
        for ($i = $sign; $i < $last - 1; $i++) {//当前值
            if ($arr[$i] < $tmp_value) {//当前值小于哨兵值
                $tmp = $arr[$sign];//当前值于游标值进行交换
                $arr[$sign] = $arr[$i];
                $arr[$i] = $tmp;
                $sign++;
            }
        }
        //哨兵值放在游标值上
        $tmp = $arr[$sign];
        $arr[$sign] = $tmp_value;
        $arr[$last - 1] = $tmp;
        return $sign;
    }

## 4.计数排序 ##

复杂度o(n+k),不稳定排序，需要额外空间。获得数组的最大值和最小值，新建一个数组，扫描原数组每个元素出现此次，统计到新数组。遍历新数组，根据下标递增重写原数组

$arr = ['1', '3', '4', '2', '1', '7', '6', '4', '8', '3', '8', '4'];
        $max = $min = $arr[0];
        for ($i = 1; $i < count($arr); $i++) {//获得最大最小数组
            if ($arr[$i] > $max) {
                $max = $arr[$i];
            }
            if ($arr[$i] < $min) {
                $min = $arr[$i];
            }
        }
        $new_array = [];
        for ($i = $min; $i <= $max; $i++) {//新数组下标为原数组值，新数组值初始为0
            $new_array[$i] = 0;
        }
        foreach ($arr as $number) {//原数组每有一个数，新数组值加一
            $new_array[$number]++;
        }
        $j = 0;
        for ($i = $min; $i <= $max; $i++) {
            while ($new_array[$i]-- > 0) {
                $arr[$j++] = $i;//重新写原数组
            }
        }

## 5.链表反转 ##