不知有晋

日期/时间表示#

1. 返回当前日期时间

   1 2	> SELECT NOW(); ## 同CURRENT_TIMESTAMP(),返回一个 datetime 表达式 <. 2021-03-14 15:37:16

2. 返回当前日期

   1 2	> SELECT DATE(NOW()); ## 同CURRENT_DATE() 和 CURDATE() <. 2021-03-14

3. 返回当前时间

   1 2	> SELECT TIME(NOW()); ## 同CURRENT_TIME() 和 CURTIME() <. 15:41:19

4. 单独返回年/月/日/时/分/秒

   1 2 3 4 5 6 7 8 9 10 11 12

   > SELECT YEAR(NOW()); <. 2021 > SELECT MONTH(NOW()); <. 3 > SELECT DAY(NOW()); <. 14 > SELECT HOUR(NOW()); <. 15 > SELECT MINUTE(NOW()); <. 49 > SELECT SECOND(NOW()); <. 43

5. 另一种方式单独返回年/月/日/时/分/秒

使用 EXTRACT(unit FROM date) 函数，unit 为要返回值类型，date 为日期时间表达式。

1
2

>   SELECT EXTRACT(YEAR FROM NOW());
<.  2021

unit包括：YEAR,MONTH,DAY,HOUR,MINUTE,SECOND,MICROSECOND等等。

使用 DATE_FORMAT(date,format) 函数，date 为日期时间表达式，format 为要返回的日期格式。

1
2

>   SELECT DATE_FORMAT(NOW(),"%Y");
<.  2021

常用的日期时间格式有：

更多的日期时间格式查看 Date and Time Functions 文档。

日期/时间计算#

1. 加 x 年/月/日/时/分/秒

   1 2 3 4

   > SELECT NOW(); <. 2021-03-14 18:21:18 > SELECT DATE_ADD(NOW(),INTERVAL 1 HOUR); <. 2021-03-14 19:21:18

2. 减 x 年/月/日/时/分/秒

   1 2 3 4

   > SELECT NOW(); <. 2021-03-14 18:23:07 > SELECT DATE_SUB(NOW(),INTERVAL 1 DAY); <. 2021-03-13 18:23:07

3. 计算两个日期时间之差

使用 DATEDIFF(date1,date2) 函数计算两个日期相差几天。

1
2

>   SELECT DATEDIFF(DATE_ADD(NOW(),  INTERVAL 1 DAY),CURDATE());
<.  1

使用 TIMEDIFF(time1,time2) 函数计算两个时间相差多少小时多少分钟多少秒钟。

1
2

>   SELECT TIMEDIFF(DATE_ADD(CURTIME(),INTERVAL 1 HOUR),CURTIME());
<.  01:00:00

日期时间与unix时间戳互相转换#

1. 日期时间 转 时间戳
   函数 UNIX_TIMESTAMP(datetime) 带一个日期时间表达式参数，当不带参数时，相当于 datetime=now()。

   1 2 3 4

   > SELECT UNIX_TIMESTAMP(); <. 1615721103 > SELECT UNIX_TIMESTAMP(DATE_ADD(NOW(),INTERVAL 1 DAY)); # 返回明天的时间戳 <. 1615807716

2. 时间戳 转 日期时间
   函数 FROM_UNIXTIME(unix_timestamp,format) 有两个参数， unix_timestamp 参数必须，表示时间戳，format 参数可选，表示日期时间格式，当 format 为空时，表示返回 "%Y-%m-%d %H:%i:%s" 格式的日期时间。

   1 2 3 4

   > SELECT FROM_UNIXTIME(1615807716); <. 2021-03-15 19:28:36 > SELECT FROM_UNIXTIME(1615807716,"%Y-%m-%d"); <. 2021-03-15

思路#

一般来说，日志文件都是按照日期来命名的，例如这样: 21_03_01.log。

每一个日志文件只记录当天某个功能的日志信息，这种做法方便于定为错误。

通过日志文件的属性——最后修改时间，可以得知日志文件记录的是哪一天的日志，距离现在过去多少天了。

当每天的日志量不多，可以考虑保存最近30天的日志量，保存再多也没有意义。

当每日的日志量很多的话，出于存储空间的考虑，可以考虑保存最近7天的日志量。

使用PHP删除日志文件#

需要删除日志文件的时候，通过web端手动调用接口 或者 通过 CLI 的方式，自动定时的调用接口，删除日志文件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

//删除日志文件
public function delLogs($day=30)
{
    if($day < 8)
    {
        echo "保留不少于一个星期的日志文件";
        die;
    } 
    $logDir = realpath(LOG_PATH);   
    $this->delLogs2($logDir,$day);
}

public function delLogs2($logDir,$day)
{
    $dh = opendir($logDir);
    if($dh){
        while($file = readdir($dh))
        {
            if($file == '.' || $file == '..')
                continue;

            $filePath = $logDir.'/'.$file;
            if(is_file($filePath))
            {
                if(filemtime($filePath) < strtotime("-{$day} days"))
                {
                    echo "file={$filePath}";
                    unlink($filePath);
                }
            }
            else
                $this->delLogs2($filePath,$day);
        }
        closedir($dh);
    }else{
        echo "目录错误：{$logDir}";
    }
}

使用SHELL脚本删除日志文件#

使用 find 命令，查找日志目录下的名字格式为 "*.log" ，最后修改时间为20天以前的文件，把找到的文件删除掉。

把命令写入 delLogs.sh 文件，通过终端命令sh delLogs.sh执行。

1
2
3
4

#!/bin/bash
echo start delete log 20 days ago...
find /app/Logs/ -mtime +20 -name "*.log" -exec  rm -rf {} \;
echo end delete log...

MySQL有四种分区类型，分别是RANGE分区、LIST分区、HASH分区和KEY分区。其中数RANGE分区使用最为普遍。

RANGE分区基于一个给定的分区键和分区值，把一个大的数据表分成多个连续且不重复的分区表。物理层面上是把一个大文件分割成多个小的文件。

数据表分区的两种方式#

方式一，创建表的同时，设置表分区

1
2
3
4
5
6
7
8

CREATE TABLE tablename(col1,col2,col3,...)
PARTITION BY RANGE(col_key)
(
    PARTITION p1 VALUES LESS THAN (value1),
    PARTITION p2 VALUES LESS THAN (value2),
    PARTITION p3 VALUES LESS THAN (value3),
    PARTITION p_maxvalue VALUES LESS THAN (MAXVALUE)
);

方式二，对已创建的表分区

