发布于 4年前
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] =>
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
