“2010.11.10讨论笔记” 19:30-22:00 参加人员：宋(主讲)，褚，董，陈（笔记整理）
---------------------分割线---------------------
+++ 应关注算法及其思想的形成过程 +++
内容：
（1）主要讲了四个经典排序算法（插入排序，折半插入排序，并归排序和快速排序），详细地讲述形成这些算法思考过程，以及算法的复杂度分析方法。
（2）分治递归思想。
---------------------分割线---------------------
说明：a. log(n)是指以2为底对n取对数。
b. n^2表示n的2次方。
---------------------分割线---------------------
细节要点：
（1）插入排序和折半插入排序
---- 插入排序
特点： a. 时间复杂度最好为O(n)，最坏为O(n^2)
b.空间复杂度为O(1)
c.稳定的排序方法
PS:a. 排序的稳定性,我来举个例子：
比如排序{2，3，1（第一个），1（第二个），5，6}
不稳定的排序，可能会排出
{1（第二个），1（第一个），2，3，5，6}；
而稳定的排序则不会，在比较的关键字相同的情况下，稳定的排序会将较早出现的元素排在前面。
b. 空间复杂度是指在排序过程中所需占用额外内存的规模（一般用big O法来描述）
类比：理牌的过程。一手牌是分成两部分的，一部分是手上的牌（排好序的），另一部分是未抓的牌（待插入的牌），每次抓一张，就会插入到手中牌合适的位置。
插入排序最坏的比较次数是(n-1)*n/2。固时间复杂度为O(n^2)
能否在此基础上进行改进？
-->由于传统插入排序都是从队尾开始，但这是没有必要的。由于插入的数据已经处于有序状态，因此我们可以从中间进行插入（类似于折半查找），而并非每次都从队尾开始，这就是“折半插入排序”。
折半插入排序时间复杂度分析：假设已经插入k个元素，那么最坏的比较次数就不再是k次了（一般插入排序），而是log(k)次；那么将n个元素排完共需要log(1)+ log(2)+ log(3)+……+log(n)<nlog(n)次，因此折半插入排序的时间复杂度为O(nlog(n))。
（2）分治和递归思想
将问题分治（即将一个大问题分解成一些小问题来解决），再用递归解决一个个小问题，并逐步向上层回溯，直至解决该问题。分治和递归两者是紧密结合的，事实上递归在很多时候就是因为分治策略的使用才出现的。
PS：递归符合人的思维习惯，易于理解，用递归思想写出来的代码简洁优雅；但递归也有其缺点。递归本质是较深的函数调用。函数调用是有系统开销，包括函数寻址，函数参数压栈弹栈，这些都需要CPU时间，而且其所用到的栈由操作系统分配和管理（对程序员透明，无法在外部进行控制），有一个深度限制（也就是说过深的递归会导致程序堆栈溢出，程序终止）。
递归所用到的栈（尽管是由操作系统维护）也需要考虑到空间复杂度中。
（3）归并排序（二路归并）
该算法采用了分治策略和递归思想（当然也可以用循环代替递归）。算法思想：先一路斩断，分解长序列，直到分到每个序列长度都为1时结束；然后是一直归并，但是每次归并实际上是在不同层次函数的递归中调用，一直归并到结束。
时间复杂度：O(nlog(n))（相当稳定，即最好和最坏情况，执行的时间差不多）
空间复杂度：O(n)（用递归实现可能还要考虑递归所用栈的空间）
稳定排序方法
现在我们假设斩断已经完成。
初始状态： [ 6 ] [ 202 ] [ 100 ] [ 301 ] [ 38 ] [ 8 ] [ 1 ]
k=1 ： [ 6 202 ] [ 100 301] [ 8 38 ] [ 1 ]
k=2 ： [ 6 100 202 301 ] [ 1 8 38 ]
k=3 ： [ 1 6 8 38 100 202 301 ]
取两个子序列（k=1时的前2个）
A: 6 202 B: 100 301
然后将两个子序列合并为一个有序序列
C为一个空序列，用来存储最后的结果。合并时保持两个指针，一个指向A中待归并的元素，一个指向B带归并的元素。每次对这两个元素比较，小的进入C序列，指针后移，这样下去直到A或B中有一个空，另一个剩下的序列直接复制到C尾部。
C: 6 100 202 301
“先享受后付出代价” -- 分割比较容易，归并比较复杂
（4）快速排序
特点： a. 时间复杂度最好为O(n)，最坏为O(n^2) ，平均为O(nlog(n))
b.空间复杂度为O(log(n))
c.不稳定的排序方法
相对于归并排序，快速排序是一种“先付出代价后享受”的排序方法 -- 分割比较难，排序比较容易
传统快速排序（杠杆点选取左边的第一个数）示例：
初始序列：{ 49 38 65 97 76 13 27 }
第一次排序：
{ 27 38 65 97 76 13 49 }
{ 27 38 49 97 76 13 65 }
{ 27 38 13 97 76 49 65 }
{ 27 38 13 49 76 97 65 }
第二次排序：
{ 27 38 13 49 76 97 65 }
{ 13 38 27 49 65 97 76 }
{ 13 27 38 49 65 76 97 }
排序完毕！
（5）参考资料
a. 《算法之道》——邹恒明