常用排序算法的核心代码-ag捕鱼王app官网

在《常用排序算法》这篇文章中我们大概介绍了各种排序算法的思想和实现步骤。本篇我将这几种排序算法的核心代码奉献给大家。

所有排序算法的完整代码在github上， 。

1. 直接插入排序

下面是封装的直接插入排序的函数

function insertsort(&$arr){
    for($i=1;$i         $p = $arr[$i];
        for($j=$i-1;$j>=0;$j--){
            if($arr[$j]>$p){
                $arr[$j 1] = $arr[$j];
            }else{
                break;
            }
        }
        $arr[$j 1] = $p;
    }
}

2. 折半插入排序

下面是封装的折半插入排序的函数

function halfinsertsort(&$arr){
    for($i=1;$i         if($arr[$i]<$arr[$i-1]){
            //使用二分查找法查找适当的位置
            $low = 0;
            $high = $i-1;
            $pos = floor(($low $high)/2);
            $key = $arr[$i];
            while($low<$high){
                if($arr[$pos]>$key){
                    $high = $pos-1;
                }elseif($arr[$pos]<=$key){
                    $low = $pos 1;
                }
                $pos = ceil(($low $high)/2);
            }
            //二分查找法结束
            if($arr[$pos]>$arr[$i]){
                $pos = $pos-1;
            }
            for($j=$i-1;$j>$pos;$j--){
                $arr[$j 1]=$arr[$j];
            }
            $arr[$j 1] = $key;
        }
    }
}

3. 表插入排序

下面是封装的表插入排序的函数

function tableinsertsort(&$arr,&$link){
    $link[0]=array('next'=>1);//初始化链表  $link第一个元素仅仅作为头部
    $link[1]=array('next'=>0); //将第一个元素放入$link
    /*
     * 开始遍历数组 从第二个元素开始
    */
    for($i=2;$i<=count($arr);$i ){
        $p = $arr[$i]; //存储当前待排序的元素
        $index =0;
        $next = 1;  //从开始位置查找链表
        while($next!=0){
            if($arr[$next]['age']<$p['age']){
                $index = $next;
                $next = $link[$next]['next'];
            }
            else break;
        }
        if($next == 0){
            $link[$i]['next'] = 0;
            $link[$index]['next'] = $i;
        }else{
            $link[$i]['next']=$next;
            $link[$index]['next']=$i;
        }
    }
}

4.希尔排序

下面是封装的希尔排序的函数

function shellsort(&$arr){
    /*
     * 首先初始化 增量  数组长度/2 取整 floor() 函数向下取整  对于增量每次循环都由 当前增量/2
     */
    for($dl=floor(count($arr)/2);$dl>=1;$dl=floor($dl/2)){
        /*
         * 每次从 增量的位置开始，直到数组递增变量达到数组的长度
         */
        for($j=$dl;$j             for($i=$j-$dl;$i>=0;$i-=$dl){
                if($arr[$i $dl]<$arr[$i]){
                    $temp = $arr[$i $dl];
                    $arr[$i $dl]=$arr[$i];
                    $arr[$i]=$temp;
                }
            }
        }
    }
}

5.归并排序

下面是归并排序的递归实现

function mergesortrecurse(&$arr,$l,$r){
    if($r <= $l) return ;
    $m = floor(($l $r)/2);
    mergesort($arr,$l,$m);
    mergesort($arr,$m 1,$r);
    $arr = merge($arr,$l,$m,$r);
}

下面是归并排序的非递归方式的实现

function mergesort(&$arr){
    $stack = array();
    $stack1 = array();
    $temp = array(0,count($arr)-1,floor((0 count($arr)-1)/2));
    array_push($stack,$temp);
    while(count($stack)>0){
        $temp = array_pop($stack);
        array_push($stack1,$temp);
        if($temp[0]<$temp[2]){
            array_push($stack,array($temp[0],$temp[2],floor(($temp[0] $temp[2])/2)));
        }
        if($temp[2] 1<$temp[1]){
            array_push($stack,array($temp[2] 1,$temp[1],floor(($temp[2] 1 $temp[1])/2)));
        }
    }
    while(count($stack1)>0){
        $temp = array_pop($stack1);
        $arr = merge($arr,$temp[0], $temp[2], $temp[1]);
    }
}

