原文

在PostgreSQL,备份和恢复相对于其他的数据库是非常友好的。许多人也许不赞同，但我们不要陷入争论中。来讨论下备份，PostgreSQL不支持增量备份，然而，有许多非常统一的备份工具和操作系统级别的解决办法来实现这个目的。

我的关于PostgreSQL备份和恢复的图解给出了一个完整的概念的想法。看图，你可以辨别出哪个备份可以用来还原或恢复。

逻辑备份

pg_dump,pg_restore和pg_dumpall工具是用来进行逻辑备份的。pg_dump和pg_restore可以帮助你在数据库级别、模式级别和表级别备份。pg_dumpall用于集群级别备份。

pg_dump支持三种格式，Plain SQL 格式（纯文本SQL格式）， Custom 格式（自定义格式）和 Tar格式（打包格式）。Custom和Tar格式的备份与pg_restore工具是兼容的，然而，Plain SQL（纯文本SQL）格式的备份是与psql工具兼容的用于还原。

以下是每个备份级别和相关的还原命令的例子。

注意：在.bash_profile里设置默认的PGDATABASE, PGUSER, PGPASSWORD和PGPORT值。（在Windows里意思是环境变量）

纯文本SQL格式的备份和还原

1
2
3
4
5
6
7
8
9
10
11

$ pg_dump -U username -Fp dbname  >  filename 
or 
$ pg_dump -U username dbname -f  filename 
or 
$ pg_dump -Fp -U username dbname -f  filename 
 
使用 psql 命令来还原
 
$ psql -U username -f filename dbname 
or 
postgres=# \i SQL-file-name     //in psql terminal with \i option

自定义格式

1
2

$ pg_dump -Fc dbname -f filename 
$ pg_restore -Fc -U username -d dbname filename.dmp

Tar格式

$ pg_dump -Ft dbname -f filename
$ pg_restore -U username -d dbname filename
or
$ cat tar-file.tar | psql -U username dbname

注意：模式级别和表级别备份执行方式是一样的，通过添加相关的选项就可以了。

集群级别备份

1
2
3
4
5

$pg_dumpall -p portnumber > filename 
 
使用 psql 命令来还原
 
$ psql -f filename

这些都是非常好的备份和恢复的方法。特别地，www.2ndQuadrant.com 出版的，作者是Simon Riggs 和 Hannu Krosing 的书： “PostgreSQL 9 Administration Cookbook - 2010”，是学习PostgreSQL备份和恢复的很好方式。

物理备份（文件系统备份）

冷备份

在冷备份中，当Postgre实例关闭时，进行一个非常简单的/data目录的文件系统备份，意思是，实现一个前后一致的数据目录备份，在复制之前，数据库服务器应该关闭。PostgreSQL通过软链接来灵活地保持pg_xlog和pg_tablspce在不同挂载点。当复制/data目录并想包括那些软链接的数据时，可以使用以下命令。

1
2
3
4
5

tar czf backup.tar.gz $PGDATA 
or 
cp -r $PGDATA /backup/ 
or 
rsync -a $PGDATA /wherever/data

热备份（在线备份）:

在热备份中，集群会一直在启动和运行，并且数据库应该是在归档日志模式中。两个系统函数将会唤醒实例来开始、关闭热备份处理（pg_start_backup(), pg_stop_backup()）。在开始进一步进行在线热备前，让我们讨论一下对于在线备份中强制的数据库归档模式。

开启 WAL（预写式日志）归档:

下面将简要介绍一下 PITR/调整 WAL 等等。目前，我们先看看WAL归档。在PostgreSQL数据库系统，实际上数据库“写”一些额外被称为预写日志（WAL）文件到磁盘。它包含了一些在数据库系统中的写记录。在崩溃的情况下，数据库可以从这些记录中还原或恢复。

一般地，写日志记录会在定期匹配时（叫做checkpoints,检查点）记录该检查点，然后在它不再需要时删除它。你也可以使用WAL作为备份，因为它是一个所有数据库的写记录。（我注：就是更改数据库的操作）。

