据说全栈路线图是这样的，详细地连 DevOps 都不得不被掩盖住一截。
[图片上传失败...(image-930165-1509644610359)]](http://upload-images.jianshu.io/upload_images/2558748-d3e0d4da018a1d3a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
全栈工程师，Full Stack Developer，常是一个较为敏感的话题，一如深度还是广度好，一如精读还是粗读好一样。你可以说，接下来步入的整个项目是一个实为 Node.JS 的伪全栈项目，但作为有志青年来讲，“全栈”足以时刻提醒自己是面向软件工程专业和互联网行业学习，找的是不去惯性局限自己视野的一股劲。毕竟：
「任何一个 Facebook 的问题，都不是别人的问题」
这次，利用 ThoughtWorks 校企实验室的团队项目机会，带来一个 React.js + Node.js 技术栈的全栈实战项目：基于番茄工作法的番茄时钟：“番茄post”。该项目将作为自己和团队的练手项目，并及时更新进度。同时，这一路走下去，也将是一场软件工程的项目实战，对理解软件开发流程模型很有帮助。
有了小产品理想，画大饼很简单，但要能够搭建一个足以依靠敏捷开发稳步推进的软件开发流程，以大学生的能力还不足以直接上手。这次，多亏了 ThoughtWorks IT 咨询师，同任我们实验室老师的 @TW李鹏 老师对功能分析的指导，让我们理解了项目前期对功能分析和设立多个目标里程碑的重要性并能予落实。引用老师的话来说，拆分项目里程碑，有如下优缺点。
这样带来的好处是：
* 我们每个里程碑所需要考虑的问题变小，易于分析、思考和掌控
* 每个里程碑要学习的东西比较集中，不会迷失
* 每个里程碑结束，有一个完整可用的产品，能够产生价值，也能够给自己带来成就感
* 如果在假期中时间或者精力不够了，可以放弃后面的里程碑，至少可以做出功能较少但是可用的东西出来，而不是一个很大但是没法使用的半成品
带来的问题是：
* 为了保证每个里程碑功能的完整，有时候需要在过程中添加一些额外的功能，而这些功能在最后可能会被丢弃，有额外的工作量
* 新的里程碑的功能可能会在之前的功能上修改，如何保证之前的功能不被破坏，需要一定的技巧
随着我们接下来对“番茄post”全栈项目的推进和文章总结，这将是一场程序员的技术战，也将是一场工程师的身心战，智慧与勇毅将带来最终的成果。
程序功能分析
“番茄post” 基于番茄工作法，旨在向用户提供个性化、社区化的时间管理环境，提高工作效率，改善生活品质，经过功能拆解历程，它的前期版本将具有以下功能：
- 发布番茄：每发布一个番茄，记录刚刚发布的一个番茄工作内容。
- 展示番茄：将发布的所有番茄内容能够展示出来。
- 登录/注册：可以向多个用户提供服务。
- 关注他人：增加用户多维链接，促进双向激励。
- 评论番茄：促进用户交流、鼓励。
- 番茄排行：展示热门番茄，让用户有所榜样。
功能拆解历程
根据“有社区的番茄工作法软件”为目标同时列出的有添加番茄、暂停番茄等与前端视觉效果有关的功能并以为然作为重点，经过老师带领我们对产品需求进行的细细挖掘下发现，“番茄post”需要解决的核心需求点在于：
- 改善用户拖延症、焦虑症、提高用户工作效率
- 解决能够随时看到他人近期完成的基于番茄工作法的内容来激励自己
- 满足用户间对于时间管理、个人成长等平台话题的社交渴求
- 能和任意平台用户一起指定多日番茄计划互相监督互相激励
以上大部分强调的是，“番茄post”更偏向社交化时间管理，前期应削弱对番茄的前端功能效果实现而重在搭建能够发布番茄、社交激励的社区平台。
以下里程碑结合功能复杂度和技术难点进行前期划分。
第一个里程碑：搭架子
平台开发环境第一性，提前了解将要使用的技术将决定架子的内在。考虑到平台多样性和团队精力的有限性，以下列出的开发环境将作为第一版出现。
- 用户平台：Web 浏览器
- 编程语言：JavaScript
- 前端框架：React.js
- 运行环境：Node.js
- 构建工具：NPM
最终，只需要能够运行出一个简单的 Hello World 页面即可。
验收条件
- 其他人可以方便的获取你的代码(Github)。
- 其他人可以通过你的说明文件，在本地将服务器快速的运行起来，看到页面(README.md)。
- 通过简单的页面可以证明你使用的技术栈和主要的库等已经配置正确；
- 代码以“小步”方式提交到github上，并且每个commit都有清楚的描述；
- 若干篇博客用来记录你的学习收获和疑问。
第二个里程碑：数据库搭建和番茄的发布及其页面
最基本的功能是对番茄的“增删改查”，在这个里程碑中，我们先实现对番茄的发布，即增加到数据库中。制作番茄发布页面。
验收条件
- 任何人可以在账号密码正确的情况下访问数据库；
- 数据库中的相关番茄表单结构确立并能够看到；
- 任何人都可以看到番茄发布页面里有一个输入框和发布番茄按钮；
- 任何人都可以通过输入框填补番茄内容并点击发布按钮发布一个番茄；
- 点击发布番茄按钮后的相关错误提示信息能够得到展示；
- 发布番茄后，数据库里要能够看到该番茄及其内容和发布时间；
- 代码以“小步”方式提交到github上，并且每个commit都有清楚的描述；
- 若干篇博客用来记录你的学习收获和疑问。
第三个里程碑：番茄的展示与删除及其页面
这一步，在我们将番茄及其相关信息更新到数据库后，要能够将数据读取出来并在前台展示，提供删除按钮并能删除成功。番茄的展示与删除的页面和番茄发布页面同为一个页面之下，名为用户个人主页页面。
验收条件
- 任何人都可以看到所有已经发布了的番茄；
- 任何人都可以删除所有已经发布了的番茄；
- 删除番茄后，该番茄将从数据库中删除并不会再展示到前台；
- 代码以“小步”方式提交到github上，并且每个commit都有清楚的描述；
- 若干篇博客用来记录你的学习收获和疑问。
第四个里程碑：登录/注册功能及相关页面
之前的里程碑都在于搭建针对单独用户的核心功能，这一步来搭建用户平台。
验收条件
- 任何人都可以访问登录、注册页面；
- 任何人都可以注册一个没有被注册的账号；
- 任何人在某账号和密码匹配的情况下都可以登录该账号；
- 登录、注册过程中的相关错误信息能够得到展示；
- 登录成功后，可以访问自己的番茄发布与展示页面；
- 代码以“小步”方式提交到github上，并且每个commit都有清楚的描述；
- 若干篇博客用来记录你的学习收获和疑问。
第五个里程碑：番茄首页
这时，每一位用户都有自己的个人主页页面并能通过发布、删除番茄来更新自己的时间管理记录。番茄首页将着手打造番茄社交环境，用来展示所有已注册过的用户，提供社交链接。
验收条件
- 任何人都可以访问番茄主页；
- 任何人都能看到番茄主页下展示的所有已注册过番茄平台的用户；
- 任何人都能看到番茄主页下提示的登录、注册按钮并可以点击；
- 代码以“小步”方式提交到github上，并且每个commit都有清楚的描述；
- 若干篇博客用来记录你的学习收获和疑问。
第六个里程碑：关注他人与被他人关注
这一步：关注他人。
验收条件
- 任何人都可以访问某位用户的个人主页；
- 任何人都可以看到某位用户的个人主页的他关注的人和关注他的人；
- 任何人都可以看到某位用户的个人主页下有关注该用户按钮；
- 任何人在点击关注该用户按钮后判断是否登录；
- 任何人在关注、登录过程中的相关错误信息能够得以展示；
- 任何人在成功关注某位用户后可以在该用户个人主页的关注他的人下看到自己；
- 任何人在成功关注某位用户后可以在自己的个人主页的我关注的人下看到该用户；
- 任何人在成功关注某位用户后再次访问该用户主页时，关注按钮变成已经关注的提示。
- 代码以“小步”方式提交到github上，并且每个commit都有清楚的描述；
- 若干篇博客用来记录你的学习收获和疑问。
第七个里程碑：番茄评论
验收条件
- 任何人可以看到每个已经发布的番茄旁有评论框和评论按钮；
- 任何人在没有登录情况下可以看到评论框和按钮无法编辑和点击并有登录提示；
- 任何人在登录的情况下可以评论某个番茄；
- 评论成功后能看到该番茄下的最新评论；
- 每个番茄下的评论按最新时间由上到下排列；
- 代码以“小步”方式提交到github上，并且每个commit都有清楚的描述；
- 若干篇博客用来记录你的学习收获和疑问。
第八个里程碑：番茄网站上线
正式上线至某 IP 地址或某域名下。
验收条件
- 将数据库部署至线上；
- 番茄平台所有功能在线上调试成功；
- 任何人能够通过互联网访问番茄首页并进行深入操作；
- 代码以“小步”方式提交到github上，并且每个commit都有清楚的描述；
- 若干篇博客用来记录你的学习收获和疑问。
更多内容，尽请期待
“番茄post”的里程碑写到这里，可以看到，还有很多细节没有深入讨论。在敏捷的软件开发流程下，鉴于我们开发者也一直在梳理需求且需求会随时回炉重塑，先开发出一个可用可见的真实产品出来再看进一步发展。
软件生存期模型是跨越整个生存期的系统开发、运作和维护所实施的全部过程、活动和任务的结构框架，其中就包括增量模型这一软件开发模型，很符合这一次任务的开发流程，图例如下。
更多内容，持续更新中~。
- Hello，我是韩亦乐，现任本科软工男一枚。软件工程专业的一路学习中，我有很多感悟，也享受持续分享的过程。如果想了解更多或能及时收到我的最新文章，欢迎订阅我的个人微信号：韩亦乐。我的简书个人主页中，有我的订阅号二维码和 Github 主页地址；我的知乎主页 中也会坚持产出，欢迎关注。
- 本文内部编号经由我的 Github 相关仓库统一管理；本文可能发布在多个平台但仅在上述仓库中长期维护；本文同时采用【知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议】进行许可。
最早拥有排序概念的机器出现在 1901 至 1904 年间由 Hollerith 发明出使用基数排序法的分类机，此机器系统包括打孔，制表等功能，1908 年分类机第一次应用于人口普查，并且在两年内完成了所有的普查数据和归档。
Hollerith 在 1896 年创立的分类机公司的前身，为电脑制表记录公司（CTR）。他在电脑制表记录公司（CTR）曾担任顾问工程师，直到1921年退休，而电脑制表记录公司（CTR）在1924年正式改名为IBM。
---- 摘自《维基百科 - 插入排序》
期中已到，期末将至。《算法设计与分析》的“预习”阶段藉此开始~。在众多的算法思想中，如果你没有扎实的数据结构的功底，不知道栈与队列，哈希表与二叉树，不妨可以从排序算法开始练手。纵观各类排序算法，常见的、经典的排序算法将由此篇引出。
排序算法的输出必须遵守的下列两个原则：
- 输出结果为递增序列（递增是针对所需的排序顺序而言）
- 输出结果是原输入的一种排列、或是重组
十大经典的排序算法及其时间复杂度和稳定性如上表所示。判断一个排序算法是否稳定是看在相等的两个数据排序算法执行完成后是否会前后关系颠倒，如若颠倒，则称该排序算法为不稳定，例如选择排序和快速排序。
排序前：(4, 1) (3, 1) (3, 7)（5, 6）
排序后：(3, 1) (3, 7) (4, 1) (5, 6) （稳定，维持次序）
排序后：(3, 7) (3, 1) (4, 1) (5, 6) （不稳定，次序被改变）
00.交换两个整数的值
接下来十个经典排序算法的详细探讨缺少不了交换两个整数值的掌握，这里回顾一下其中三种方交换法：用临时变量交换两个整数的值(SwapTwo_1)、不用第三方变量交换两个整数的值(SwapTwo_2)、使用位运算交换两个整数的值(SwapTwo_3)。其中用临时变量交换两个整数的值效率最高，后俩者只适用于内置整型数据类型的交换，并不高效。
void SwapTwo_1 (int *a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void SwapTwo_2 (int *a, int *b) {
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
void SwapTwo_3 (int *a, int *b) {
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
01. 冒泡排序(BubbleSort)
先不说公司面试笔试，大学实验室的纳新题里最常有的就是冒泡排序。冒泡排序重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。
[图片上传失败...(image-6edc3d-1509644592135)]](http://upload-images.jianshu.io/upload_images/2558748-990f8de3fbdbb50d.gif?imageMogr2/auto-orient/strip)
上图可见，冒泡排序算法的运作如下：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
通俗来讲，整个冒泡排序就是通过两次循环，外层循环将此轮最大(小)值固定到此轮尾部，内层循环“冒泡”比较相邻的两个元素并决定是否交换位置。
从上图也可理解冒泡排序如何将每一轮最大（小）值固定到此轮尾部：尾部总为有序状态，前面无序状态区根据大小规则冒泡向后方传递最值。
/*
* 冒泡排序。每次外循环将最值固定到数组最后
* @param: {int []} arr
* @param: {int} len
* @return null;
*/
void BubbleSort (int arr[], int len) {
int i, j, temp;
for (int i = 0; i < len - 1; i++) {
// 每趟 i 循环将最大(小)值固定到最后一位
for (int j = 0; j < len - 1 - i; j++) {
// 每趟 j 循环循环没有被固定到后方的数字
if (arr[j] > arr[j + 1]) {
// arr[j] < arr[j + 1] 代表从小到大排序
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
更多十大经典排序算法请戳我的 Github 仓库 @LeetCode-C
02. 选择排序(SelectionSort)
选择排序首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
上图左下角和右上角可以分别看做排序序列起始位置(已排序区)和排序序列末尾(未排序区)，左下角一直稳定更新，但选择排序不稳定，即排序后曾经相同的两个元素的前后位置关系可能会发生颠倒。
/*
* 选择排序。每次外循环选择最值固定到数组开始
* @param: {int []} arr[]
* @param: {int} len
* @return null;
*/
void SelectionSort (int arr[], int len) {
int i, j, temp, min;
for (i = 0; i < len - 1; i++) {
min = i;
for (j = i + 1; j < len - 1; j++) {
if (arr[min] > arr[j]) {
// 只需找到最小的值的位置后一次性替换
min = j;
}
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}
更多十大经典排序算法请戳我的 Github 仓库 @LeetCode-C
03. 插入排序(InsertionSort)
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place
排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤 2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找插入排序。这里先不做涉及。
/*
* 插入排序。前面有序的数字循环向后留给满足条件的第一个无序数字
* @param: {int []} arr
* @param: {int} len
* @return null;
*/
void InsertionSort (int arr[], int len)
{
int i, j, temp;
for (i = 1; i < len; i++) {
// 与已排序的数逐一比较，大于 temp 时，该数向后移
temp = arr[i];
// 如果将赋值放到下面的for循环内, 会导致在第10行出现 j 未声明的错误
j = i - 1;
for (; j >= 0 && arr[j] > temp; j--) {
// j 循环到-1时，由于短路求值，不会运算 arr[-1]
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
// 被排序数放到正确的位置
}
}
更多十大经典排序算法请戳我的 Github 仓库 @LeetCode-C
04. 希尔排序(ShellSort)
希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。希尔排序也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
- 插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。
已知的最好步长序列是由 Sedgewick 提出的(1, 5, 19, 41, 109,...)，这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
/*
* 希尔排序。
* @param: {int []} arr
* @param: {int} len
* @return null;
*/
void ShellSort(int arr[], int len) {
int gap, i, j;
int temp;
for (gap = len >> 1; gap > 0; gap >>= 1) {
// gap 为间隔，每次间隔折半
for (i = gap; i < len; i++) {
// 循环该轮数组后半段
temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
// 根据当前 grap 间隔和条件进行插入排序前的后移
arr[j + gap] = arr[j];
}
// 插入到当前位置
arr[j + gap] = temp;
}
}
}
更多十大经典排序算法请戳我的 Github 仓库 @LeetCode-C
05. 归并排序(MergeSort)
归并排序是创建在归并操作上的一种有效的排序算法，效率为 O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
归并排序用迭代法和递归法都可以实现，迭代法的算法步骤为：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
递归法的算法步骤为：
- 将序列每相邻两个数字进行归并操作，形成 floor(n/2) 个序列，排序后每个序列包含两个元素
- 将上述序列再次归并，形成 floor(n/4) 个序列，每个序列包含四个元素
- 重复步骤 2，直到所有元素排序完毕
/*
* 归并排序。迭代版
* @param: {int []} arr
* @param: {int} len
* @return null;
*/
void MergeSort_1 (int arr[], int len) {
int* a = arr;
int* b = (int*) malloc(len * sizeof(int));
int seg, start;
for (seg = 1; seg < len; seg += seg) {
for (start = 0; start < len; start += seg + seg) {
int low = start, mid = Min (start + seg, len), high = Min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
int* temp = a;
a = b;
b = temp;
}
if (a != arr) {
int i;
for (i = 0; i < len; i++)
b[i] = a[i];
b = a;
}
free(b);
}
int Min(int x, int y) {
return x < y ? x : y;
}
/*
* 归并排序。递归版
* @param: {int []} arr
* @param: {const int} len
* @return null;
*/
void MergeSort_2 (int arr[], const int len) {
int reg[len];
merge_sort_recursive(arr, reg, 0, len - 1);
}
void merge_sort_recursive (int arr[], int reg[], int start, int end) {
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 <= end1)
reg[k++] = arr[start1++];
while (start2 <= end2)
reg[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
总结【上】
这篇文章“十大经典排序算法及其 C 语言实现【上】”引出了十大经典算法的前五个并用 C 语言实践：冒泡排序、选择排序、插入排序、希尔排序和归并排序，并作出了充足的图文解释。即将推出的“十大经典排序算法及其 C 语言实现【下】”将对剩下五个经典算法快速排序、堆排序、计数排序、桶排序、基数排序作出完善，尽请期待~。
- Hello，我是韩亦乐，现任本科软工男一枚。软件工程专业的一路学习中，我有很多感悟，也享受持续分享的过程。如果想了解更多或能及时收到我的最新文章，欢迎订阅我的个人微信号：韩亦乐。我的简书个人主页中，有我的订阅号二维码和 Github 主页地址；我的知乎主页 中也会坚持产出，欢迎关注。
- 本文内部编号经由我的 Github 相关仓库统一管理；本文可能发布在多个平台但仅在上述仓库中长期维护；本文同时采用【知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议】进行许可。