1
2
3
4
5
6
7

ALTER TABLE tablename PARTITION BY RANGE(col_key) 
(
    PARTITION p1 VALUES LESS THAN (value1),
    PARTITION p2 VALUES LESS THAN (value2),
    PARTITION p3 VALUES LESS THAN (value3),
    PARTITION p_maxvalue VALUES LESS THAN (MAXVALUE)
);

分区的时候，最好设置一个最大分区 p_maxvalue

1

PARTITION p_maxvalue VALUES LESS THAN (MAXVALUE)

存放意料之外的数据。例如：

• 当出现错误数据，大于所有分区值时，会存放到 p_maxvalue 分区
• 当来不及增加分区时，数据会存放到 p_maxvalue 分区，且对前面的分区无影响

总之，设置 p_maxvalue 分区并不是为了存放数据，而是在出现意外的时候，程序不至于报错。

显示已分区的数据表#

1
2
3
4
5
6
7
8

SELECT
	TABLE_NAME tname,                   -- 数据表名
	TABLE_ROWS trow                     -- 数据行数
FROM
	information_schema.`TABLES`
WHERE
	TABLE_SCHEMA = {$dbName}
AND CREATE_OPTIONS LIKE '%partitioned%';

显示某个表的分区列表#

1
2
3
4
5
6
7
8
9
10
11
12

SELECT
	PARTITION_ORDINAL_POSITION onum,    -- 分区序号
	PARTITION_NAME pname,               -- 分区名字
	PARTITION_METHOD pmethod,           -- 分区方式
	PARTITION_EXPRESSION pkey,          -- 分区键
	PARTITION_DESCRIPTION pvalue,       -- 分区值
	TABLE_ROWS trows                    -- 数据行数
FROM
	information_schema.`PARTITIONS`
WHERE
	TABLE_SCHEMA = {$dbName}
AND TABLE_NAME = {$tname};

删除分区#

当历史数据归档后，分区的数据行数为0，此时该分区已经无用，为了减少系统的文件数，可以把它删除掉。

1

ALTER TABLE {$dbName}.{$tname} DROP PARTITION {$pname};

使用 DROP PARTITION 删除分区的同时，也会删除分区里的数据

取消分区#

1

ALTER TABLE {$dbName}.{$tname} REMOVE PARTITIONING;

取消分区对表数据无影响

增加分区#

增加分区之前，需要删除最大分区 p_maxvalue。
因为分区是连续递增的，所以需要把最大分区 p_maxvalue 删除，再增加新的分区。

1
2
3
4

ALTER TABLE {$dbName}.{$tname} ADD PARTITION 
(
    PARTITION {$pname} VALUES LESS THAN (value1)
);

拆分分区#

当来不及增加分区时，数据会存放到 p_maxvalue 分区。当发现 p_maxvalue 分区有数据时，应该尽快创建新分区，并把数据迁移到新分区上。

1
2
3
4
5

ALTER TABLE {$dbName}.{$tname} REORGANIZE PARTITION p_maxvalue INTO 
(
	PARTITION p_20210301 VALUES less than (1614528000),
	PARTITION p_maxvalue VALUES less than (MAXVALUE)
);

此时数据保存到了 p_20210301 分区，通过

1

EXPLAIN SELECT ....;

可以看到 partitions 字段的值为 p_20210301 ,表示查询的内容在 p_20210301 分区。

此时若发现查询并未使用到索引，则需要优化一下分区。

执行语句：

1
2

ALTER TABLE {$dbName}.{$tname} REBUILD PARTITION p_maxvalue,p_20210301;         -- 重建分区
ALTER TABLE {$dbName}.{$tname} ANALYZE PARTITION p_maxvalue,p_20210301;         -- 分析分区

或

1

ALTER TABLE {$dbName}.{$tname} OPTIMIZE PARTITION p_maxvalue,p_20210301;;

再次执行查询语句

1

EXPLAIN SELECT ....;

发现已经使用了索引。

REORGANIZE PARTITION 也可以用于重命名分区，重命名分区后也需要执行一下优化分区语句。

分区预警#

以下分区预警思路针对RANGE分区类型，基于时间的连续分区。

使用分区预警的好处有：

• 可以提前知晓备用的分区不足，不用逐个表检查
• 可以不用一下子准备多个备用分区，减少分区数量

分区预警的思路如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 分区预警，预警值默认60天
public static function warningPartition($warningDays=60)
{
    // 获取所有的数据库
    $dbNames = self::get_all_db();
    $result = [];
    foreach($dbNames as $dbName)
    {
        // 获取指定数据库的分区表列表
        $sqlTable = "SELECT TABLE_NAME tname,TABLE_ROWS trow FROM information_schema.`TABLES` WHERE TABLE_SCHEMA='{$dbName}' AND CREATE_OPTIONS LIKE '%partitioned%'";
        $listTable = self::querySql($sqlTable);
        foreach($listTable as $table)
        {
            // 获取指定数据库，指定表的除p_maxvalue外的最大分区的值
            $sqlPartition = "SELECT PARTITION_NAME pname,PARTITION_DESCRIPTION pvalue FROM information_schema.`PARTITIONS` WHERE TABLE_SCHEMA='{$dbName}' AND TABLE_NAME='{$table}' AND PARTITION_NAME != 'p_maxvalue' ORDER BY PARTITION_DESCRIPTION DESC LIMIT 1";
            $listPartition = self::querySql($sqlPartition);
            $pvalue = $listPartition[0]['pvalue'];

            // 最大分区的值小于阈值，则保存预警信息
            if($pvalue - time() < $warningDays * 86400)
                $result[] = "数据表：{$dbName}.{$table}，最新分区：{$listPartition[0]['pname']} - {$listPartition[0]['pvalue']}，预警阈值：{$warningDays}天";  
        }
    }
    return $result;
}

分区预警程序 + Telegram机器人可以实时的收到预警信息。

趁着十一假期，闲来无事，于是上叠石山走一走。

一来听老妈说叠石山上修了路，有人在上面设了佛（可以拜拜的神仙），有了香火，想去看看变成什么样子；

二来也想登顶去看看河浦全景。

遥想上一次上叠石山应该是2017年的春节，和同学两个人在傍晚的时候上叠石山散步，拍了不少逗逼照片，怀念当年简单的快乐。

从家里步行15分钟就到达山脚下，远远就看到了一个牌坊，写着「叠石书院」，看起来挺气派的。

穿过牌坊后，右手边有一大片空地，摆有挺多便民的健身设施，应该是给老人晨练活动的。

