“快速排序”(Quick Sort )和气泡排序都是交换类排序。 快速排序是对鼓泡排序的改进。 快速排序是不稳定的排序方法，因为关键字的比较和交换是通过跳转完成的。
0 .序
1 .通过鼓泡排序
2 .快速排序
2.1基本思想
2.2一次快速排序(一次分隔) ) )。
2.3流程
2.4实现
2.5复杂度分析
2.5.1小时的复杂性(包括证明)。
2.5.2空间复杂性
0 .序
快速排序算法最初由图灵奖获得者美丽的大船Hoare设计。 他对形式化的方法论和ALGOL60编程语言的发明做出了卓越的贡献，是上个世纪最伟大的计算机科学家之一。
快速排序被列为20世纪十大算法之一。
1 .通过鼓泡排序
在排序过程中，假设记录序列R[1.n]的状态如下：
2 .快速排序
快速排序也通过反复比较和移动的交换来实现排序。 但是，这种实现增加了记录比较和移动的距离，直接将关键字大的记录从前向后移动，将关键字小的记录从后向前移动，从而减少了总比较次数和移动交换次数。
2.1基本思想
要排序的记录在一次排序中分为两个独立的部分，一个记录的关键字小于另一个记录的关键字，每个部分继续排序，直到顺序完全对齐。
2.2一次快速排序(一次分隔)
目标：查找关键字为“集线器”的记录，关键字小于集线器的记录移动到该记录之前，相反关键字大于集线器的记录移动到该记录之后。
以R[s]=52为集线器
将R[high].key与集线器关键字进行比较，要求r [ high ].key集线器关键字
对比R[low].key和集线器的关键字，要求r [ low ].key集线器的关键字
这样，经过“一次划分”，将关键字的排列
52、49、80、36、14、58、61、97、23、75
调整为23、49、14、36、(52 )、58、61、97、80、75
在调整过程中，设置了low和high两个指针，它们的初始值分别为s和t
然后逐渐减小high，增加low，保证R[high].key52和R[low].key52，否则进行记录的“交换”。
2.3流程
首先对无序记录序列进行“一次划分”，然后对分割得到的两个子序列分别进行“递归”快速排序。
2.4实现
//快速排序O(nlogn )---逆序o ) n^2)//调用QSort(1) 1，n )保留记录index=1 . n
公共int [ ] qsort (intlow，inthigh ) ) if ) low
qsort(low，p-1 )；
qort(p1，high )；
}returnneedSort；
}私有内分区(intlow，inthigh ) )。
needSort[0]=needSort[low]； wile(low=needsort[0] ) high--；
needSort[low]=needSort[high]； 低速(lowhighneedsort [ low ]=need sort [0] ) low；
needSort[high]=needSort[low]；
}
needSort[low]=needSort[0]； 返回低；
}
2.5复杂度分析
2.5.1小时的复杂性
最佳情况下，Partition每次均分，对n个关键字进行排序，递归树(见2.5.2 )的深度为
也就是说，如果只递归2n次log，而所需时间为t(n )，则第一个分区应该扫描整个数组并进行n次比较。 然后，注意到如果获得的集线器将数组分为两部分，则分别需要t(n/2 )的时间)是最好的情况，进行2等分。 于是，我们不断地划分，得出了以下不等式的估计。
t(n )2t ) n/2 ) n，t )1)=0
t(n )2 ) 2t ) n/4 ) n/2 ) n=4t ) n/4 ) 2n
t(n )4 ) 2t ) n/8 ) n/4 ) 2n=8t ) n/8 ) 3n
.
t(n )nt(1) ) log2n (n=o ) log2n ) )。
我不知道为什么“”
不是“＝”？ 待补充也就是说，在最优的情况下，快速排序算法的时间复杂度为O(nlogn)。
② 在最坏情况下，待排序的序列为正序或逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它是一颗斜树。此时需要执行n-1次递归调用，且第i次划分需要经过n-i次关键字的比较才能找到第i个记录，也就是枢纽的位置，因此比较次数为
，最终其时间复杂度为O(n2)。
③ 平均的情况，设枢纽的关键字应该在第k的位置(1≤k≤n)，每个位置的概率相同，均为1/n，那么：
数学归纳法可证明，其数量级为O(nlogn)。 待补充
通常，快速排序被认为是在所有同数量级O(nlogn) 的排序方法中，其平均性能是最好的。但是，若待排记录的初始状态为按关键字有序或基本有序时，快速排序将蜕化为冒泡排序，其时间复杂度为O(n2)。
为避免出现这种情况，需在进行一次划分之前，进行“预处理”，即：先对R(s),key，R(t).key和R[└(s+t)/2┘].key，进行相互比较，然后取关键字为“三者之中”的记录为枢纽记录。
2.5.2 空间效率
举例：
快速排序的递归过程可用生成一颗二叉树形象地给出，下图对应上面例子递归调用过程的二叉树。
快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递归调用层数与上述二叉树的深度一致。因而，存储开销在理想情况下为O(log2n)，即树的高度，其空间复杂度也就为O(logn)；在最坏情况下，需要进行n-1次递归调用，即二叉树是一个单链，为O(n)；平均情况，空间复杂度也为O(logn)。
注意，由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。
参考：
上课ppt
《大话数据结构》jadhb著 清华大学出版社，2011.6(2017.6 重印)