好久没更博客了, 最近一直在学排序, 这东西有点烧脑

对于很多刚刚起步的程序员来说, 排序一直是比较头疼的一块, 因为它很好理解, 但是写起来却能折磨死你. 其它看起来很难的程序, 其实写起来非常简单. 但是排序是看起来非常简单, 你讲给一个十岁的小孩听, 估计都能听懂, 但是转换成代码你就是不会. 算法也是很多考试中必考的, 例如快速排序

因为最近在学 PHP, 所以就直接用 PHP 写排序算法了, 下面包含几乎所有的热门排序, 当然可能没有更新完, 因为到目前为止, 我只是学了几种排序算法. 我自己写的排序有点我自己的想法在里面, 所以和网上呈现的或者书中呈现的可能有所不同, 可能并不是完全按照排序的严格定义来写的, 但是大致都是按照排序的特点来写的

下面直接给出排序的代码, 之后会有专门的课程讲排序

Sort.php :

<?php

#冒泡排序

function bubbleSort(&$arr) {

    $len = count($arr);

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

        for($j = $len - 1; $j > 0; $j--) {

            if($arr[$j] < $arr[$j - 1]) {

                $temp = $arr[$j];

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

                $arr[$j - 1] = $temp;

            }

        }

    }

}

#直接插入排序

function insertSort(&$arr) {

    $len = count($arr);

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

        $R = $arr[$i];

        for($j = $i - 1; $j >= 0; $j--) {

            if($arr[$j] > $R) {

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

            }else {

                break;

            }

        $arr[$j] = $R;

        }

    }

}

#折半插入排序

function binInsertSort(&$arr) {

    $len = count($arr);

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

        $low = 0;

        $high = $i;

        $R = $arr[$i + 1];

        while($low <= $high) {

            $mid = (int)(($high + $low) / 2);

            if($R > $arr[$mid]) {

                $low = $mid + 1;

            }else {

        $high = $mid - 1;

    }

}

    for($j = $i; $j >= $low; $j--) {

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

    }

    $arr[$low] = $R;

    }

}

#希尔排序

function shellSort(&$arr) {

    $len = count($arr);

    $gap = (int)($len / 2);

    while($gap >= 1) {

        for($i = $gap; $i < $len; $i++) {

            for($j = $i; $j >= 0 and $j - $gap >= 0; $j -= $gap) {

                if($arr[$j] < $arr[$j - $gap]) {

                    $temp = $arr[$j];

                    $arr[$j] = $arr[$j - $gap];

                    $arr[$j - $gap] = $temp;

                }else {

                    break;

                }

            }

        }

        $gap = intval($gap / 2);

    }

}

#快速排序

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

    $R = $arr[$low];

    $arr[$low] = NULL;#使备份元素对应的位置为空, 方便之后交换

    while($low != $high) {

        if($arr[$high] < $R and $arr[$high] != null) {

            $arr[$low] = $arr[$high];

            $arr[$high] = NULL;

        }

        if($arr[$low] > $R and $arr[$low] != null) {

            $arr[$high] = $arr[$low];

            $arr[$low] = NULL;

        }

        if($arr[$high] == null) {

            $low++;

        }else {

            $high--;

        }

    }

    $flag = $low;

    $arr[$flag] = $R;

    return $flag;

}

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

    if($low < $high) {

        $flag = firstQuickSort($arr, $low, $high);#划分数组

        if($flag != 0) {

            quickSort($arr, $low, $flag - 1);

        }

        if($flag != count($arr) - 1){

            quickSort($arr, $flag + 1, $high);

        }

    }

}

#简单选择排序

function simpleSelectSort(&$arr) {

    $len = count($arr);

    for($i = 0; $i < $len - 1; $i++) { $min = $i; for($j = $len - 1; $j > $i; $j--) {

            if($arr[$j] < $arr[$min]) {

                $min = $j;

            }

        }

        $swap = $arr[$min];

        $arr[$min] = $arr[$i];

        $arr[$i] = $swap;

    }

}

#树形选择排序

function treeSelectSort(&$arr) {

    $len = count($arr);

    $j = 0;

    for($i = 0; $i < $len; $i++) {

        $arrS = $arr;

        while(count($arrS) != 1) {

            $arrS = treeSelectMin($arrS);

        }

        for($j = 0; $j < $len; $j++) {

            if($arr[$j] == $arrS[0]) {

                $arr[$j] = NULL;

                break;

            }

        }

        $arrR[$i] = $arrS[0];

    }

    $arr = $arrR;

}

function treeSelectMin($arr) {

    $len = count($arr);

    $j = 0;

    for($i = 0; $i < $len; $i += 2) {

        if($i == $len - 1) {

            $arrS[$j] = $arr[$i];

            break;

        }

        if($arr[$i] == null and $arr[$i + 1] == null) {

            continue;

        }

        if($arr[$i] == null and $arr[$i + 1] != null) {

            $arrS[$j] = $arr[$i + 1];

            $j++;

            continue;

        }

        if($arr[$i] != null and $arr[$i + 1] == null) {

            $arrS[$j] = $arr[$i];

            $j++;

            continue;

        }

        if($arr[$i] < $arr[$i + 1]) {

                $arrS[$j] = $arr[$i];

        }else {

                $arrS[$j] = $arr[$i + 1];

        }

        $j++;

    }

    return $arrS;

}

#堆排序