如果是开车过来的，可以把车停在这里。

再往前走可看见竖着一块石碑，石碑看起来很新，应该是翻新过或者重新做的。

石碑后面是一片池塘，水很浅，长了很多杂草，还有不少枯枝烂叶。

这里被称为「龙潭」，可能是因为小池塘的后面是「虎穴」吧。叫「龙潭虎穴」听起来比较有意境。

上山的泥土坡路都铺上了混泥土，还做了围栏，改变很大，颇有景区的样子。

上了斜坡后到达小平台，此处设有石凳，可供行人休息和观光。

旁边就展示了叠石山的导游图和各个石刻景点的照片。若是不熟悉叠石山的朋友，可以根据这个导游图按照石刻景点的顺序逐个到达。

站在小平台上，远远就可以望到「虎穴」石刻。

我印象中这里有野路可以上山，但可能我忘记了，竟然找不到出路，于是返回来老老实实走台阶上山。

上山的楼梯很好走，收拾的很干净，打心里敬佩家乡的爱心人士，为家乡打造了一处出行好去处。

可能考虑上山的楼梯比较长，不利于老年人小孩子，所以在楼梯中间的空地建了亭子厕所，方便大家休息。

终于来到设有香火的地方，按照导游图上的标记，这里就是「圣贤洞」。

记忆中这个石洞挺深的，里面被丢了很多垃圾，走进去就有一阵臭味，墙壁被烟火熏得发黑，路过通常都不进去的。

如今却被改造成小屋子一般，通了水电，收拾的干干净净，用来摆放神位。

石洞外面也搭了铁皮遮阴，摆了很多凳子桌子，供大家休息聊天。

「圣贤洞」的后面就是「九曲径」，上面是「龙凤石」。

「龙凤石」这个名字我第一次看到，我们都管着叫「大石」，上「大石」可以借助旁边的大树上去，不过需要手脚并用，有点危险；不想爬树也可以再往上走，绕一下也能到达。

上到大石，记得小的时候还开玩笑说不能大声说话，大声说话会让石头裂开，最后从山上滚下去。

站在大石上，有远眺河浦最好的视野。

河浦街道的几个村落互相紧邻着，房子越来越多，越建越高，不断得向外围扩张。

还记得当年第一次上「大石」时，有小伙伴跟我们介绍，河浦形状似一把枪，如今看来已无迹可寻了。

「大石」旁边有个炉位，这里是烧番薯的地方。

当年可以呼唤几个同学，带上一袋子番薯和几瓶水，上「大石」度过愉快的一天，那段时光真是无忧无虑。

这么多年了，多少人的青春里有它，多少人因它而快乐。

可能在我们那个年代，娱乐的项目太少，于是上「大石」烧番薯就成了一个不错的选项，有的吃，有的玩，还有趣。

如今，看着炉位旁边绿油油的杂草，还开了花，想必现在的小孩子都不会上「大石」烧番薯了吧！

也是，现在的娱乐太多了，手机太好玩了。

从大石下来后，遇见一行大叔大妈，应该是本地人，于是我慢慢的跟在后面，听其中一个大叔介绍叠石山的一些事迹。

虽然叠石山来过不少次，但其实我对叠石山的历史也不很了解，只知道以前有个人，叫陈英猷 在这里潜心读书，出名后，很多人来这里找他拜师学习而已。

「幽涧泉」下是真的有泉水的，记得以前到这里会洗手洗脸的，嬉戏一番，只不过当天没见到泉水，不过犹可见湿润的沙石。

「幽涧泉」往下就是「旋螺洞」，由于我脱离了大叔大妈的队伍，只身一人，加上上个月在山上被蚂蜂蜇了几针，到现在还心有余悸，于是就没往下去了。

旋螺洞的图片和介绍可以看看这一篇 游叠石山

按照导游图「寿」和「古松鹤舞」就在附近。

「寿」藏的比较隐秘，在小路旁边的大石的背后，需要绕一下才能看到。

「古松鹤舞」也是，沿着小路走，记得回头看一下就能看到。

接着来到「石室」和「叠石井」，这里就是先人读书学习的地方，我们也叫「叠石书房」。

石室内低矮、潮湿、阴暗，布局简陋，蚊子成群。

墙壁上用红色颜料写了很多名字，类似XX、XX、XX结拜兄弟之类的，看到这些难免会心一笑，我甚至可以想象到一群小年轻热血方刚的跪在一起发誓。

从「石室」出来，往上走左拐就看到了「河图」。

这个神秘的图案一直在这，没人知道它代表了什么，表达了什么意思。

根据导游图，河图过后就是「仙踪」，但我竟然给漏了，直到下山后才发现。仙踪的图片来源于 叠石山风景区

「仙踪」其实就是有一个大脚印，并且只有一个。

相传是神仙一步跨过几座山，所以只在此处留下一个脚印。

最后一个打卡点是「海阔天空」。

听老一辈说以前从这里望下去是一片沧海桑田，无边无际。

但由于河浦这里人多地少，用地紧张，所以要填海造陆。

到如今，海没了，田慌了，时过境迁，物是人非，再也见不到当初的海阔天空了。

离开「海阔天空」后一路径直下山，结束叠石山之行。

最后说明一下写这一篇游记的目的。

我这一路上山下山，看到沿途有很多垃圾。

塑料瓶，塑料袋、零食袋，果皮甚至看到整张的野餐垫。

五颜六色的垃圾跟大自然实在不搭，大煞风景。

爱心人士开始开发叠石山，并且在上面设置了香炉。

我们知道河浦人爱拜老爷拜神仙，香火所到之处，人流必跟之，人流所到之处往往会有产生垃圾的问题。

我相信未来叠石山会成为一个知名景点，会有更多的人上叠石山上香或者游玩，但我不希望看到山上因此出现越来越多的垃圾。

所以希望爱心人士在开发叠石山的同时，关注一下环境保护方面的问题。

比如：

1. 可以发起一场「清山活动」，组织一些热心人士上山把垃圾带下来
2. 沿着山路摆放「不乱扔垃圾」的提示语，提醒大家保护环境

清远佛冈猪咸脑山，又名猪牙山，海拔889米，山高路陡，怪石嶙峋，地形险要。与韶关龙斗峰地貌风光相似，所谓“小龙斗”。

9月6日周日，天气多云转阴。

