快速排序学习总结
昨天花了一天的时间学习总结冒泡排序，今天下决心把数据结构的相关内容，各种排序，树，
查找算法等都大概学习了一遍，把时间复杂度和空间复杂度等概念理清了，终于有了一点点
的踏实感，因为自己没考研，本科基础也没打牢，总感觉自己跟任何一个人都有一大段的差距，
连写程序和找实习工作都觉得自己很没信心，缺少底气，因为一些研究生里面大家都会的基础
知识我丝毫不懂，真是太打击自己了！！
自己的近期安排：
今天总结了快速排序，hash函数等知识之后，明天开始就要踏踏实实的看软件测试的论文了！！
在看论文的同时，如果想练练手，最好坚持把上学期的“决策树”的作业实现了，这样自己
就有信心面对一切了！！
另外，好好上李老师数据挖掘的课！千万不要迟到，最好6点10分就要去到新信息楼！好好学习，
去图书馆借几本好书，提前学习和准备！
还有，明天别忘了问问解婷婷和杨惠她们的英文论文都是从哪下的？怎么搜索，比如，Proges的使用？
怎么知道哪些英文论文比较好？
好了，现在言规正传，学习快速排序：
快速排序和冒泡排序都是交换排序类型，快排的算法思想是：
每次选一个基准值（比如第一个数），让小于这个基准值的数向左移，大于这个基准值的数向右移，
一趟移动之后，这个基准值就定位到合适的位置了，它的左边的数比它小，右边的数比它大；一趟可以
定位一个数，左边和右边分别递归，n-1趟后所有数就都定位到合适位置了！
算法分析
快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。
（1）最坏时间复杂度
最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。
因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：
Cmax = n(n-1)/2=O(n2)
如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增序(或递减序)排列时，每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录，则快速排序所需的比较次数反而最多。
（2） 最好时间复杂度
在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：
0(nlgn)
注意：
用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右子区间长度大致相等，故递归树的高度为O(lgn)，而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n，故整个排序过程所需要的关键字比较总次数C(n)=O(nlgn)。
因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为0(n2)，最好时间复杂度为O(nlgn)。
具体的算法描述、代码实现、算法分析和动画演示参见：
数据结构自考网
http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.2.4.htm
附排序的面试题：
来自：http://www.javaref.cn/topics/Question/10566.html
问题：
a)冒泡 (bubble sort) 和快速排序 (quick sort) 的区别？它们的时间复杂度？
冒泡：每趟排序将最大值安置到最后一个位置上，时间复杂度为 O(n 平方 ).
快速排序法是对起泡排序法的一种改进，
基本思想是通过一趟排序将待排序纪录分割成独立的两部分，其中一部分纪录的关键字
均比另一部分纪录的关键字小，则可以分别对这两部分纪录继续进行排序，以达到整个序列有序。
时间复杂度为 O(NlogN).
疑问：快排的最坏时间复杂度是O(n 平方 )，最好时间复杂度到底是 O(Nlog2N)，还是 O(NlgN)？？
按照“数据结构自考网”的分析应该是O(Nlog2N)，但是《数据结构》书上277上的分析，似乎O(Nlog2N)
和O(NlgN)都是合理的，到底是什么呢？明天问问解婷婷吧。
b)在什么情况下快速排序的效果最差？ 答案：输入数据逆序排列时效果最差，蜕化成冒泡