JIYIK CN >

In the article "Common Sorting Algorithms", we briefly introduced the ideas and implementation steps of various sorting algorithms. In this article, I will share the core codes of these sorting algorithms with you.

The complete code of all sorting algorithms is on github, click here to download .

1. Direct insertion sort

The following is the encapsulated direct insertion sort function

function InsertSort(&$arr){
    for($i=1;$i<count($arr);$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. Binary Insertion Sort

The following is the encapsulated binary insertion sort function

function HalfInsertSort(&$arr){
    for($i=1;$i<count($arr);$i++){
        if($arr[$i]<$arr[$i-1]){
            //Use binary search to find the appropriate position
            $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);
            }
            //End of binary searchif
            ($arr[$pos]>$arr[$i]){
                $pos = $pos-1;
            }
            for($j=$i-1;$j>$pos;$j--){
                $arr[$j+1]=$arr[$j];
            }
            $arr[$j+1] = $key;
        }
    }
}

3. Table insertion sort

The following is the encapsulated table insertion sort function

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<count($arr);$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<count($arr);$j++){
            $k = floor($arr[$j]/$radix)%10;
            $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();
    //Initialize queue
    for($i=0;$i<10;$i++){
        $bucket[$i]=array('num'=>0,'val'=>array());
    }
    for($j=0;$j<count($arr);$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);
        }
    }
    /*
     * Collect the data in the bucket, now the sequence is ordered
     */
    $arr = array();
    for($j=0;$j<10;$j++){
        for($i=0;$i<count($bucket[$j]['val']);$i++){
            $arr[] = $bucket[$j]['val'][$i];
        }
    }
}

I hope this article is helpful to you.