发布于 5年前

php 排序多个链表

将多个无序链表排列成一个有序链表。原理:插入排序

代码:

<?php

$singleLinkedList1=new SingleLinkedList(1);
$singleLinkedList1->add(2);
$singleLinkedList1->add(5);
$singleLinkedList1->add(7);
//print_r($singleLinkedList1);

$singleLinkedList2=new SingleLinkedList(2);
$singleLinkedList2->add(4);
$singleLinkedList2->add(6);
$singleLinkedList2->add(8);
$singleLinkedList2->add(10);

$singleLinkedList3=new SingleLinkedList(3);
$singleLinkedList3->add(5);
$singleLinkedList3->add(7);
$singleLinkedList3->add(9);
$singleLinkedList3->add(20);
//print_r($singleLinkedList2);

$lists=[$singleLinkedList2,$singleLinkedList1,$singleLinkedList3];

print_r(sortLinkedList($lists,null));

class Node
{
    public $val;
    public $next=null;
    public function __construct($val)
    {
        $this->val=$val;
    }

}

class SingleLinkedList
{
    private $header;

    public function __construct($val)
    {
        $this->header = new Node($val);
    }
    public function add($val) {
        $newNode = new Node($val);
        $endNode = $this->end();
        $endNode->next= $newNode;
        return true;
    }

    public function linkedTwoList($linkList)
    {
        $endNode = $this->end();
        $endNode->next= $linkList->getHeader();
        return true;
    }

    public function end()
    {
        $startNode=$this->header;
        while ($startNode->next!=null){
            $startNode=$startNode->next;
        }
        return $startNode;
    }
    public function shift()
    {
        $val=$this->header->val;
        if($this->header->next){
            $this->header=$this->header->next;
        }else{
            $this->setHeader(null);
        }

        return $val;
    }
    public function insertSort($val)
    {
        $startNode=$this->header;
        $newNode = new Node($val);
        $prevNode=null;
        while ($startNode->val<$val){
            $prevNode=$startNode;

            if(!$startNode->next){
                break;
            }
            $startNode=$startNode->next;

        }
        if(!$prevNode){//插在第一位
            $newNode->next=$startNode;
            $this->header=$newNode;
        }else{

            if(!$startNode->next){//最后一位
                $startNode->next=$newNode;
            }else{//插在中间
                $newNode->next=$startNode;
                $prevNode->next=$newNode;
            }

        }
        return true;
    }
    public function getHeader()
    {
        return $this->header;
    }
    public function setHeader($header)
    {
        return $this->header=$header;
    }
}

function sortLinkedList($lists,$sortList,$first=true){

    if($first){
//        $lists=quick_sort($lists);
    }

    list($lists,$sortList)=handleQuickSort($lists,$sortList);

    if(empty($lists)){
        return $sortList;
    }

    if(count($lists)==1){

        $sortList->linkedTwoList($lists[0]);
        return $sortList;
    }

    return sortLinkedList($lists,$sortList,false);
}

function quick_sort($data){

    if(count($data)<=1){
        return $data;
    }
    $pivot=$data[0];
    unset($data[0]);
    $A1=[];
    $A2=[];
    foreach ($data as $val){
        if($val->getHeader()->val<$pivot->getHeader()->val){
            $A1[]=$val;
        }else{
            $A2[]=$val;
        }
    }
    $A1= quick_sort($A1);
    $A2= quick_sort($A2);
    return array_merge($A1,[$pivot],$A2);
}
function handleQuickSort($lists,$sortList)
{

    $lists=array_values(array_filter(array_map(function($list)use(&$sortList) {

        if ($sortList == null) {//第一个节点
            $sortList = new SingleLinkedList($list->shift());
        } else {
            $sortList->insertSort($list->shift());
        }

        if(!$list->getHeader()){
            return null;
        }
        return $list;
    },$lists)));
    return [$lists,$sortList];
}

输出:

SingleLinkedList Object
(
    [header:SingleLinkedList:private] => Node Object
        (
            [val] => 1
            [next] => Node Object
                (
                    [val] => 2
                    [next] => Node Object
                        (
                            [val] => 2
                            [next] => Node Object
                                (
                                    [val] => 3
                                    [next] => Node Object
                                        (
                                            [val] => 4
                                            [next] => Node Object
                                                (
                                                    [val] => 5
                                                    [next] => Node Object
                                                        (
                                                            [val] => 5
                                                            [next] => Node Object
                                                                (
                                                                    [val] => 6
                                                                    [next] => Node Object
                                                                        (
                                                                            [val] => 7
                                                                            [next] => Node Object
                                                                                (
                                                                                    [val] => 7
                                                                                    [next] => Node Object
                                                                                        (
                                                                                            [val] => 8
                                                                                            [next] => Node Object
                                                                                                (
                                                                                                    [val] => 9
                                                                                                    [next] => Node Object
                                                                                                        (
                                                                                                            [val] => 10
                                                                                                            [next] => Node Object
                                                                                                                (
                                                                                                                    [val] => 20
                                                                                                                    [next] => 
                                                                                                                )

                                                                                                        )

                                                                                                )

                                                                                        )

                                                                                )

                                                                        )

                                                                )

                                                        )

                                                )

                                        )

                                )

                        )

                )

        )

)
©2020 edoou.com   京ICP备16001874号-3