php 排序算法(直接插入排序, 希尔排序, 冒泡排序及改进版1-2, 快速排序, 归并排序, 选择排序, 堆排序)

bubbleSort.class.php

<?php

/**
 * 排序名称:冒泡排序.
 * 
 * 说明:冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来.
 * 
 * 步骤：
 * 1 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 * 2 对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上。
 * 3 针对所有的元素重复以上的步骤，除了最后一个。
 * 4 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 *
 * @param array $arr
 *
 * @return array
 * 
 * @author liujingyu
 **/
function bubbleSort($arr) {

    $total = count($arr);

    for ($i = 0; $i < $total-1; $i++) {
        for ($j = 0; $j < $total-$i-1; $j++) {

            if ($arr[$j+1] < $arr[$j]) {
                list($arr[$j], $arr[$j+1]) = [$arr[$j+1], $arr[$j]];
            }
        }
    }

    return $arr;
}

/**
 * 冒泡排序改进版.
 *
 * @param array $arr
 *
 * @return array
 * 
 * @author liujingyu
 **/
function bubbleSortUpgrade($arr) {

    $total = count($arr);

    for ($i = 0; $i < $total-1; $i++) {

        $pos = $i;
        for ($j = $i; $j < $total; $j++) {

            if ($arr[$j] < $arr[$pos]) {
                $pos = $j;
            }
        }

        list($arr[$i], $arr[$pos]) = [$arr[$pos], $arr[$i]];
    }

    return $arr;
}

/**
 * 冒泡排序改进版.
 *
 * @param array $arr
 *
 * @return array
 * 
 * @author liujingyu
 **/
function bubbleSortUpgrade2($arr) {

    $high = count($arr) - 1;
    $low  = 0;

    while ($low < $high) {

        $pos = $high;
        for ($i = $low; $i < $high; $i++) {
            if ($arr[$pos] < $arr[$i]) {
                $pos = $i;
            }
        }
        list($arr[$high], $arr[$pos]) = [$arr[$pos], $arr[$high]];
        --$high;

        $pos = $low;
        for ($i = $high; $i > $low; $i--) {
            if ($arr[$pos] > $arr[$i]) {
                $pos = $i;
            }
        }
        list($arr[$low], $arr[$pos]) = [$arr[$pos], $arr[$low]];
        ++$low;
    }

    return $arr;
}

heapSort.class.php

<?php
/**
 * 排序名称:堆排序.
 * 说明：
 * 堆排序在 top K 问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的，虽然实质上还是一维数组.二叉堆是一个近似完全二叉树 .
 * 二叉堆具有以下性质：
 * 父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值.
 * 每个节点的左右子树都是一个二叉堆（都是最大堆或最小堆）.
 * 
 * 步骤：
 * 1 构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。
 * 2 堆排序（HeapSort）：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0...n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0...n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。
 * 3 最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点 .
 * 
 **/
function heap_sort($arr) {
    $n = count($arr);
    $first = intval($n/2 - 1);

    foreach (range($first, 0, -1) as $key) {
        max_heapify($arr, $key, $n - 1);
    }

    foreach (range($n-1, 0, -1) as $key) {
        list($arr[$key], $arr[0]) = [$arr[0], $arr[$key]];
        max_heapify($arr, 0, $key - 1);
    }

    return $arr;
}

function max_heapify(&$arr, $start, $end) {

    $root = $start;

    while (true)
    {
        $child = $root * 2 + 1;

        if ($child > $end) {
            break;
        }

        if ($child + 1 <= $end and $arr[$child] < $arr[$child + 1]) {
            $child += 1;
        }

        if ($arr[$root] < $arr[$child]) {
            list($arr[$root], $arr[$child]) = [$arr[$child], $arr[$root]];
            $root = $child;
        } else {
            break;
        }
    }
}

print_r(heap_sort([1, 3, 45, 3, 5]));

insertSort.class.php

<?php

/**
 * 排序名称:直接插入排序.
 * 
 * 说明:插入排序的工作原理是，对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入.
 * 
 * 步骤：
 * 1 从第一个元素开始，该元素可以认为已经被排序
 * 2 取出下一个元素，在已经排序的元素序列中从后向前扫描
 * 3 如果被扫描的元素（已排序）大于新元素，将该元素后移一位
 * 4 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
 * 5 将新元素插入到该位置后
 * 6 重复步骤2~5
 * 
 * 时间复杂度O(N^2）
 *
 * @param array $arr
 *
 * @return array
 * 
 * @author liujingyu
 **/
function insertSort($arr) {

    $total = count($arr);

    for ($i = 1; $i < $total; $i++) {

        if (true) {
            $min = $i;
            for ($j = $i -1; $j >= 0; $j--){
                if ($arr[$min] < $arr[$j]) {

                    list($arr[$min], $arr[$j]) = [$arr[$j], $arr[$min]];

                    $min = $j;
                }
            }
        } else {
            if ($i >= 1 and $arr[$i] < $arr[$i-1]) {

                $min = $arr[$i];

                $arr[$i] = $arr[$i-1];

                $j = $i-1;

                while ($j >= 0 and $min < $arr[$j]) {
                    $arr[$j+1] = $arr[$j];
                    $j--;
                }

                $arr[$j+1] = $min;
            }
        }
    }

    return $arr;
}

main.class.php

<?php

