排序法【PHP】

1. 插入排序法

<?php
/**
 * 插入排序
 * 思路：从第二个数起，把当前数插入到前面已排好序的序列中
 * 算法复杂度：
 * 空间复杂度：原址操作
 * 时间复杂度：n^2
 * @param array $arr
 * @return array
 */
function InsertSort(Array $arr)
{
    if(empty($arr)) {
        return [];
    }
    $len =count($arr);
    for($i = 1; $i < $len; $i++) {
        $j = $i - 1;
        $tmp = $arr[$i];
        while ($tmp < $arr[$j] && $j > -1) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $tmp;
    }
    return $arr;
}

//测试
$arr = [8,32,12,35,66,77,2,4];
print_r(InsertSort($arr));
/**
 * output:
 * Array
(
[0] => 2
[1] => 4
[2] => 8
[3] => 12
[4] => 32
[5] => 35
[6] => 66
[7] => 77
)
 */

2. 归并排序法

<?php
/**
 * 归并排序法
 * 思路：分治法，核心算法在合， 即总的数组的排序可由两个已经排好序的子数组的合并得到。
 * 复杂度：
 * 空间复杂度：合并时需要额外两个子数组，O(n)
 * 时间复杂度：O(nlogn) 稳定排序法
 * @param $arr 数组
 * @param $start 初始下标
 * @param $end 结束下标
 */
function MergeSort(&$arr, $start, $end)
{
    if($start < $end) {
        $mid = (int)(($start + $end) / 2);
        MergeSort($arr, $start, $mid);
        MergeSort($arr, $mid + 1, $end);
        Merge($arr, $start, $mid, $end);
    }
}

/**
 * 合并两个子数组
 * @param $arr 数组
 * @param $start 初始下标
 * @param $mid  两个子数组的分割点
 * @param $end 结束下标
 */
function Merge(&$arr, $start, $mid, $end)
{
    $left = $right = [];
    for($i = $start; $i <= $mid; $i++) {
        $left[] = $arr[$i];
    }
    for($i = $mid+1; $i <= $end; $i++) {
        $right[] = $arr[$i];
    }
    $lenLeft = $mid - $start + 1;
    $lenRight = $end - $mid;
    $l = $r = 0;
    $j = $start;
    while ($l < $lenLeft && $r < $lenRight) {
        $arr[$j++] = $left[$l] < $right[$r] ? $left[$l++] : $right[$r++];
    }
    while ($l < $lenLeft) {
        $arr[$j++] = $left[$l++];
    }
    while ($r < $lenRight) {
        $arr[$j++] = $right[$r++];
    }
}

//测试
$arr = [8,32,12,35,66,77,2,4];
MergeSort($arr, 0, count($arr) - 1);
print_r($arr);

/**
 * output:
 * Array
(
[0] => 2
[1] => 4
[2] => 8
[3] => 12
[4] => 32
[5] => 35
[6] => 66
[7] => 77
)
 */

3. 快速排序

/**
 * 快速排序法
 * 思路：分治法，核心算法在分。总的数组的排序可以对子数组的排序得到，子数组的排序又可以由子子数组的排序得到...
 * 复杂度：
 * 空间复杂度：原址操作
 * 时间复杂度：平均 O(nlogn)，最差 n^2， 不稳定的排序法
 * @param $arr 数组
 * @param $start 初始下标
 * @param $end 结束下标
 */
function QuickSort(&$arr, $start, $end)
{
    if($start < $end) {
        $mid = Partition($arr, $start, $end);
        QuickSort($arr, $start, $mid - 1);
        QuickSort($arr, $mid + 1, $end);
    }
}

/**
 * 将数组分为两部分，小于基准数值的在左边， 大于基准数值的在右边，然后返回基准数值的位置
 * @param $arr
 * @param $start
 * @param $end
 */
function Partition(&$arr, $start, $end)
{
    $measure = $arr[$end]; //基准数值
    $p = $start - 1; //p用于表示小于基准数值的数的下标，比如有一个比基准数值小，那么该数下标为0，两个则是1，以此类推...
    for($i = $start; $i <= $end; $i++) {
        if($arr[$i] < $measure) {
            $tmp = $arr[$i];
            $arr[$i] = $arr[$p + 1];
            $arr[$p + 1] = $tmp;
            $p ++;
        }
    }
    $arr[$end] = $arr[$p + 1];
    $arr[$p + 1] = $measure;
    return $p + 1;
}

//测试
$arr = [8,32,12,35,66,77,2,4];
QuickSort($arr, 0, count($arr) - 1);
print_r($arr);

/**
 * output:
 * Array
(
[0] => 2
[1] => 4
[2] => 8
[3] => 12
[4] => 32
[5] => 35
[6] => 66
[7] => 77
)
 */

4. 堆排序

<?php
/**
 * 堆排序法
 * 思路：最大堆，将顶点（即最大值）放到最后，然后最剩下的再运行保持最大堆特性，然后在取最大值到倒数第二... 直到将所有节点值取出。
 * 复杂度：
 * 空间复杂度：原址操作
 * 时间复杂度：O(nlogn) 程序的空间局部性不好，不利于缓存，因为处理的数组元素都不是相邻的
 * @param $arr 数组
 */
function HeapSort(&$arr)
{
    $len = count($arr);
    BuildMaxHeap($arr, $len);
    for($i = $len - 1; $i > 0; $i--)
    {
        $tmp = $arr[$i];
        $arr[$i] = $arr[0];
        $arr[0] = $tmp;
        MaxHeapify($arr, 0, --$len);
    }
}

/**
 * 父节点下标
 * @param int $index
 * @return int
 */
function Parent($index)
{
    return (int)(($index - 1)/2);
}

/**
 * 左子节点下标
 * @param int $index
 * @return int
 */
function Left($index)
{
    return 2 * $index + 1;
}

/**
 * 右子节点下标
 * @param int $index
 * @return int
 */
function Right($index)
{
    return 2 * $index + 2;
}

/**
 * 保持最大堆的性质
 * @param array $arr
 * @param int $index 下标
 * @param int $len 数组长度
 */
function MaxHeapify(&$arr, $index, $len)
{
    $left = Left($index);
    $right = Right($index);
    $largest  = $index;
    if($left < $len && $arr[$left] > $arr[$index]) {
        $largest = $left;
    }
    if($right < $len && $arr[$right] > $arr[$largest]) {
        $largest = $right;
    }
    if($index != $largest) {
        $tmp = $arr[$index];
        $arr[$index] = $arr[$largest];
        $arr[$largest] = $tmp;
        MaxHeapify($arr, $largest, $len);
    }
}

/**
 * 建堆
 * @param array $arr
 * @param int $len 数组长度
 */
function BuildMaxHeap(&$arr, $len)
{
    $start = (int)($len/2) - 1;
    for($i = $start; $i >= 0; $i--) {
        MaxHeapify($arr, $i, $len);
    }
}


//测试
$arr = [8,32,12,35,66,77,2,4];
HeapSort($arr);
print_r($arr);

/**
 * output:
 * Array
(
[0] => 2
[1] => 4
[2] => 8
[3] => 12
[4] => 32
[5] => 35
[6] => 66
[7] => 77
)
 */