WAL归档概念:

WAL是由每16MB大小（我注：文件）组成的，这被称为segments（段）。WAL驻留在pg_xlog目录下，这是一个位于数据目录下的子目录。文件名会被PostgreSQL实例按数字升序来命名，执行一个WAL基础备份，这需要一个基础备份，一个数据目录的完整备份，并且WAL段会介于基础备份和当前日期之间。

配置WAL段归档，可以通过在postgresql.conf里的两个配置参数来设置:archive_command和archive_mode。使集群进入归档模式需要重启PostgreSQL。

1
2

archive_mode= on/off (boolean parameter) 
archive_command = 'cp –i %p /Archive/Location/f% '

注意：%p为通过路径来复制文件来作为一个文件名，%f没有为目标文件设置目录。（我注：也就是%p代表pg_xlog的绝对路径的文件，%f表示pg_xlog目录下的文件名，所以%p前没有目录，%f前有目录前缀）。

关于归档进程的更加多信息，请参考“PostgreSQL 9.0 内存 & 进程”

在线备份 :

采取在线备份：

1
2
3
4
5
6
7
8
9
10

步骤 1 : 在psql终端执行 pg_start_backup('lable')  
postgres=# select pg_start_backup('fb'); 
步骤 2 : 操作系统级别地复制 $PGDATA 目录到任何一个备份的位置。
$ cp -r $PGDATA  /anylocation 
步骤 3 : 在psql终端执行 pg_stop_backup()
postgres=# select pg_stop_backup(); 
注意：这两个函数不需要在数据库的同一个会话里执行。备份模式是全局的并且是持久的。

在PostgreSQL中，没有目录来保存在线备份的开始时间和结束时间。然而，当在线备份正在进行时，会有数个文件会被创建和删除。