7:30分在客村地铁B出口集合，8:00准时出发，途径从化，进入清远，最终到达小龙斗山下的旁边的村庄。
在从化服务区停留的时候，与走在尾队的领队小湘闲聊了一下，得知小龙斗是省内三星路线中危险系数最大的，同时景色也是最好的。
听到这里不由得兴奋起来，毕竟我也已经拿下几条三星路线了，甚至开始“膨胀”了，准备去尝试四星路线了。

大概10:00的时候到达山脚下，在领队的带领下，大家一起做热身动作，然后成群结队出发。

以前我喜欢紧跟着前队的人，一路无语，专心赶路，走累了就停下来口水，调整一下，然后继续走；走快了就停下来，等一等后面的人，实在等不到了，又开始走。最后变成在山下等，最长一次是等了两个多小时。

鉴于小龙斗的危险系数和景色，我这次想要慢点走，并且体验一下走在尾队的感受。

艰难上山#

上山后全程野路，经过一片又一片的密林，时而要钻过矮竹林，还要当心被打脸。

这里的竹子都很细，但每一根都很挺拔。
地上覆盖着厚厚的落叶，脚步走过，沙沙作响。

竹林里的竹子密密麻麻，在阴暗光线的笼罩下，有一瞬间我恍惚了，我感觉到一排竹子在我面前晃荡，这种奇怪的感觉让我只想快速离开。

离开竹林后要通过一处乱石水涧，灰黑色的大石头经过流水的浸泡，已经开始长青苔了。
领队在乱石间娴熟的迈步，跟着跨过几根枯木，一个跳跃上了小土坡，看起来是在告诉后面的人，跟着我这样走就可以安全的过来。

之前有人说山路很滑，我想象中的是那种湿润的黄土坡，没想过还有长青苔的大石头，真是too young too simple，这个滑倒可痛好多，所以我倒是小心翼翼的走好每一步，队友间互相搀扶着，遇到需要拉一把的即可伸出援手。

走在尾队的初步感觉是：
累了停一下，渴了停一下，别人停一下我也停一下，完全没有赶路的压力。

爱在小树林#

中午13点的时候我们走到了小树林，前面的人已经早到半个小时了，大家各自找地方坐下来休息补给。

刚一到达，就看到领队在分西瓜了，看到我们到达，拿着几片西瓜就递过来，这种感觉真好。

后来才知道，这一次的西瓜是其中一位徒友背上来的，说是为了锻炼负重
，于是背了个如桶一般的大背包，里面装了很多东西，其中就包括了这个西瓜。

大家把各自带的美食都拿出来分享，放到了野餐垫上。看到这个场面，感觉我应该带点冬枣或者柑橘来的。
接着有小伙伴拿出了啤酒，我在他的怂恿下也试了一点，果然还是有点苦涩。

午餐我还是一罐八宝粥外加几个小水果就搞定了。

一起走的朋友这一次也吃了八宝粥，但吃下没多久就开始拉肚子。
我估计是吃到生冷的东西，加上阴冷的天气，导致着凉了。
据他说这是他第一次在户外吃八宝粥，听后我感觉这样太冒险了。

由此对户外食物分享有一点反思：

大家开开心心一起出来游玩，还带了喜欢吃的食物出来分享，这本身是好的，但是作为接受分享的人，要根据自身的肠胃能力来做选择。

最保险的做法是吃自己带的食物和吃自己日常吃过的食物。
对于没吃过或者不常吃的就要谨慎对待。否则在荒郊野外吃出肠胃问题，后果无法想象。

我见过分享的食物种类还挺多的，有：小番茄、提子、青瓜、自制的凤爪、自制的辣条、不认识的啤酒、瓜子、诱人的小零食和面包等等。
因为我自知肠胃消化能力不强，所以对于没吃过的食物，一般都不会轻易尝试。
同时也建议徒友们不要轻易尝试对自己身体“陌生”的食物。

总之，户外分享精神值得提倡和宣扬，但接受分享需要谨慎。

看天气预报，说今天天气是多云的，无奈天公不作美，天气持续阴冷。
早上做热身运动的时候莫名奇妙的流了一身汗，一直到中午都还没干，被汗湿透的衣服贴着身体，感觉到阴凉，心想失策了，应该带件衣服来更换的。

大家“酒足饭饱”后纷纷收拾行囊陆续出发了，眼看没剩几个人了，作为尾队的我们也赶紧起动，跟上大家的步伐。爬了半个小时坡，终于上到山脊线上。

山顶拍照#

山上风光无限好，让人眼前一亮，豁然开朗，乱石嶙峋，险峭奇特。

有的形似巨蟒出洞，有的形似雄鹰展翅，有的形似神龟望天，有的形似犄角凸起，有的形似骆驼匍匐……，看得我眼花缭乱。
巨石屹立，如同一道道险阻的关隘，越过重重阻碍，迎接我们的是一望无际的蓝天白云。

无限风光在此，无限风光在险峰。

山顶的打卡点颇多，景色也别具一格。站在巨石上，眺望远方，蓝天与白云相间，远处有有河流蜿蜒流长，稍近一些有村庄星罗棋布，更近的地方是郁郁葱葱的丛林，而脚下是令人望而却步的悬崖。美中不足的是视野略带灰蒙。微风吹拂而过，带走整个上午的阴冷湿气，彷佛在提醒这我们，振作起来，拍照时间到了。

路过打卡点，阳光 领队已经在那里等候，凑齐四人，摆好pose，快门一按，就把大家的笑容给定住了。

此行真心要夸夸 32号 的领队，把大家照顾的很周全。

来到集合地点后，照例拍个大合照。

大合照后留有一些时间给大家自由活动和拍照，看大家发挥搞怪、逗比的表演也是一件享受的事。

山顶危峰耸立，怪石遍布，有时候需要在石缝间穿过，攀爬。不过难度不大，可以爬到猪牙峰最高处看小龙斗山全景。

山顶上百草凋零，脚步所过皆是颓黄惨淡。时而冷风掠过，为数不多的绿树瑟瑟发抖。顽强的石头仍傲然挺立着，在温暖的阳光照耀下，发出雄伟的光芒。

在不知不觉中，上午一直湿透的衣服也逐渐干了，心情舒畅，准备下山返回。

最难是下山#

下午14:30开始从垭口这里下山，这里是今天最难的一段。
路滑险陡，需要绳降。
要保持距离，一个接一个下去，否则有可能踩落滚石误伤下面的伙伴。

差不多花20分钟可以下完乱石坡，然后花1个小时穿过小树林。

午后阳光灿烂，林荫间的阴冷早已被驱散。
温度刚好，一路下山都没有出汗。
天气干燥，有些野路沙化，有点陡滑。
这个时候手套是个好帮手，带上手套，扶着两边的树干走就行。
尽管这样，我还是光荣地臀降了一次。

