排序

时间复杂度

冒泡排序

依次比较相邻的两个数，将较大的数往上冒泡，每一轮冒出一个数字，直到排序完成

时间复杂度 O(n^2) 空间复杂度 O(1)

class BubbleSort
{
    public function sort($data)
    {
        $count = count($data);

        for ($i = 0; $i < $count - 1; $i++) {
            for ($j = 0; $j < $count - 1 - $i; $j++) {
                if ($data[$j] > $data[$j + 1]) {
                    $temp = $data[$j];
                    $data[$j] = $data[$j + 1];
                    $data[$j + 1] = $temp;
                }
            }
        }

        return $data;

    }
}

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

$res = (new BubbleSort())->sort($arr);

print_r($res);

选择排序

每一轮选出一个最小的数字，直到排序完成

时间复杂度 O(n^2) 空间复杂度 O(1)

class SelectSort
{
    public function sort($data)
    {
        $count = count($data);

        for ($i = 0; $i < $count - 1; $i++) {
            $minIndex = $i;
            for ($j = $i + 1; $j < $count; $j++) {
                if ($data[$i] > $data[$j]) {
                    $minIndex = $j;
                }
            }

            if ($minIndex != $i) {
                $temp = $data[$i];
                $data[$i] = $data[$minIndex];
                $data[$minIndex] = $temp;
            }
        }

        return $data;
    }
}


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

$res = (new SelectSort())->sort($arr);


print_r($res);

插入排序

从左到右比较相邻的数，如果左边小于右边，本轮结束

反之，交换两数，继续往左边反向比较，直到左边的数小于右边，本轮结束

然后继续往右边比较，重复上述动作，直到排序完成

时间复杂度 O(n^2) 空间复杂度 O(1)

class InsertSort
{
    public function sort($data)
    {
        $count = count($data);

        for ($i = 0; $i < $count - 1; $i++) {
            for ($j = $i + 1; $j > 0; $j--) {
                if ($data[$j - 1] > $data[$j]) {
                    $temp = $data[$j - 1];
                    $data[$j - 1] = $data[$j];
                    $data[$j] = $temp;
                } else {
                    break;
                }
            }
        }

        return $data;
    }
}


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

$res = (new InsertSort())->sort($arr);

print_r($res);

快速排序

快速排序使用分治的思想，先取第一个数作为基准数，然后循环剩余的数与基准数比较

大于基准数的放右边，小于基准数的放左边，然后递归左右两边的数组以同样的方法处理

最后合并所有排序好的小数组

时间复杂度 O(nlogn) 如果每次基准数都是最小或最大，递归深度会变深，最终退化成 O(n^2)

空间复杂度 O(logn) 跟时间复杂度一样，最坏的情况会退化成 O(n)

class QuickSort
{

    public function sort($data)
    {
        $count = count($data);
        if ($count <= 1) {
            return $data;
        }

        $middle = $data[0];
        $left = [];
        $right = [];

        for ($i = 1; $i < $count; $i++) {
            if ($data[$i] > $middle) {
                $right[] = $data[$i];
            } else {
                $left[] = $data[$i];
            }
        }

        return array_merge($this->sort($left), [$middle], $this->sort($right));
    }

}

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

$res = (new QuickSort())->sort($arr);

print_r($res);

归并排序

归并排序使用分治的思想，每次拆分数组的一半进行递归，直至数组中只剩一个元素后返回

将拆分后的数组排序后向上返回

归并排序比快速排序更稳定，因为每次都是拆分数组的一半进行递归，但是需要开辟更多的内存空间

时间复杂度 O(nlogn) 空间复杂度 O(n) 排序过程中需要一个临时存储空间保存合并序列

class MergeSort
{
    public function sort($data)
    {
        $count = count($data);

        if ($count <= 1) {
            return $data;
        }

        $middle = intval($count / 2);

        $left = array_slice($data, 0, $middle);
        $right = array_slice($data, $middle);

        $left = $this->sort($left);
        $right = $this->sort($right);

        return $this->merge($left, $right);
    }

    protected function merge($left, $right)
    {
        $minArr = [];

        while (count($left) && count($right)) {
            $minArr [] = $left[0] > $right[0] ? array_shift($right) : array_shift($left);
        }

        return array_merge($minArr, $left, $right);
    }
}

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

$res = (new MergeSort())->sort($arr);

print_r($res);

堆排序

TODO 优化 使用堆排序，不是堆结构排序

$heap = new Heap();

$arr = [6, 77, 8, 4, 5, 6, 7, 8, 9];

foreach ($arr as $v) {
    $heap->insert($v);
}

$sortArr = [];
while (true) {
    $value = $heap->pop();

    if ($value === null) {
        break;
    }

    $sortArr[] = $value;

}

print_r($sortArr);