pg_start_backup('label')和pg_stop_backup是两个执行在线备份的系统函数。通过pg_start_backup('label')会创建一个文件backup_label在$PGDATA目录下，通过pg_stop_backup()会创建一个文件wal-segement-number.backup在$PGDATA/pg_xlog目录下。backup_label会给出开始时间以及WAL(预写式日志）段的检查点位置，也会通知PostgreSQL实例是处于备份模式。在$PGDATA/pg_xlog目录下的wal-segment-number.backup文件描述了开始和停止时间，带有WAL段号的检查点位置。

注意： 在pg_stop_backup()之后，PostgreSQL实例就会删除backup_label文件。

提交你的评论，建议。

—Raghav

By Raghavendra

原文

在PostgreSQL,备份和恢复相对于其他的数据库是非常友好的。许多人也许不赞同，但我们不要陷入争论中。来讨论下备份，PostgreSQL不支持增量备份，然而，有许多非常统一的备份工具和操作系统级别的解决办法来实现这个目的。

我的关于PostgreSQL备份和恢复的图解给出了一个完整的概念的想法。看图，你可以辨别出哪个备份可以用来还原或恢复。

逻辑备份

pg_dump,pg_restore和pg_dumpall工具是用来进行逻辑备份的。pg_dump和pg_restore可以帮助你在数据库级别、模式级别和表级别备份。pg_dumpall用于集群级别备份。

pg_dump支持三种格式，Plain SQL 格式（纯文本SQL格式）， Custom 格式（自定义格式）和 Tar格式（打包格式）。Custom和Tar格式的备份与pg_restore工具是兼容的，然而，Plain SQL（纯文本SQL）格式的备份是与psql工具兼容的用于还原。

以下是每个备份级别和相关的还原命令的例子。

注意：在.bash_profile里设置默认的PGDATABASE, PGUSER, PGPASSWORD和PGPORT值。（在Windows里意思是环境变量）

纯文本SQL格式的备份和还原

1
2
3
4
5
6
7
8
9
10
11

$ pg_dump -U username -Fp dbname  >  filename 
or 
$ pg_dump -U username dbname -f  filename 
or 
$ pg_dump -Fp -U username dbname -f  filename 
 
使用 psql 命令来还原
 
$ psql -U username -f filename dbname 
or 
postgres=# \i SQL-file-name     //in psql terminal with \i option

自定义格式

1
2

$ pg_dump -Fc dbname -f filename 
$ pg_restore -Fc -U username -d dbname filename.dmp

Tar格式

$ pg_dump -Ft dbname -f filename
$ pg_restore -U username -d dbname filename
or
$ cat tar-file.tar | psql -U username dbname

注意：模式级别和表级别备份执行方式是一样的，通过添加相关的选项就可以了。

集群级别备份

1
2
3
4
5

$pg_dumpall -p portnumber > filename 
 
使用 psql 命令来还原
 
$ psql -f filename

这些都是非常好的备份和恢复的方法。特别地，www.2ndQuadrant.com 出版的，作者是Simon Riggs 和 Hannu Krosing 的书： “PostgreSQL 9 Administration Cookbook - 2010”，是学习PostgreSQL备份和恢复的很好方式。

物理备份（文件系统备份）

冷备份

在冷备份中，当Postgre实例关闭时，进行一个非常简单的/data目录的文件系统备份，意思是，实现一个前后一致的数据目录备份，在复制之前，数据库服务器应该关闭。PostgreSQL通过软链接来灵活地保持pg_xlog和pg_tablspce在不同挂载点。当复制/data目录并想包括那些软链接的数据时，可以使用以下命令。

1
2
3
4
5

tar czf backup.tar.gz $PGDATA 
or 
cp -r $PGDATA /backup/ 
or 
rsync -a $PGDATA /wherever/data

热备份（在线备份）:

在热备份中，集群会一直在启动和运行，并且数据库应该是在归档日志模式中。两个系统函数将会唤醒实例来开始、关闭热备份处理（pg_start_backup(), pg_stop_backup()）。在开始进一步进行在线热备前，让我们讨论一下对于在线备份中强制的数据库归档模式。

开启 WAL（预写式日志）归档:

下面将简要介绍一下 PITR/调整 WAL 等等。目前，我们先看看WAL归档。在PostgreSQL数据库系统，实际上数据库“写”一些额外被称为预写日志（WAL）文件到磁盘。它包含了一些在数据库系统中的写记录。在崩溃的情况下，数据库可以从这些记录中还原或恢复。

一般地，写日志记录会在定期匹配时（叫做checkpoints,检查点）记录该检查点，然后在它不再需要时删除它。你也可以使用WAL作为备份，因为它是一个所有数据库的写记录。（我注：就是更改数据库的操作）。

WAL归档概念:

WAL是由每16MB大小（我注：文件）组成的，这被称为segments（段）。WAL驻留在pg_xlog目录下，这是一个位于数据目录下的子目录。文件名会被PostgreSQL实例按数字升序来命名，执行一个WAL基础备份，这需要一个基础备份，一个数据目录的完整备份，并且WAL段会介于基础备份和当前日期之间。

配置WAL段归档，可以通过在postgresql.conf里的两个配置参数来设置:archive_command和archive_mode。使集群进入归档模式需要重启PostgreSQL。

1
2

archive_mode= on/off (boolean parameter) 
archive_command = 'cp –i %p /Archive/Location/f% '

注意：%p为通过路径来复制文件来作为一个文件名，%f没有为目标文件设置目录。（我注：也就是%p代表pg_xlog的绝对路径的文件，%f表示pg_xlog目录下的文件名，所以%p前没有目录，%f前有目录前缀）。

关于归档进程的更加多信息，请参考“PostgreSQL 9.0 内存 & 进程”

在线备份 :

采取在线备份：

1
2
3
4
5
6
7
8
9
10

步骤 1 : 在psql终端执行 pg_start_backup('lable')  
postgres=# select pg_start_backup('fb'); 
步骤 2 : 操作系统级别地复制 $PGDATA 目录到任何一个备份的位置。
$ cp -r $PGDATA  /anylocation 
步骤 3 : 在psql终端执行 pg_stop_backup()
postgres=# select pg_stop_backup(); 
注意：这两个函数不需要在数据库的同一个会话里执行。备份模式是全局的并且是持久的。

在PostgreSQL中，没有目录来保存在线备份的开始时间和结束时间。然而，当在线备份正在进行时，会有数个文件会被创建和删除。

pg_start_backup('label')和pg_stop_backup是两个执行在线备份的系统函数。通过pg_start_backup('label')会创建一个文件backup_label在$PGDATA目录下，通过pg_stop_backup()会创建一个文件wal-segement-number.backup在$PGDATA/pg_xlog目录下。backup_label会给出开始时间以及WAL(预写式日志）段的检查点位置，也会通知PostgreSQL实例是处于备份模式。在$PGDATA/pg_xlog目录下的wal-segment-number.backup文件描述了开始和停止时间，带有WAL段号的检查点位置。

注意： 在pg_stop_backup()之后，PostgreSQL实例就会删除backup_label文件。

提交你的评论，建议。

—Raghav

By Raghavendra

原文
作者：Raghav

在PostgreSQL构架基础上进一步了解，在这里，通过信息链接我将会讨论关于实用进程和内存。许多提交者已经好好地记录了关于进程和内存，在这里有提供链接。在我这里有适当关于PostgreSQL实用进程的描述。

每个PostgreSQL实例启动，会有一组实用进程（包括强制性和可选性进程）和内存。两个强制性进程（bgwriter后台写进程和walwriter预写式日志写进程）。你可以通过命令ps -ef | grep postgres检测一下，结果如图10.1.

图10.1

进程和内存概要

图10.2

关于图10.2，它表明了进程附加到PostgreSQL共享内存。

BGWriter/Writer Process后台写进程或者叫写进程:

后台写进程或者叫写进程是一种强制性进程:

所有PostgreSQL服务器进程从磁盘读取数据然后将它们移到共享缓冲池（Shared Buffer Pool）里。 共享缓冲池使用ARC算法或者LRU（最近最少使用）机制来淘汰页数据。BGWRITER后台写进程很多时候都是在休眠，但每次唤醒，它通过搜索共享缓冲池（Shared Buffer Pool）来寻找被修改的页。每次搜索完之后，BGWRITER后台写进程就会选择那些被修改的页，将它们写到磁盘，然后将它们从共享缓冲池里淘汰出来。后台写进程通过三个参数BGWRITER_DELAY、BGWRITER_LRU_PERCENT以及BGWRITER_LRU_MAXPAGES来控制。

http://www.enterprisedb.com/docs/en/9.0/pg/kernel-resources.html
http://www.enterprisedb.com/docs/en/8.4/pg/runtime-config-resource.html

WAL Writer Process预写式日志写进程:

预写式日志写进程是一个强制性进程。

预写式日志写进程在适当间隔时会写入并进行文件同步。为了保证事务安全，预写式日志缓冲区在事务日志里持有数据库的更改操作。预写式日志缓冲区在每次事务提交时写到磁盘，预写式日志写进程负责写到磁盘。WAL_WRITER_DELAY参数是用于调用预写式日志写进程的，然而，还有其他参数同样会使预写式日志写进程比较繁忙。下面有一些链接。

http://www.enterprisedb.com/docs/en/8.4/pg/wal-configuration.html

Stats Collector Process状态收集进程:

状态收集进程是可选进程，默认是开启的。

状态收集进程会收集一些关于服务器运作的信息。它会计算访问表和索引二者磁盘块的数量和个别的行项数（我注：一个block有可能多个row item，可以通过 select ctid from tbname来查看，第一个数字就是block数，第二个就是row item数)。它同样会跟踪每一个表的总行数，每一个表关于VACUUM（清理）和ANALYZE（分析）动作的信息。收集这些统计数据会对查询执行有额外的开销，自己决定收不收集这些信息。以下的链接有更多关于状态收集进程以及相关参数的说明。

http://www.enterprisedb.com/docs/en/9.0/pg/monitoring-stats.html

Autovacuum Launcher Process自动清理启动器进程:

自动清理进程是一个可选进程，默认是开启的。

为了自动执行VACUUM和ANALYZE命令，自动清理启动器进程是由许多被称为autovacuum workers(自动清理工作者)组成的后台进程。自动清理启动器进程负责启动autovacuum workers(自动清理工作者)进程来处理所有数据库。启动器会按交叉时间地分发工作，在每个时间间隔里会试图在每一个数据库里启动一个工作者（我注：指autovacuum workers），通过参数autovacuum_naptime来设置间隔时间。每个数据库都会启动一个工作者，通过参数autovacuum_max_workers来设置最大数。每一个工作者进程都会在它所在的数据库里检查每一张表，然后在有需要的时候执行VACUUM或者ANALYZE命令。以下的链接有更多关于AUTOVACUUM自动清理启动器进程的相关参数的说明。

http://www.enterprisedb.com/docs/en/8.4/pg/runtime-config-autovacuum.html

Syslogger Process / Logger Process系统日志进程或者叫日志进程 :

图10.3

日志是一个可选进程，默认是关闭的。

依据图10.3， 可以清楚地理解所有 实用进程+用户后台进程 + Postmaster守护进程都附加到系统日志进程来记录这它们的活动信息。每一个进程信息都会被记录在PGDATA/pg_log 目录下的.log文件里。
注意：如果数据目录是通过INITDB命令创建的，pg_log目录不会在数据目录里自动创建。需要显式地创建该目录。

调试更多的进程信息会导致服务器的一些额外开销。总是建议日志是最低级别的，如果有要求的话再提高调试级别。以下的链接有更多关于日志参数的说明。

http://www.enterprisedb.com/docs/en/8.4/pg/runtime-config-logging.html

Archiver Process归档进程:

图10.4

归档进程是可选进程，默认是关闭的。

上面图10.4 是从我观察PostgreSQL的归档进程而制作的。设置数据库为归档模式，意味着捕捉预写式日志（WAL）数据填充到每个段文件。在段文件重新回收利用之前，会将数据保存到某些地方。

图中每个数字标签的解释。

1.在数据库的归档模式，一旦预写式日志（WAL）数据填充满了预写式日志（WAL）段文件，填充满的段文件会被预写式日志写进程（WAL Writer）在目录$PGDATA/pg_xlog/archive_status下创建一个后缀为”.ready”的文件。文件名将会是“段文件名.ready”。

2.归档进程就会触发去查找那些被预写式日志写进程创建的“.ready”状态的文件。归档进程选择那些后缀是”.ready”的”段_文件号”文件，然后从$PGDATA/pg_xlog复制这些文件到archive_command参数（在postgresql.conf）指定的目的地里。

3.成功地从源目录复制到目的目录，归档进程会重命名”段-文件名.ready”为段-文件名.done。这就完成了归档的过程。

不用说，如果在$PGDATA/pg_xlog/archive_status目录里有任何名为”段-文件名.ready”的文件都是正等待着被复制到归档目的地里（我注：通过参数archive_command来指定）。

更多关于参数和归档的信息，请看以下链接。

http://www.enterprisedb.com/docs/en/9.0/pg/continuous-archiving.html

请把你的意见/建议提交在这篇文章中,将不胜感激。

献上我真诚的问候
Raghav

原文

作者：Raghavendra

很高兴在这里发布我的第一篇博客，是关于 PostgreSQL 构架的。

在很长一段时间里，我在工作、学习上都广泛地接触PostgreSQL。作为一个初学者，想到尝试给出一张关于 PostgreSQL 的架构图。PostgreSQL构架包括几部分：内存、进程和文件存储系统，这难以在一张图里展示所有东西。我尽我所能地给出一个关于PostgreSQL构架的概要。

大部分的设计都是在我们的PostgreSQL提交者（Heikki,Robert Haas,Bruce）的帮助下完成的， 我从他们身上学习到了很多关于PostgreSQL内部的东西。 非常感谢他们的协作让我了解到关于PostgreSQL的一切。我不是黑客，也不是构架师，仅仅是为PostgreSQL新手写了一篇文章。请留下你的评论、建议或者发现到我写文章的任何错误也可留言。

PostgreSQL 9.0 构架概述

PostgreSQL实例由一系列进程和内存组成。PostgreSQL 使用一个简单的 “每个用户一个进程” 的 客户/服务器 模型。PostgreSQL 有许多种类型进程。

• postmaster进程，是后台监听进程，postmaster附加到共享内存段（我注：其实就是通过共享内存来进行进程间的通信），但是尽量避免访问它（我注：避免我们自定义去访问该共享内存，而是由PG内部各进程进行协调）。

• 实用进程（bgwriter后台写进程，walwriter预写式日志写进程，syslogger系统日志进程，archiver归档进程，statscollector状态收集器进程 以及 autovacuum自动清理进程）以及

• 用户后台进程（postgres进程自身，服务器进程）

当有一个客户端请求连接到数据库时，首先，请求被postmaster后台进程执行身份认证，受权之后会复制一个服务器后台进程（postgres进程）来处理该请求。从那时起，客户端进程和服务器端进程进程通信，而不再需要postmaster介入。因此，postmaster进程是一直在运行的，一直等待连接请求，然而客户端和服务器端进程会继续进行通信。libpq库允许一个单客户端连接到多个服务器进程。

然而，每个后台进程都是单线程的，一次仅仅只能执行一条查询；所以，任何的一个前端-后台连接都是单线程的。postmaster进程和postgres进程都是以PostgreSQL的”超级用户”身份的用户ID来运行的。每个打开数据库的会话里都会存在一个postgres进程。一旦经过身份验证的用户连接,它就会与共享内存直接连接（与谁，目的是做什么）。

内存

• Shared Buffers，共享缓冲区
• WAL Buffers，预写式日志缓冲区
• clog Buffers，是一种 SLRU 类型的缓冲区(Commit log，提交日志缓冲区）
• Other Buffers，其他缓冲区

PostgreSQL共享内存是非常大的并且所有缓冲区都没有同步的，这意味着都是独立的。一些专家/提交者已经将他们的大量关于PostgreSQL的经验信息放在网站上。结合PostgreSQL文档和这个构架图就会对PostgreSQL构架的有个基础的了解。以下链接有更多概述.

http://www.postgresql.org/docs/9.0/interactive/runtime-config-resource.html
http://www.enterprisedb.com/docs/en/8.4/pg/runtime-config-resource.html
http://www.postgresql.org/files/documentation/books/aw_pgsql/hw_performance/0.html

实用进程:

强制性进程：这些进程是没有选项来 开启/关闭 的

• BGWriter

• WAL Writer

可选进程：这些进程是有选项来 开启/关闭 的

• Stats-collector，状态收集进程
• Autovacuum launcher，自动清理进程
• Archiver，归档进程
• Syslogger，系统日志进程
• WAL Sender，预写式日志发送进程
• WAL Receiver，预写式日志接收进程

不久，我将会提交一张关于实用性进程和用户后台进程的概要图

献上我真诚的问候
Raghav

栈

实现也很简单，只需要一个一维数组和一个指向栈顶的变量 top 就可以了。我们通过 top 来对栈进行插入和删除操作。

特点：后进先出

利用栈判断是否回文（java实现）

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

public static void main(String[] args) {
    char[] character = { 'a', 'a', 'h', 'a', 'a' };
    char[] stack = new char[10];
    int top = -1;
    int mid = character.length % 2 == 0 ? character.length / 2 - 1 : character.length / 2;
    for (int i = 0; i <= mid; i++) {
        top++;
        stack[top] = character[i];
    }
    if (character.length % 2 == 0) {
        mid++;
    }
    for (int i = mid; i < character.length; i++) {
        if (top >= 0) {
            if (stack[top] != character[i]) {
                break;
            }
        }
        top--;
    }
    if (top == -1) {
        System.out.println("YES");
    } else {
        System.out.println("NO");
    }
}

列队的主要特点：先进先出

文中题目

规则是这样的：首先将第 1个数删除，紧接着将第 2 个数放到这串数的末尾，再将第 3 个数删除并将第 4 个数放到这串数的末尾，再将第 5 个数删除……直到剩下最后一个数，将最后一个数也删除。按照刚才删除的顺序，把这些删除的数连在一起就是小哈的 QQ啦.

Java实现

例如：加密过的一串数是 “6 3 1 7 5 8 9 2 4”，输出应该是“6 1 5 9 4 7 2 8 3”

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

public static void main(String[] args) {
    int[] array = { 6, 3, 1, 7, 5, 8, 9, 2, 4 };
    int[] queue = new int[100];
    int head = 0;
    int tail = 0;
    for (int i = 0; i < array.length; i++) {
        queue[i] = array[i];
        tail++;
    }
    while (head < tail) {
        System.out.println(queue[head]);
        head++;
        queue[tail] = queue[head];
        tail++;
        head++;
    }
}

基本思想

每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的一边，将大于等于基准点的数全部放到基准点的另一边.

时间复杂度

因此快速排序的最差时间复杂度和冒泡排序是一样的，都是 O(N^2 )，它的平均时间复杂度为 O(NlogN)。

Java实现（从大到小）

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

public static void main(String[] args) {
    int length = 20;
    int maxValue = 20;
    int[] array = new int[length];
    Random r = new Random();
    for (int i = 0; i < array.length; i++) {
        array[i] = r.nextInt(maxValue);
    }
    System.out.println(Arrays.toString(array));
    quickSort(array, 0, length-1);
    System.out.println(Arrays.toString(array));
}
 
 
// 假设以左边的为基数，那就要从右边开始移动。左为大于基数，右为小于基数
public static void quickSort(int[] array, int leftPoint, int rightPoint) {
    if (leftPoint > rightPoint) {
        return;
    }
    int swapTmp = 0;
    int baseNumber = array[leftPoint];// 以左边为基准
    int i = leftPoint;
    int j = rightPoint;
    while (leftPoint != rightPoint) {
        // 从右边开始向左移动，到找第一个大于基数时停止
        while (array[rightPoint] <= baseNumber && leftPoint < rightPoint) {
            rightPoint--;
        }
 
        // 从左边开始向右移动，到找第一个小于基数时停止
        while (array[leftPoint] >= baseNumber && leftPoint < rightPoint) {
            leftPoint++;
        }
 
        // 没有相遇时，就交换
        if (leftPoint < rightPoint) {
            swapTmp = array[leftPoint];
            array[leftPoint] = array[rightPoint];
            array[rightPoint] = swapTmp;
        }
    }
    //恢复新一轮的基准，将旧的基准归位，然后又重新定一个新的左边基准位。即将基准数与中间数互换
    array[i] = array[leftPoint];
    array[leftPoint] = baseNumber;
 
    //递归左，右两边
    quickSort(array, i, leftPoint-1);
    quickSort(array, leftPoint+1, j);
}

基本思想

冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。

以从大到小为例。

每次都是比较相邻的两个数，如果后面的数比前面的数大，则交换这两个数的位置。一直比较下去直到最后两个数比较完毕后，最小的数就在最后一个了。就如同是一个气泡，一步一步往后“翻滚” ，直到最后一位。所以这个排序的方法有一个很好听的名字“冒泡排序” 。

每将一个数归位我们将其称为“一趟” 。每一趟，都是将小的归位（先是最小，后次小，次后第三小…）。

如果有 n 个数进行排序，只需将 n-1 个数归位，也就是说要进行n-1 趟操作。而“每一趟”都需要从第 1 位开始进行相邻两个数的比较，将较小的一个数放在后面，比较完毕后向后挪一位继续比较下面两个相邻数的大小，重复此步骤，直到最后一个尚未归位的数， 已经归位的数则无需再进行比较 （已经归位的数你还比较个啥， 浪费表情） 。

核心思想

冒泡排序的核心部分是双重嵌套循环。

时间复杂度：O（N^2）

Java实现

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

public static void main(String[] args) {
    int length = 10;
    int maxValue = 20;
    int[] array = new int[length];
    Random r = new Random();
    for (int i = 0; i < array.length; i++) {
        array[i] = r.nextInt(maxValue);
    }
    System.out.println("before");
    print(array);
    bubbleSort(array);
    System.out.println("after");
    print(array);
}
 
 
public static void bubbleSort(int[] array) {
    int tmp = 0;
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length-1; j++) {
            if (array[j] < array[j+1]) {//如果前一个比后一个小，则进行交换。这样子就可以是从大到小。
                tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
            }
        }
    }
}
 
 
public static void print(int[] array) {
    System.out.println(Arrays.toString(array));
}

