排序算法(PHP实现)

冒泡排序

• 两两比较, 讲逆序的两个数交换位置

// 冒泡排序, 时间复杂度O(N^2)
for ($i = 0; $i < count($arr); $i++)
{
    for ($j = $i; $j < count($arr); $j++)
    {
        if ($arr[$i] > $arr[$j])
        {
            $temp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $temp;
        }
    }
}

快速排序

• 选择一个基准元素, 讲数组里的数与之比较, 区分出比之大的和比之小的两部分, 并分别对这两部分递归执行上述操作

/**
 * 选中数组中的某一值,比较将比该数大的放在右边,比该数小的放在左边,然后对左右两个数组继续执行上述操作
 * 时间复杂度 O(NlogN）
 */
public function quick_sort($arr)
{
    if (count($arr) < 2) return $arr;

    $left_arr = [];
    $right_arr = [];
    $key = $arr[0];
    // 从第二个数开始比较
    for ($i = 1; $i < count($arr); $i++)
    {
        if ($arr[$i] <= $key)
        {
            $left_arr[] = $arr[$i];
        }
        else
        {
            $right_arr[] = $arr[$i];
        }
    }
    $left_arr = $this->quick_sort($left_arr); //递归排序yuansu
    $right_arr = $this->quick_sort($right_arr);
    return array_merge($left_arr, [$key], $right_arr);
}

插入排序

• 选择一个要排序元素, 从该元素之前的最后一位开始比较, 如果逆序就插入到其前面

// 插入排序, 时间复杂度 O(N^2)
for ($i = 1; $i < count($arr); $i++)
{
    $temp = $arr[$i];
    for ($j = $i - 1; $j >= 0; $j--)
    {
        if ($arr[$j] > $temp)
        {
            $arr[$j + 1] = $arr[$j];
            $arr[$j] = $temp;
        }
        else
        {
            break;
        }
    }
}

选择排序

• 每次找到要排序数组的还未排序部分的最小值将之放在已排序部分的最后面

// 选择排序, 时间复杂度O(N^2)
for ($i = 0; $i < count($arr); $i++)
{
    $temp = $arr[$i];
    $index = $i;
    for ($j = $i; $j < count($arr); $j++)
    {
        if ($arr[$j] < $temp)
        {
            $index = $j;
        }
    }
    if ($i != $index)
    {
        $arr[$i] = $arr[$index];
        $arr[$index] = $temp;
    }
}