【算法】php实现排序（一）

选择排序
方式：先让第一位与其他位比较大小找到最小的数字，然后是第二位与除第一位的其他位比较大小找出第二位，依此类推

$arr = [2,45,12,67,33,5,23,132,46];

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

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

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

            $tmp = $arr[$i];

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

            $arr[$j] = $tmp;

        }

    }

}

print_r($arr);

冒泡排序
方法：比较相邻两个位置的数据并进行排序
优化：添加字段 if_replace 判断该轮排序是否完成，如果完成则不再继续后面的排序

$arr = [2,45,12,67,33,5,23,132,46];

$if_replace = false;

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

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

        if($arr[$j] > $arr[$j+1]){

            $tmp = $arr[$j];

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

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

            $if_replace = true;

        }

    }

    if(!$if_replace){

        break;

    }

}

print_r($arr);

插入排序
方法：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

$arr = [2,45,12,67,33,5,23,132,46];

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

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

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

            $tmp = $arr[$j];

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

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

        }else{

            break;

        }

    }

}

print_r($arr);

希尔排序
方法：设待排序元素序列有n个元素，首先取一个整数increment（小于n）作为间隔将全部元素分为increment个子序列，
　　　所有距离为increment的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。
　　　然后缩小间隔increment，重复上述子序列划分和排序工作。直到最后取increment=1，将所有元素放在同一个子序列中排序为止。

$arr = [2,45,12,67,33,5,23,132,46];

$increment = count($arr);

do{

    $increment = floor($increment/3)+1;

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

        $k = 0;

        $j = $i;

        do{

            for ($m=$j+$increment; $m > 0; $m-=$increment) {

                if($arr[$m-$increment] > $arr[$m] && $arr[$m]){

                    $tmp = $arr[$m];

                    $arr[$m] = $arr[$m-$increment];

                    $arr[$m-$increment] = $tmp;

                }else{

                    break;

                }

            }

            $k++;

            $j = $i+($k*$increment);

        }while($j<count($arr));

    }

}while($increment > 1);

print_r($arr);

快速排序

方法：先从数列中取出一个数作为基准数，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边，依此操作直到各区间只有一个数

$arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];

function quickSort($arr)

{

    $count = count($arr);

    if ($count < 2) {

        return $arr;

    }

    $leftArray = $rightArray = array();

    $middle = $arr[0];// 基准值

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

        // 小于基准值，存入左边；大于基准值，存入右边

        if ($arr[$i] < $middle) {

            $leftArray[] = $arr[$i];

        } else {

            $rightArray[] = $arr[$i];

        }

    }

    $leftArray = quickSort($leftArray);

    $rightArray = quickSort($rightArray);

    return array_merge($leftArray, array($middle), $rightArray);

}

print_r(quickSort($arr));

巴特西

【算法】php实现排序（一）

最新文章

热门文章