<?php
/**
 * 
 */
class Solution
{
    private $queue;
    function __construct()
    {
        $this->queue = new SplQueue;
    }

    // 环形链表
    function cycleListNode($n) 
    {
        $cur = null;
        for ($i=1; $i <= $n; $i++) {
            $node = new ListNode($i);
            if ($i == 1) {
                $head = $node;
                $head->next = $head; // 如果只有一个节点，自己形成环形链表
                $cur = $head;
            } else {
                $cur->next = $node;
                $cur->next->next = $head;
                $cur = $cur->next;
            } 
            $head->count++;
        }

        return $head;
    }

    /*
    * 猴王选举
    *
    * 一 群猴子排成一圈，按1，2，…，n依次编号。然后从第1只开始数，数到第m只,把它踢出圈，从它后面再开始数，再数到第m只，在把它踢出去…，
    * 如此不停的 进行下去，直到最后只剩下一只猴子为止，那只猴子就叫做大王。要求编程模拟此过程，输入m、n, 输出最后那个大王的编号。用程序模拟该过程。
    */
    function isKing($m, $n) {
        $offset = 1;
        $currNode = $this->cycleListNode($n);
        $count = $currNode->count;
        while ($count > 1) {
            // 下一个就是目标节点
            // var_dump($offset);
            // var_dump($m);
            // echo "当前值{$currNode->val}\n";
            // echo "=============\n";
            if (($offset+1)%$m == 0) {
                // echo "出一个{$currNode->next->val}\n";
                $currNode->next = $currNode->next->next;
                $count--;
            } else {
                $currNode = $currNode->next;
            }
            $offset++;
        }
        return $currNode;
    }

    // 随机数组
    function randArr($n) {
        $arr = [];
        for ($i=0; $i < $n; $i++) { 
            $arr[] = rand(1, $n);
        }
        return $arr;
    }

    // 快速排序
    function quickSort($arr) {
        $len = count($arr);
        if ($len <= 1) {
            return $arr;
        }

        $tmp = $arr[0];
        $left = [];
        $right = [];
        for ($i=1; $i < $len; $i++) { 
            if ($arr[$i] < $tmp) {
                $left[] = $arr[$i];
            } else {
                $right[] = $arr[$i];
            }
        }

        return array_merge($this->quickSort($left), [$tmp], $this->quickSort($right));
    }

    // 冒泡排序
    function bubbleSort($arr) {
        $len = count($arr);
        if ($len <= 1) {
            return $arr;
        }

        for ($i=0; $i < ($len-1); $i++) {
            for ($j=$i+1; $j < $len; $j++) { 
                if ($arr[$i] > $arr[$j]) {
                    $tmp = $arr[$j];
                    $arr[$j] = $arr[$i];
                    $arr[$i] = $tmp;
                }
            } 
        }
        return $arr;
    }

    // 插入排序
    function insertSort($arr) {
        $len = count($arr);
        if ($len <= 1) {
            return $arr;
        }

        for ($i=1; $i < $len; $i++) { 
            $tmp = $arr[$i];
            for ($j=$i-1; $j >= 0; $j--) { 
                if ($tmp < $arr[$j]) {
                    $arr[$j+1] = $arr[$j];
                    $arr[$j] = $tmp;
                }
            }
        }
        return $arr;
    }

    // 选择排序
    function selectSort($arr) {
        $len = count($arr);
        for ($i=0; $i < $len; $i++) { 
            $p = $i;
            for ($j=$i+1; $j < $len; $j++) { 
                if ($arr[$p] > $arr[$j]) {
                    $p = $j;
                }
            }

            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
        return $arr;
    }
}

function que2Arr($queue) {
    $arr = [];
    $queue->rewind();
    while ($queue->valid()) {
        $arr[] = $queue->current();
        $queue->next();
    }

    return $arr;
}

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

function getMsectime() {
    list($msec, $sec) = explode(' ', microtime());
    return (float)sprintf('%.0f', (floatval($msec) + floatval($sec)) * 1000);
}

$time1 = getMsectime();

$sol = new Solution();
echo "<pre>";
$res = $sol->isKing(3, 10);
echo("国王编号：{$res->val}\n\n\n");

$arr = $sol->randArr(5000);
echo("原始数组：".json_encode($arr)."\n\n");
$res = $sol->quickSort($arr);
$time2 = getMsectime();
echo("快速排序：".json_encode($res)."\n耗时：".($time2-$time1)."\n");
$res = $sol->bubbleSort($arr);
$time3 = getMsectime();
echo("冒泡排序：".json_encode($res)."\n耗时：".($time3-$time2)."\n");
$res = $sol->insertSort($arr);
$time4 = getMsectime();
echo("插入排序：".json_encode($res)."\n耗时：".($time4-$time3)."\n");
$res = $sol->selectSort($arr);
$time5 = getMsectime();
echo("选择排序：".json_encode($res)."\n耗时：".($time5-$time4)."\n");