想到上周在某个户外群里看到的，也是在小龙斗，有个女生刚下山的时候就崴到脚了，最后一路臀降下山，看视频并没有凄凄惨惨戚戚，反而一路欢声笑语，趣味十足。

最后，走半小时的机耕路，4点钟就可以出到终点啦！

到达终点后，上车拿换洗的衣物，在山下一位阿姨的家里洗澡，换上干净的衣服，舒服。然后喝了几大碗绿豆糖水，满足了。

走出院子，望向小龙斗峰。回想这一路的忍耐都值得，感谢队友的陪伴，感谢领队的照顾。

一路走下来，小龙斗路线总体不难，风景倒是不错。
徒步全程约8公里，需要6个多小时，路线属三星难度。

一路经过无数迷坡乱石，需要手脚并用攀爬，必备手套和登山杖。
下山急降坡那里险陡路滑，需要绳降，务必小心落石。

Windows下，PHP添加扩展，步骤如下：

1. 找到目标扩展
2. 把扩展文件放到PHP扩展文件夹里
3. 添加扩展配置
4. 重启

下面以添加redis扩展为例。

确定PHP版本信息#

访问 phpinfo.php，找到这三个字段的值：

• PHP Version
• Architecture
• Thread Safety

从上图可知，需要找支持PHP版本7.0、x86架构、线程安全的redis扩展。

查找扩展#

到PECL查找redis扩展，输入扩展名字，查找。

从查找结果列表中找到redis扩展。

点击进入，看到有不同版本的redis扩展。

注意要找稳定版(statble)的DLL。

根据第一步确定的信息，可以找到目标扩展，点击下载。

安装扩展#

解压缩扩展文件，把DLL扩展文件放到PHP扩展文件夹里面。

如果不知道PHP扩展文件夹的位置，从php.ini里搜索extension_dir=”…”可以找到。

在php.ini文件里添加

extension=php_redis.dll

即可。

测试#

重启服务器，访问 phpinfo.php ，如果看到有目标扩展信息，即表示安装成功。

第一次看到大南山的图片是蓝蓝的天空，厚厚的白云，绿油油的草原，颇有几分大西北的感觉，如果有多几只牛羊，以假乱真足矣。这如画的风景不去可惜了，于是叫上朋友一起报名，参加了8月8日周六的活动。

大南山位于惠州市惠东县与汕尾市海丰县接壤的地带，此地群峰耸峙，林深壑幽，山腰白练飘飘，山下溪涧奔流。
三五村落散布其间，恍若桃源。因有著名的南山寺、南山河，故统称南山。

当天上午7:30出发，经过3个多小时的车程，到达惠东县南山村，下车后集体做热身动作，将近11点的时候，开始进山。

进山首先就遇到上坡，虽然坡度不陡，但是一开始连续上坡的话可能会造成身体不适，所以领队也建议走一段歇一段，让身体逐渐进入状态。

大概12点的时候到达午餐点（此时还没走3公里），午餐点是一条较为平坦的土路，路面铺满了枯萎的落叶。
路两边长有很高的树，把中午的阳光都挡住了，感觉阴凉。
大家纷纷在路的两旁挨着树坐下，先到的在前面，后到的坐后面，如此一排坐下去。
领队切好了西瓜，就沿着两边一个一个分过去。

午餐既丰富又有惊喜，同行的小伙伴们纷纷拿出了“珍藏”，发挥户外分享精神，有提子、小番茄、青瓜。
有的小伙伴热情的很，端着盒小番茄一个人一个人的问过去：“吃一个，吃一个”。

冰镇西瓜基本是标配，令我感到惊喜的是领队还带了私家辣条和冰镇可乐，顿时引起一阵骚动。

要知道什么时候的可乐最好喝，肯定是运动后，大汗淋漓，筋疲力尽，可乐犹如催化剂一般将你激活。

相比较而言我带的冬枣和青柑不太受欢迎，但我觉得也不错啊。
一巡吃下来，差不多有五六分饱了，手上的八宝粥也不“香”了，但为了后面不至于体力下降，还是把八宝粥吃了下去。

酒足饭饱好赶路，短暂休整后就开始跟着前队出发了。

因为刚吃东西不久，所以行进的速度也没敢太快，就当作散步那样慢走。没多久就走出了丛林，来到了令人找不到北的茅草荡前。

茅草长得又高又密，刚进去手指就被割了，虽然流了点血，不过也仅仅是皮外伤，无大碍。
领队说的要武装到牙齿，应该就是指这一段吧！
庆幸的是，这一段不用五分钟就穿过了。

因为在茅草荡里都是弯腰低头走路的，所以出来的第一个感觉就像重见天日一般，不仅如此，还看到了接下来要上的第一个急升坡，像一块绿色的毯子一样挂在那里，第一次如此亲近草原，迫不及待来一张。

终于来到第一座山前面，装好水就开始上山了。这一座山爬升高度有400多米，由半山腰的一个平台分成两节。

上第一节的时候，我们已经被前队的人甩掉了，自然的就变成了中队的人。
爬升没一会儿就开始喘息，在山脊上稍站了一下，发现完全没风，而且还很闷热，于是就继续跟着爬升，想着尽快到达平台。

在快要到达平台的时候，感觉到呼吸不畅，有呕吐的感觉，于是才马上停下来，大口呼吸，努力让心率降下来。
经过调整节奏，放缓速度，最后才颤巍巍的到达平台，没有被领队拉爆，自己反而“爆了”，策略错误。

所以说，无论是爬山还是跑步，都要时刻关注自己的呼吸，重视身体给出的信号，要根据当前的体力情况来调整速度和节奏。
切莫盲目的跟着前面的人或者跟别人比拼耐力，也不要因为挡到后面的人而强忍着继续前进。

到达第一座山顶峰后，累得直接坐下来，顺手把刚刚吃剩下的提子小番茄冬枣和青柑拿出来，做一轮补充，顺便也减一下负。

没过多久尾队的领队也到了，我和我朋友都惊呆了！
我们跟着前队出发，和中队一起上山，最后在山顶休息，变成了尾队。我“断后大师”的小目标实现得太突然了。
于是赶紧收拾东西，撇了。

一段短暂的下坡后就下山了，接着就是3公里的机耕路。

机耕路好走很多了，我加快了脚步想要去追中队。但是发现朋友速度没跟上，或许是刚刚的上坡太猛还没恢复，在确定了水量和食物足够后，我就先去追中队了。