总结

冒泡比较耗时

时间复杂度：O(M+N)

M:桶的个数（也是该数值的最大数）
N:待排序个数

Java实现

随便输入N个不大于M的数字，然后从小到大输出：（从大到小，作一下小修改即可）

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

public static void main(String[] args) {
    int M= 100;
    int N = 5;
    int[] array = new int[M+ 1];
    Scanner scan = new Scanner(System.in);
    int in = 0;
    for (int i = 0; i < N; i++) {
        in = scan.nextInt();
        array[in] = array[in] + 1;
    }
 
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array[i]; j++) {
            System.out.println(i);
        }
    }
}

个人总结

这种算法适合于范围比较小的排序，并且是需要知道输入的最大值。不然就不适用了。

假设有个评论系统，要求支持无限层级的回复，就像一棵树那样

1
2
3
4
5

       文章
     /      \
    /        \
评论1     评论2
....

注意可以有任意个子树以及做任意个叶子

大意的表结构

1
2
3
4
5
6
7
8

create table comments (
    comment_id serial primary key,
    parent_id bigint,
    bug_id bigint not null,
    author varchar(20) not null,
    comment text not null,
    foreign key (parent_id) references comments(comment_id)
);

1
2
3
4
5
6
7
8
9
10
11

test=# select * from comments;
 comment_id | parent_id | bug_id | author |       comment      