function main() {
    $arr = [49, 38, 65, 97, 76, 13, 27, 49];

    echo '直接插入排序'."\n";
    print_r(insertSort($arr));

    echo '希尔排序'."\n";
    print_r(shellSort($arr));

    echo '冒泡排序'."\n";
    print_r(bubbleSort($arr));

    echo '冒泡排序升级'."\n";
    print_r(bubbleSortUpgrade($arr));

    echo '冒泡排序升级2'."\n";
    print_r(bubbleSortUpgrade2($arr));

    echo '快排'."\n";
    print_r(quickSort($arr, 0, count($arr)-1));
}

main();

mergeSort.class.php

<?php
/**
 * 排序名称:归并排序.
 *
 * 说明:归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组.
 * 先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位.
 * 然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可.
 * 再考虑递归分解，基本思路是将数组分解成left和right，如果这两个数组内部数据是有序的，
 * 那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？
 * 可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可.
 * 
 * @param array $arr
 * 
 * @return array
 * 
 * @author liujingyu
 **/
function merge_sort($arr) {
    if (count($arr) <= 1) {
        return $arr;
    }

    $num = intval(count($arr)/2);
    $left = merge_sort(array_slice($arr, 0, $num));
    $right = merge_sort(array_slice($arr, $num));

    return merge($left, $right);
}

function merge($left, $right) {

    list($l, $r) = [0, 0];
    $result = [];

    while ($l < count($left) and $r < count($right)) {

        if ($left[$l] < $right[$r]) {
            array_push($result, $left[$l]);
            $l++;
        } else {
            array_push($result, $right[$r]);
            $r++;
        }
    }

    if ($l > $r) {
        $result = array_merge($result, array_slice($right, $r));
    } else {
        $result = array_merge($result, array_slice($left, $l));
    }

    return $result;
}

quickSort.class.php

<?php

/**
 * 排序名称:快排.
 *
 * 说明:
 * 快速排序通常明显比同为Ο(n log n)的其他算法更快，因此常被采用，
 * 而且快排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子.
 * 
 * 步骤：
 * 1 从数列中挑出一个元素作为基准数。
 * 2 分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边。
 * 3 再对左右区间递归执行第二步，直至各区间只有一个数。
 * 
 * @return void
 * 
 * @author liujingyu
 **/
function quickSort(&$arr, $low, $high) {

    if ($low < $high) {
        $privotLoc = partition($arr, $low, $high);
        quickSort($arr, $low, $privotLoc-1);
        quickSort($arr, $privotLoc+1, $high);
    }
    
    return $arr;
}

function partition(&$arr, $low, $high) {

    $privotKey = $arr[$low];

    while ($low < $high) {

        while ($low < $high and $arr[$high] >= $privotKey) {
            --$high;
        }
        list($arr[$low], $arr[$high]) = [$arr[$high], $arr[$low]];

        while ($low < $high and $arr[$low] <= $privotKey) {
            ++$low;
        }
        list($arr[$low], $arr[$high]) = [$arr[$high], $arr[$low]];
    }

    return [$arr, $low];
}

selectSort.class.php

<?php

function select_sort($arr) {

    $n = count($arr);

    foreach (range(0, $n-1) as $i) {
        $min = $i;
        foreach (range($i, $n-1) as $j) {
            if ($arr[$j] < $arr[$min]) {
                $min = $j;
            }
        }

        list($arr[$i], $arr[$min]) = [$arr[$min], $arr[$i]];
    }

    return $arr;
}

print_r(select_sort([1, 2, 3, 4,2,2]));

shellSort.class.php

<?php

/**
 * 排序名称:希尔排序.
 *
 * 说明: 希尔排序，也称递减增量排序算法，实质是分组插入排序。由 Donald Shell 于1959年提出。希尔排序是非稳定排序算法.
 * 希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行.
 * 最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序.
 * 
 * @param array $arr
 *
 * @return array
 * 
 * @author liujingyu
 **/
function shellSort($arr) {

    $dk = count($arr)/2;

    while ($dk >= 1) {
        $arr = shellInsertSort($arr, $dk);
        $dk /= 2;
    }

    return $arr;
}


/**
 * 希尔排序.
 * 直接插入排序
 *
 * @param array $arr
 * @param int   $dk
 *
 * @return array
 * 
 * @author liujingyu
 **/
function shellInsertSort($arr, $dk) {

    $total = count($arr);

    for ($i = 1; $i < $total; $i++) {
        if ($i >= $dk and $arr[$i] < $arr[$i-$dk]) {

            $base = $arr[$i];

            $arr[$i] = $arr[$i-$dk];

            $j = $i-$dk;

            while ($j >= 0 and $base < $arr[$j]) {
                $arr[$j+$dk] = $arr[$j];
                $j -= $dk;
            }

            $arr[$j+$dk] = $base;
        }
    }

    return $arr;
}

summary.txt

下面为七种经典排序算法指标对比情况：

method        avg         best         worst        space       steady

冒泡         O(n^2)       O(n)         O(n^2)       O(1)          Y
选择         O(n^2)       O(n^2)       O(n^2)       O(1)          N
插入         O(n^2)       O(n)         O(n^2)       O(1)          Y
希尔 O(nlogn) ~ O(n^2)   O(n^1.3)      O(n^2)       O(1)          N
堆          O(nlogn)     O(nlogn)      O(nlogn)     O(1)          N
归并        O(nlogn)     O(nlogn)      O(nlogn)     O(n)          Y
快排        O(nlogn)     O(nlogn)      O(n^2)     O(logn)~ O(n)   N