连走带跑的追到中队伍并且超过了中队的领队，赶在15点前到达第二座山下。

后来才意识到，其实不用那么赶的，如果体力足够的话，领队也不会阻止你登顶的。设置关门时间，可能是想给一些想要提前下撤的队友多一个选择，或者说是帮他们做一个选择，当然最重要的还是自己决定。

短暂的休息，喝水，装水后，开始上第二座山。

第二座山爬升高度有100多米，由山腰的一个平台分成两节。

这一次格外注意上升速度，累了就歇，避免再次出现身体不适。
行走在山脊上，同样的无风，闷热。
走累了就停一下，一停下来就感觉到身体不断的在散发热量，汗水滴在乱石上，一下子就不见了，所以停下来好像也没舒服多少。
只能集中精神，忍着慢慢上。

终于到达山腰的平台，队友们聚集在悬崖边聊天、看风景、补充食物。

一阵风吹来，大家都安静了。微风带走身体多余的热量，带走暑气，舒服，沁人心脾。

在平台上眺望那条长长的机耕路，看到三三两两的人群，回想起刚刚一个人连走带跑的情景，心想我刚刚是否走太快了？以至于遗落了一些什么东西。

但生活中不就是这样吗？总是为了实现一个目标一条路走到黑，而忽略了过程中的美景，这注定无法兼得。

陈老师说：“我知道草原上又扬起微风，就该要说再见”。

是的，感谢微风带走疲倦，我还要赶路，再见。

第二节爬升高度大约50米，难度不大，不用15分钟就登顶了。

顶峰——斧头石，无遮无挡，明显更晒，但风景却最好。

往前看，可以看到大海，那是惠州的内海湾，惠州海湾大桥横跨南北两岸；
左边是一片低矮的山地，散布着村落，还有几根大烟囱，冒着浓浓白烟；
右边是陡峭的悬崖，还有连绵不绝的山脉；
后面正是来时的路，陡峭的山脊直通山脚下，远处则是那条如黄色丝带般的机耕路，连接着两座高山。

正当休息的时候，意外发现朋友就在下面的平台，正在往上面走。最后能一起登顶当然是最好的结果，也是最开心的事情。

大约16点的时候，尾队的小伙伴全部登顶了，拍了个大合照，我们就先下撤了。

下撤路是一条长长的下坡路（如下海拔图，从最高点一直到最低点），相对来说，下坡路容易一点，但需要一些技巧。
考虑到领队几次强调这一次下坡比较长，所以一开始就借用了朋友的一根登山杖并尝试使用，庆幸的是走到这里已经能熟练的借力登山杖了。

下山后在想，或许正因为有登山杖的帮助，我才能顺利的下山。
因为记得有几个地方是比较陡峭的黄土坡，黄土经过雨水的冲刷，变得湿润，踩上去极容易打滑，稍不留神就会摔屁股。登山杖就是在你打滑的时候给你一个支撑，留给你更多的反应时间。
由此也一改我以前对登山杖的看法。

其实每个工具被创造出来，自有它的用处，如果你觉得没用，那可能是你还不会用，或者是还没用到它的时候。

走过漫长的“绝望坡”，穿过狂野的乱石路，终于看到了大马路，终点就在眼前了。
最后自娱自乐的“冲刺”通过围栏，“恭喜第五名第六名选手完成穿越”。

终于到达终点——大王庙，来到大王庙对面的小吃店歇息，此时啥也吃不下，整两碗糖水先。

小吃店有厕所可以免费洗澡，虽然条件简陋，但能把那身被汗水湿透的衣服换洗下来，已经很满足了。

接下来就是等待尾队的小伙伴下来，直到19点的时候，才看到尾队的领队，19:30全员上车，返回广州，大约22:30抵达客村地铁站，结束今天的行程。

本次行程有14公里，累计爬升将近1000米，耗时6小时20分。
从南山村出发，登顶斧头石，最后安全到达大王庙。

算法思想#

基数排序是一种借助于多关键字排序的思想对单关键字排序的方法。

基数排序也有人称桶排序，因为借助于10个桶（0~9号桶）临时存放记录。

基数排序算法通过若干次 $(loop)$ 分配和收集实现排序。$loop$ 值由最大的记录关键值的位数决定，例如待排序的表中，最大的记录关键值为100，那么 $loop$ 等于3，需要3次分配和收集才能实现有序表。

第一次分配，需要取 记录关键值的个位数 为索引值，存放到对应的桶里面，如果有相同的索引值，则按顺序存储。

第一次收集，需要按桶的索引值和桶里面记录值的顺序收集。

这样就完成了第一次分配和收集。

第二次、第三次分配收集也是按照这样的过程完成。

一道使用基数排序解决的题 leetcode 128h 最长连续序列

性能评价#

时间复杂度：$O(n)$

稳定性：稳定

基数排序完整代码#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

#include <stdio.h>
#include <stdlib.h>
typedef int KeyType;
typedef char InfoType[10];

typedef struct node
{
    KeyType key;
    InfoType data;
    struct node *next;
} RecType;

void DisRecType(RecType *p);
RecType* generalPNode(int* nums, int numsSize);
int getMaxNum(RecType *p);
int GetMaxLoop(int num);
int getBaseNum(int num,int numSt);
void RadixSort(RecType **p);

//  基数排序
int main()
{
    int n = 10;
    RecType *p;
    KeyType a[] = {1,4,6,8,0,2,5,7,9,3};
    p =generalPNode(a, n);

    printf("排序前：");
    DisRecType(p);

    printf("基数排序 ... \n");
    RadixSort(&p);

    printf("排序后：");
    DisRecType(p);
    return 0;
}

// 输出序列
void DisRecType(RecType *p)
{
    while (p != NULL)
    {
        printf("%d ",p->key);
        p = p->next;
    }
    printf("\n");
}

//  构造基数排序存储结构
RecType* generalPNode(int* nums, int numsSize)
{
    int i;
    RecType *p = NULL,*q = NULL,*tmp;
    for(i=0;i<numsSize;i++)
    {
        tmp = (RecType *)malloc(sizeof(RecType));
        tmp->key = nums[i];
        tmp->next = NULL;
        if(q == NULL)
        {
            q = tmp;
            p = q;
        }
        else
        {
            q->next = tmp;
            q = tmp;
        }
    }
    return p;
}

