专栏首页PHP修行之路【算法】php实现排序(一)

【算法】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));

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • nginx代理(正向代理和反向代理)

      是一个位于客户端和原始服务器(origin server)之间的服务器,为了从原始服务器取得内容,客户端向代理发送一个请求并指定目标(原始服务器),然后代理...

    码缘
  • 【多进程】php多进程编程

    php实现多进程需要安装pcntl模块,这个模块是php官方提供的,所以我们可以在PHP源码中找到,下载 php7.3.7 源码并解压到 /home 目录下,...

    码缘
  • php json_encode()函数返回对象和数组问题

    php json_encode() 函数格式化数据时会根据不同的数组类型格式化不同类型的json数据

    码缘
  • 快速排序(quick sort)C++实现

    每次选一个轴pivot(我选数组的第一个元素arr[p]),遍历其余数组元素使得比arr[p]大的数都在arr[p]的右边,比arr[p]小的数都在arr[p]...

    kalifa_lau
  • 常用算法比较,js实现

    <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> <style>...

    前朝楚水
  • 排序算法之选择排序-java版

    选择排序类似于冒泡排序,均属于内排,也可以看做是对冒泡排序的优化。因为冒泡排序是比较相邻的两个值,然后直接交换。而选择排序是找到一个最大值或者最小值之后,再进行...

    shengjk1
  • JavaScript数组排序总结

    将数组中的相邻两个元素进行比较,将比较大(较小)的数通过两两比较移动到数组末尾(开始),执行一遍内层循环,确定一个最大(最小)的数,外层循环从数组末尾(开始)遍...

    用户4831957
  • 选择排序

    选择排序的思想,每次从剩余元素中最小的元素与当前元素交换,第一次从arr[0]arr[n-1]中选取最小值,与arr[0]交换;第二次从arr[1]arr[n-...

    桑鱼
  • JavaScript实现八大内部排序算法

    ? 注:基数排序中:r是关键字的基数,d是长度,n是关键字的个数 1.插入排序 基本思想:在序号i之前的元素(0到i-1)已经排好序,本趟需要找到i对应的元素...

    用户1149564
  • 快速排序

    参考:http://www.cnblogs.com/skywang12345/p/3596746.html  下面上代码: #include<iostream>...

    xcywt

扫码关注云+社区

领取腾讯云代金券