function heapSort(&$arr) {

    $len = count($arr);

    while($len != 0) {

        for($i = 0; $i + 2 < $len; $i++) {

            $max = $i;

            for($j = ($i + 1) * 2 - 1; $j <= ($i + 1) * 2; $j++) { if($j >= $len) {

                    break;

                }

                if($arr[$j] > $arr[$max]) {

                    $max = $j;

                }

            }

            if($i != $max) {

                $swap = $arr[$i];

                $arr[$i] = $arr[$max];

                $arr[$max] = $swap;

                if($i != 0) {

                    $i = -1;

                }

            }

        }

        if($len > 2) {

            $swap = $arr[0];

            $arr[0] = $arr[$len - 1];

            $arr[$len - 1] = $swap;

        }

        if($len == 2) {

            if($arr[0] > $arr[1]) {

                $swap = $arr[0];

                $arr[0] = $arr[1];

                $arr[1] = $swap;

            }

        }

        $len--;

    }

}

#归并排序

function mergeSort(&$arr) {

    $len = count($arr);

    $gap = ceil($len / 2);

    $add = 2;

    while($gap > 0) {

        if($gap == 1) {

            $arr = oneMergeSort($arr, $add);

            break;

        }else {

            $arr = oneMergeSort($arr, $add);

        }

        if($gap / 2 == 1) {

            $gap = 1;

        }else {

            $gap = ceil($gap / 2);

        }

        $add *= 2;

    }

}

function oneMergeSort($arr, $add) {

    $len = count($arr);

    $l = 0;

    for($i = 0; $i < $len; $i += $add) {

        $low = $i;

        $mid = (2 * $i + $add) / 2;

        $high = $i + $add;

        $cnt = 0;

        $arrA = array();

        for($j = $low; $j < $mid and $j < $len; $j++) {

            $arrA[$cnt] = $arr[$j];

            $cnt++;

        }

        $cnt = 0;

        $arrB = array();

        for($j = $mid; $j < $high and $j < $len; $j++) {

            $arrB[$cnt] = $arr[$j];

            $cnt++;

        }

        if(count($arrB) == 0) {

            for($h = 0; $h < count($arrA); $h++) {

                $arrS[$l] = $arrA[$h];

                $l++;

            }

            break;

        }

        $flagB = 0;

        for($j = 0; $j < count($arrA); $j++) {

            for($k = $flagB; $k < count($arrB); $k++) {

                if($arrA[$j] < $arrB[$k]) { $arrS[$l] = $arrA[$j]; $l++; break; }else { $arrS[$l] = $arrB[$k]; $l++; $flagB++; } } if($k >= count($arrB)) {

                break;

            }

        }

        if($j < count($arrA) and $k >= count($arrB)) {

            for($h = $j; $h < count($arrA); $h++) { $arrS[$l] = $arrA[$h]; $l++; } } if($j >= count($arrA) and $k < count($arrB)) {

            for($h = $k; $h < count($arrB); $h++) {

                $arrS[$l] = $arrB[$h];

                $l++;

            }

        }

    }

    return $arrS;

}

#链式基数排序

function chainedRadixSort(&$arr) {

    $gap = gapCal($arr);

    $time = 1;

    for($i = 1; $i <= $gap; $i++) { $arrS = array( 0 => array(),

            1 => array(),

            2 => array(),

            3 => array(),

            4 => array(),

            5 => array(),

            6 => array(),

            7 => array(),

            8 => array(),

            9 => array()

        );

        for($j = 0; $j < count($arr); $j++) {

            switch($flag = numCal($arr[$j], $time)) {

                case 0 :

                    $arrS[0][count($arrS[0])] = $arr[$j];

                    break;

                case 1 :

                    $arrS[1][count($arrS[1])] = $arr[$j];

                    break;

                case 2 :

                    $arrS[2][count($arrS[2])] = $arr[$j];

                    break;

                case 3 :

                    $arrS[3][count($arrS[3])] = $arr[$j];

                    break;

                case 4 :

                    $arrS[4][count($arrS[4])] = $arr[$j];

                    break;

                case 5 :

                    $arrS[5][count($arrS[5])] = $arr[$j];

                    break;

                case 6 :

                    $arrS[6][count($arrS[6])] = $arr[$j];

                    break;

                case 7 :

                    $arrS[7][count($arrS[7])] = $arr[$j];

                    break;

                case 8 :

                    $arrS[8][count($arrS[8])] = $arr[$j];

                    break;

                case 9 :

                    $arrS[9][count($arrS[9])] = $arr[$j];

                    break;

            }

        }

        $l = 0;

        for($k = 0; $k < 10; $k++) {

            if(count($arrS[$k]) != 0) {

                for($h = 0; $h < count($arrS[$k]); $h++) { $arrX[$l] = $arrS[$k][$h]; $l++; } } } $arr = $arrX; $time++; } } function numCal($num, $time) { if($time > 1) {

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

            $num /= 10;

        }

        $flag = $num % 10;

    }else {

        $flag = $num % 10;

    }

    return $flag;

}

function gapCal($arr) {

    $max = 0;

    for($i = 1; $i < count($arr); $i++) { if($arr[$i] > $arr[$max]) {

            $max = $i;

        }

    }

    $num = $arr[$max];

    $gap = 0;

    do {

        $gap++;

        $num /= 10;

    }while($num > 1);

    return $gap;

}

?>