------------+-----------+--------+--------+---------------------
          1 |           |      1 | Fran   | 这个bug的成因是什么
          2 |         1 |      1 | Ollie  | 我觉得是一个空指针
          3 |         2 |      1 | Fran   | 不，我查过了
          4 |         1 |      1 | Kukla  | 我们需要查无效输入
          5 |         4 |      1 | Ollie  | 是的，那是个问题
          6 |         4 |      1 | Fran   | 好，查一下吧
          7 |         6 |      1 | Kukla  | 解决了
(7 rows)

SQL语句

利用递归查询，可以查某篇文章评论组成的树结构。其中 depth是树的深度，显示的时候，按已经排序好的层次及相应的父结点显示出来就可以了。

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

test=# with RECURSIVE  commenttree (comment_id, bug_id, parent_id, author, comment, depth) as (select comment_id, bug_id, parent_id, author, comment , 0 as depth from comments where parent_id is null union all select c.comment_id, c.bug_id, c.parent_id, c.author, c.comment, ct.depth+1 as depth from commenttree as ct join comments as c on (ct.comment_id = c.parent_id)) select * from commenttree where bug_id = 1;;
 comment_id | bug_id | parent_id | author |       comment       | depth
------------+--------+-----------+--------+---------------------+-------
          1 |      1 |           | Fran   | 这个bug的成因是什么 |     0
          2 |      1 |         1 | Ollie  | 我觉得是一个空指针  |     1
          4 |      1 |         1 | Kukla  | 我们需要查无效输入  |     1
          3 |      1 |         2 | Fran   | 不，我查过了        |     2
          5 |      1 |         4 | Ollie  | 是的，那是个问题    |     2
          6 |      1 |         4 | Fran   | 好，查一下吧        |     2
          7 |      1 |         6 | Kukla  | 解决了              |     3
(7 rows)
 
test=#

注意PostgreSQL里，必须加 RECURSIVE 才能支持递归。

内容来源资料：
[1]《SQL反模式》