亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定

歸并排序

归并排序

这里使用的语言是PHP,但是语言都是相通的,用别的语言也可以实现,可以参考这里自行实现别的语言版本

/**
 * 归并排序
 */
function mergeSort(&$arr)
{
    $arr_len = count($arr);
    if ($arr_len <= 0) {
        return [];
    }
    merge_sort($arr, 0, $arr_len - 1);
}
//递归调用对arr[l...r]的范围进行排序
function merge_sort(&$arr, $l, $r)
{
    if ($l >= $r) {
        return;    
    }
    $mid = intval(($l + $r) / 2);
    merge_sort($arr, $l, $mid);
    merge_sort($arr, $mid + 1, $r);
    mergeData($arr, $l, $mid,$r);    
}
function mergeData(&$arr, $l, $mid,$r){

        //将数组arr[l...mid]和arr[mid + 1...r]两部分进行合并
        /**
         * 写法1:
         */
        $temparr = [];
        $i = $l;
        $k = $l;
        $j = $mid + 1;
        while($i != $mid + 1 && $j != $r+1)
        {
            if($arr[$i] >= $arr[$j]){
                $temparr[$k++] = $arr[$j++];
            }
            else{
                $temparr[$k++] = $arr[$i++];
            }
        }

        //将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
        while($i != $mid+1){
            $temparr[$k++] = $arr[$i++];
        }
        //将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
        while($j != $r+1){
            $temparr[$k++] = $arr[$j++];
        }
        for($i=$l; $i<=$r; $i++){
            $arr[$i] = $temparr[$i];
        }


        /**
         * 写法2:
         */
        // $aux = [];
        // for ($i = $l; $i <= $r; $i++) { 
        //     $aux[$i - $l] = $arr[$i];
        // }
        // $i = $l;
        // $j = $mid + 1;
        // for ($k = $l; $k <= $r; $k++) { 

        //     if ($i > $mid) {
        //         $arr[$k] = $aux[$j - $l];
        //         $j++;
        //     }elseif($j > $r) {
        //         $arr[$k] = $aux[$i - $l];
        //         $i++;
        //     }elseif($aux[$i - $l] < $aux[$j - $l]) {
        //         $arr[$k] = $aux[$i - $l];
        //         $i++;
        //     }else{
        //         $arr[$k] = $aux[$j - $l];
        //         $j++;
        //     }
        // }
}

$start = microtime();
$arr = [100,4,5,6,7,2,44,59,67,57,45,71,82,1];
mergeSort($arr);
$endtime = microtime();
echo '排序耗时:'.($endtime - $start) .'毫秒'."\n";
for ($i=0; $i < count($arr); $i++) { 
    echo $arr[$i].', ';
}

點擊查看更多內容
1人點贊

若覺得本文不錯,就分享一下吧!

評論

作者其他優質文章

正在加載中
軟件工程師
手記
粉絲
19
獲贊與收藏
139

關注作者,訂閱最新文章

閱讀免費教程

感謝您的支持,我會繼續努力的~
掃碼打賞,你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃,即可進行掃碼打賞哦
今天注冊有機會得

100積分直接送

付費專欄免費學

大額優惠券免費領

立即參與 放棄機會
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號

舉報

0/150
提交
取消