6. 快速排序

下面是快速排序的递归方式的实现

function fastsortrecurse(&$arr,$s,$e){
    if($s>=$e) return ;
    $nextp = findpiv($arr,$s,$e);  //找到下一个基准所在位置
    fastsortrecurse($arr,$s,$nextp-1);
    fastsortrecurse($arr,$nextp 1,$e);
}

下面是快速排序的非递归方式的实现

function fastsort(&$arr){
    $stack = array();
    array_push($stack,array(0,count($arr)-1));
    while(count($stack)>0){
        $temp = array_pop($stack);
        $p = findpiv($arr, $temp[0], $temp[1]);
        if($p 1<$temp[1]) array_push($stack,array($p 1,$temp[1]));
        if($temp[0]<$p-1) array_push($stack,array($temp[0],$p-1));
    }
}

7. 堆排序

下面是封装的堆排序的函数——其实现是大顶堆

function heapsort(&$arr){
    $start = floor(count($arr)/2); //找到最后一个非叶子节点
    $end = count($arr);
    /*
     * 构造大顶堆
    */
    while($start>0){
        $p = $start;
        while($p){
            $p = makeheapchild($arr,$p,$end);
        }
        $start-- ;
    }
    //构造大顶堆结束
    /*
     * 交换顶部节点和最后一个叶子节点 依次调整大顶堆
     */
    while($end>1){
        swap($arr,0,$end-1);
        $end--;
        $p = 1;
        while($p){
            $p = makeheapchild($arr,$p,$end);
        }
    }
}

8.选择排序

下面是封装的选择排序的函数

function selectsort(&$arr){
    $end = count($arr)-1;
    do{
        $p = 0;
        for($i=0;$i<=$end;$i ){
            if($arr[$i]>$arr[$p]){
                $p = $i;
            }
        }
        swap($arr,$p,$end);
    }while(--$end>0);
}

9. 冒泡排序

下面是封装的冒泡排序的实现函数

function bubblesort(&$arr){
    $end = count($arr)-1;
    while($end>0){
        $flag = false;
        for($i=0;$i<$end;$i ){
            if($arr[$i]>$arr[$i 1]){
                swap($arr,$i,$i 1);
                $flag = true;
            }
        }
        if(!$flag) break;
        $end--;
    }
}

10. 基数排序——lsd

下面是封装的基数排序的lsd方式的函数

function lsd_radixsort(&$arr){
    //得到序列中最大位数
    $d = findmaxbit($arr);
    $bucket = array();
    //初始化队列
    for($i=0;$i<10;$i ){
        $bucket[$i]=array('num'=>0,'val'=>array());
    }
    /*
     * 开始进行分配
     */
    $radix = 1;
    for($i=1;$i<=$d;$i ){
        for($j=0;$j             $k = floor($arr[$j]/$radix);
            $bucket[$k]['num'] ;
            array_push($bucket[$k]['val'],$arr[$j]);
        }
        $arr = array();
        foreach ($bucket as $key => $val) {
            for ($j = 0; $j < $val['num']; $j ) {
                $arr[] = $val['val'][$j];
            }
        }
        for($l=0;$l<10;$l ){
            $bucket[$l]=array('num'=>0,'val'=>array());
        }
        $radix *= 10;
    }
}

11. 基数排序——msd

下面是封装的基数排序的msd方式的函数

function msd_radixsort(&$arr,$r){
    $radix = pow(10,$r-1);
    $bucket = array();
    //初始化队列
    for($i=0;$i<10;$i ){
        $bucket[$i]=array('num'=>0,'val'=>array());
    }
    for($j=0;$j         $k = floor($arr[$j]%pow(10,$r)/$radix);
        $bucket[$k]['num'] ;
        array_push($bucket[$k]['val'],$arr[$j]);
    }
    for($j=0;$j<10;$j ){
        if($bucket[$j]['num']>1){
            msd_radixsort($bucket[$j]['val'],$r-1);
        }
    }
    /*
     * 将桶中的数据收集起来，此时序列是有序的
     */
    $arr = array();
    for($j=0;$j<10;$j ){
        for($i=0;$i             $arr[] = $bucket[$j]['val'][$i];
        }
    }
}

希望本文对大家有帮助。