//  归并排序
void RadixSort(RecType **p)
{
    int max = getMaxNum(*p);
    int	loop = GetMaxLoop(max);

    RecType *head[10],*tail[10],*tmp;
    int i,j,k;

    for (i = 1; i <= loop; i++)
    {
        //  每次循环，先清空各个桶里的数据
        for(j = 0; j < 10; j++)
            head[j] = tail[j] = NULL;

        //  分配
        //  把链表的分配到指定的桶里
        //  由于是链式存储，所以每个桶里的实际数据是head和tail指针之间的节点
        while ((*p) != NULL)
        {
            k = getBaseNum((*p)->key,i);

            if (head[k] == NULL)
                head[k] = (*p);
            else
                tail[k]->next = (*p);

            tail[k] = (*p);
            (*p) = (*p)->next;
        }

        //  重置链表
        (*p) = NULL;     

        //  收集
        //  各个桶里的实际数据是有head和tail指针确定的
        //  所以把各个桶按顺序，按照 tail->next = head 连接起来
        //  最后把 tail->next = NULL 就完成了收集工作
        for ( j = 0; j < 10; j++)
        {
            if (head[j] != NULL)
            {
                if ((*p) == NULL)
                    (*p) = head[j];    
                else
                    tmp->next = head[j];
                tmp = tail[j];
            }
        }
        tmp->next = NULL;
    }
}

//  返回最大关键值
int getMaxNum(RecType *p)
{
    int max = 0;
    while (p != NULL)
    {
        if(p->key > max) max = p->key;
        p = p->next;
    }
    return max;
}

//  返回整数的位数
int GetMaxLoop(int num)
{
	int bits = 1;
	num /= 10;
	while (num != 0)
	{
		++bits;
		num /= 10;
	}
	return bits;
}

//  返回整数指定位序号的值
int getBaseNum(int num,int numSt)
{
    int numTimes = 1;
    int i,baseNum;
    for(i=1;i<numSt;i++)
    {
        numTimes *= 10;
    }
    baseNum = num/numTimes%10;
    return baseNum;
}

算法思想#

归并排序简单的来说是把两个有序表合并成一个有序表。

一开始从规模最小的只有1个记录的两个表开始合并，使待排序表局部有序。
随着记录规模的扩大，待排序表从局部有序逐渐变成整体有序。

每一次循环的规模都遵循2倍数扩大，从一开始的1个记录，到2、4、8、…，递增。

每一次归并排序都需要借助开辟的存储空间来保存合并后的有序表，然后再复制到原来的表上，不能在原来的表上直接操作。

性能评价#

时间复杂度：$O(nlog_2n)$

稳定性：稳定

归并排序完整代码#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

#include <stdio.h>
#include <stdlib.h>
typedef int KeyType;
typedef char InfoType[10];

typedef struct
{
    KeyType key;
    InfoType data;
} RecType;

void DisRecType(RecType R[],int n);
void MergeSort(RecType R[],int n);
void MergeSortWithLength(RecType R[],int length,int n);
void Merge(RecType R[],int left,int mid,int right);

//  归并排序
int main()
{
    int n = 10;
    KeyType a[] = {1,4,6,8,0,2,5,7,9,3};
    RecType R[10];
    for (int i = 0; i < n; i++)
        R[i].key = a[i];

    printf("排序前：");
    DisRecType(R,n);

    printf("归并排序 ... \n");
    MergeSort(R,n);

    printf("排序后：");
    DisRecType(R,n);
    return 0;
}

// 输出序列
void DisRecType(RecType R[],int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ",R[i].key);

    printf("\n");
}

void MergeSort(RecType R[],int n)
{
    int length=1;
    while (length < n)
    {
        MergeSortWithLength(R,length,n);
        length *= 2;
    }
}

void MergeSortWithLength(RecType R[],int length,int n)
{
    int i = 0;                  //  第一个有序数组开始下标   
    int k = i + length - 1;     //  第一个有序数组结束下标           
    int j = i + 2*length - 1;   //  第二个有序数据结束下标
    while (j < n)
    {
        Merge(R,i,k,j);
        i = j + 1;
        k = i + length - 1;
        j = i + 2*length - 1;
    }

    //  剩下至少有 length 个记录，才需要整理排序
    if(k < n)
    {
        Merge(R,i,k,n-1);
    }
}

//  合并两个有序数组成一个有序数组
void Merge(RecType R[],int left,int mid,int right)
{
    int i = left,j = mid + 1,k=0;
    RecType *tmp = (RecType *)malloc(sizeof(RecType) * (right-left+1));
    
    while (i <= mid && j <= right)
        if(R[i].key < R[j].key)
            tmp[k++] = R[i++];
        else
            tmp[k++] = R[j++];
    
    while (i <= mid)
        tmp[k++] = R[i++];

    while (j <= right)
        tmp[k++] = R[j++];

    for (int k = 0,i = left; i<=right; i++,k++)
        R[i] = tmp[k]; 
}

算法思想#

每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子表的最后，直到全部记录排序完毕。

两种选择排序方法#

1. 直接选择排序
2. 堆排序

直接选择排序#

基本思想

设有n个元素，则需要n-1次循环。
每次循环通过两两对比，找到关键值最小的记录，经过n-1次循环后则可以得到一个有序的序列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

//  选择排序
void SelectSort(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            //  R[i]的关键值与R[j]的关键值逐个比较，每次把较小的赋值给R[i]
            //  存在交换多次的问题
            if(R[i].key > R[j].key)
            {
                tmp = R[i];
                R[i] = R[j];
                R[j] = tmp;
            }
        }
    }
}

性能评价

时间复杂度：$O(n^2)$

稳定性：非稳定

直接选择排序 优化版#

基本思想

直接选择排序在每一次找到最小值的过程中，需要进行多次关键值比较。
若比较结果成立，则记录的位置互换（执行赋值操作）。
例如要求关键字序列：9 8 7 6 5 按递增顺序显示，程序的第一次遍历结果如下：

1
2
3
4
5

1>   9 8 7 6 5 
2>   8 9 7 6 5
3>   7 9 8 6 5
4>   6 9 8 7 5
5>   5 9 8 7 6

很明显，第一次遍历找到的最小值应该是 5，但是找到最小值过程中，发生了多次无用的赋值操作（第2、3、4行）。
为了减少时间复杂度，在比较的过程中，使用一个变量保存最小值的索引值，直到与最后一个元素比较后，才执行赋值操作。优化后的程序第一次遍历的结果如下：

1
2

