排序算法
Laiyong Wang Lv5
  1. 冒泡排序(将无序表中的所有记录,通过指针后移,其值不断的进行两两比较,大小不一则进行互换,得出升序序列或者降序序列)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    function swap(&$x, &$y) {
    $t = $x;
    $x = $y;
    $y = $t;
    }

    function bubble_sort(&$arr) {
    for ($i = 0; $i < count($arr) - 1; $i++)
    for ($j = 0; $j < count($arr) - 1 - $i; $j++)
    if ($arr[$j] > $arr[$j + 1])
    swap($arr[$j], $arr[$j + 1]);
    }
  2. 选择排序( n 个记录的无序表遍历 n-1 次,第 i 次从无序表中第 i 个记录开始,找出后序关键字中最小的记录,然后放置在第 i 的位置上)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    function selectionSort($arr)
    {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
    $minIndex = $i;
    for ($j = $i + 1; $j < $len; $j++) {
    if ($arr[$j] < $arr[$minIndex]) {
    $minIndex = $j;
    }
    }
    $temp = $arr[$i];
    $arr[$i] = $arr[$minIndex];
    $arr[$minIndex] = $temp;
    }
    return $arr;
    }
  3. 插入排序(重写,将数据按照一定的顺序一个一个的插入到有序的表,两两相比,大小不一就互换位置)

1
2
3
4
5
6
7
8
9
10
11
12
function insertionSort($arr)
{
$len = count($arr);
for ($i = 1; $i < $len; $i++) {
$preIndex = $i - 1;
while($preIndex >= 0 && $arr[$preIndex] > $arr[$preIndex + 1]) {
list($arr[$preIndex+1],$arr[$preIndex]) = [$arr[$preIndex],$arr[$preIndex+1]];
$preIndex--;
}
}
return $arr;
}
  1. 希尔排序 (其实就是另类的插入排序,先不断的分批小段(跳跃固定数量进行组合)进行插入排序,使得总体数据归于有序,最终所有的再一起排序,降低了时间复杂度)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    function shellSort($arr)
    {
    $len = count($arr);
    $temp = 0;
    $gap = 1;
    while($gap < $len / 3) {
    $gap = $gap * 3 + 1;
    }
    for ($gap; $gap > 0; $gap = floor($gap / 3)) {
    for ($i = $gap; $i < $len; $i++) {
    $temp = $arr[$i];
    for ($j = $i - $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap) {
    $arr[$j+$gap] = $arr[$j];
    }
    $arr[$j+$gap] = $temp;
    }
    }
    return $arr;
    }
  2. 基数排序(按照数学意义上的个十百千万来进行排序,实际写代码基本用不到)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    function radixSort($arr, $maxDigit = null)
    {
    if ($maxDigit === null) {
    $maxDigit = max($arr);
    }
    $counter = [];
    for ($i = 0; $i < $maxDigit; $i++) {
    for ($j = 0; $j < count($arr); $j++) {
    preg_match_all('/\d/', (string) $arr[$j], $matches);
    $numArr = $matches[0];
    $lenTmp = count($numArr);
    $bucket = array_key_exists($lenTmp - $i - 1, $numArr)
    ? intval($numArr[$lenTmp - $i - 1])
    : 0;
    if (!array_key_exists($bucket, $counter)) {
    $counter[$bucket] = [];
    }
    $counter[$bucket][] = $arr[$j];
    }
    $pos = 0;
    for ($j = 0; $j < count($counter); $j++) {
    $value = null;
    if ($counter[$j] !== null) {
    while (($value = array_shift($counter[$j])) !== null) {
    $arr[$pos++] = $value;
    }
    }
    }
    }

    return $arr;
    }
  3. 快速排序(基于比较的排序,每次选定一个数,将小于的放左边,大于的放右边,不断递归,最终就由小到大排序了)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    function quickSort($arr)
    {
    if (count($arr) <= 1)
    return $arr;
    $middle = $arr[0];
    $leftArray = array();
    $rightArray = array();

    for ($i = 1; $i < count($arr); $i++) {
    if ($arr[$i] > $middle)
    $rightArray[] = $arr[$i];
    else
    $leftArray[] = $arr[$i];
    }
    $leftArray = quickSort($leftArray);
    $leftArray[] = $middle;

    $rightArray = quickSort($rightArray);
    return array_merge($leftArray, $rightArray);
    }
  4. 记数排序
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    function countingSort($arr, $maxValue = null)
    {
    if ($maxValue === null) {
    $maxValue = max($arr);
    }
    for ($m = 0; $m < $maxValue + 1; $m++) {
    $bucket[] = null;
    }

    $arrLen = count($arr);
    for ($i = 0; $i < $arrLen; $i++) {
    if (!array_key_exists($arr[$i], $bucket)) {
    $bucket[$arr[$i]] = 0;
    }
    $bucket[$arr[$i]]++;
    }

    $sortedIndex = 0;
    foreach ($bucket as $key => $len) {

    if($len !== null){
    for($j = 0; $j < $len; $j++){
    $arr[$sortedIndex++] = $key;
    }
    }
    }

    return $arr;
    }
 Comments