1>   9 8 7 6 5 
2>   5 9 8 7 6

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//  选择排序 优化版
void SelectSort_v2(RecType R[],int n)
{
    int i,j,k;
    RecType tmp;
    for(i=0;i<n-1;i++)
    {
        //  默认第一个元素是最小的
        k = i;      
        for(j=i+1;j<n;j++)
            if(R[k].key > R[j].key)
                k = j;
        
        //  最后做一次比较，不相等则互相交换
        if(i != k)
        {
            tmp = R[k];
            R[k] = R[i];
            R[i] = tmp;
        }
    }
}

性能评价

时间复杂度：$O(n^2)$

稳定性：非稳定

直接选择排序代码#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

#include <stdio.h>

typedef int KeyType;
typedef char InfoType[10];

typedef struct
{
    KeyType key;
    InfoType data;
} RecType;

void DisRecType(RecType R[],int n);
void SelectSort(RecType R[],int n);
void SelectSort_v2(RecType R[],int n);


//  选择排序
int main()
{
    int n = 10;
    KeyType a[] = {1,4,6,8,0,2,5,7,9,3};
    RecType R[10];
    for (int i = 0; i < n; i++)
        R[i].key = a[i];

    printf("排序前：");
    DisRecType(R,n);

    printf("选择排序 ... \n");
    SelectSort(R,n);

    printf("选择排序 改进版... \n");
    SelectSort_v2(R,n);


    printf("排序后：");
    DisRecType(R,n);
}

// 输出序列
void DisRecType(RecType R[],int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ",R[i].key);

    printf("\n");
}

//  选择排序
void SelectSort(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            //  R[i]的关键值与R[j]的关键值逐个比较，每次把较小的赋值给R[i]
            //  存在交换多次的问题
            if(R[i].key > R[j].key)
            {
                tmp = R[i];
                R[i] = R[j];
                R[j] = tmp;
            }
        }
    }
}

//  选择排序 改进版
void SelectSort_v2(RecType R[],int n)
{
    int i,j,k;
    RecType tmp;
    for(i=0;i<n-1;i++)
    {
        //  默认第一个元素是最小的
        k = i;      
        for(j=i+1;j<n;j++)
            if(R[k].key > R[j].key)
                k = j;
        
        //  最后做一次比较，不相等则互相交换
        if(i != k)
        {
            tmp = R[k];
            R[k] = R[i];
            R[i] = tmp;
        }
    }
}

堆排序#

完全二叉树简介

使用待排序 关键值序列 构建一棵完全二叉树，然后从上到下，从左到右，按顺序给完全二叉树编号。

使用顺序存储结构，所以物理编号为 $0$ 的位置为空，从物理编号为 $1$ 的位置开始保存关键值。

根据完全二叉树的性质可知：

1. 若编号为 $i$ 的节点为分支节点，则 $2i$ 为左子节点，$2i+1$ 为右子节点；
2. 若编号为 $i$ 的节点有父节点，则父节点编号为 $floor(\frac {i} {2})$ ；
3. 若完全二叉树有 $n$ 个节点，则编号最大的分支节点为 $floor(\frac {n}{2})$ ；

堆的定义

$n$ 个关键字序列 $K_1,K_2,…,K_n$ 称为堆，当且仅当该序列满足如下性质：

1. $K_i<=K_{2i}$ 且 $K_i<=K_{2i+1}$
2. 或 $K_i>=K_{2i}$ 且 $K_i>=K_{2i+1}$
   $(1<=i<=floor(\frac {n}{2}))$

堆可分为小根堆和大根堆：

1. 小根堆：根节点关键值 小于等于 左右子节点关键值的堆；
2. 大根堆：根节点关键值 大于等于 左右子节点关键值的堆；

基本思想

从编号最大的分支节点开始（编号为 $floor(\frac {n}{2})$ ），最大堆化 每一棵树，直到根节点结束。
此时得到一个最大堆，因为最大堆的根节点关键值最大，所以保存根节点，然后使用最有一个叶子节点赋值给根节点，继续堆化，直到最后一个节点结束。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

//  堆排序
void HeapSort(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    for(i=n/2;i>0;i--)
        Heapify(R,i,n);
    
    for(j=n;j>0;j--)
    {
        tmp = R[j];
        R[j] = R[1];
        R[1] = tmp;
        Heapify(R,1,j-1);
    }
}

//  最大堆化
void Heapify(RecType R[],int p,int n)
{
    int i,j;
    RecType tmp;
    tmp = R[p];
    i = p;
    j = 2 * p;

    // 有至少一个子节点
    while (j <= n)
    {
        //  有两个子节点则找到较大的那个
        if(j < n && R[j].key < R[j+1].key) j++;

        //  父节点比子节点小，则子节点“上浮”到父节点，并且继续堆化
        if(tmp.key < R[j].key)
        {
            R[i] = R[j];
            i = j;
            j = 2 * j;
        }
        else
            break;
    }
    R[i] = tmp;
}

性能评价

时间复杂度：$O(nlog_2n)$

稳定性：非稳定

堆排序完整代码#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

#include <stdio.h>

typedef int KeyType;
typedef char InfoType[10];

typedef struct
{
    KeyType key;
    InfoType data;
} RecType;

void DisRecType(RecType R[],int n);
void HeapSort(RecType R[],int n);
void Heapify(RecType R[],int p,int n);


//  选择排序
int main()
{
    int n = 10;
    KeyType a[] = {1,4,6,8,0,2,5,7,9,3};
    RecType R[10];
    for (int i = 0; i < n; i++)
        R[i+1].key = a[i];

    printf("排序前：");
    DisRecType(R,n);

    printf("堆排序... \n");
    HeapSort(R,n);

    printf("排序后：");
    DisRecType(R,n);
}

// 输出序列
void DisRecType(RecType R[],int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ",R[i+1].key);

    printf("\n");
}

//  堆排序
void HeapSort(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    for(i=n/2;i>0;i--)
        Heapify(R,i,n);
    
    for(j=n;j>0;j--)
    {
        tmp = R[j];
        R[j] = R[1];
        R[1] = tmp;
        Heapify(R,1,j-1);
    }
}

//  堆化
void Heapify(RecType R[],int p,int n)
{
    int i,j;
    RecType tmp;
    tmp = R[p];
    i = p;
    j = 2 * p;

    // 有至少一个子节点
    while (j <= n)
    {
        //  有两个子节点则找到较大的那个
        if(j < n && R[j].key < R[j+1].key) j++;

        //  父节点比子节点小，则子节点“上浮”到父节点，并且继续堆化
        if(tmp.key < R[j].key)
        {
            R[i] = R[j];
            i = j;
            j = 2 * j;
        }
        else
            break;
    }
    R[i] = tmp;
}