目录：

快速排序例题

OOOO参考文献排序规则

快速排序例题

1、② 在最坏情况下，待排序的序列为正序或逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它是一颗斜树。此时需要执行n-1次递归调用，且第i次划分需要经过n-i次关键字的比较才能找到第i个记录，也就是枢纽的位置，因此比较次数为

2、通常，快速排序被认为是在所有同数量级O(nlogn) 的排序方法中，其平均性能是最好的。但是，若待排记录的初始状态为按关键字有序或基本有序时，快速排序将蜕化为冒泡排序，其时间复杂度为O(n2)。

3、为避免出现这种情况，需在进行一次划分之前，进行“预处理”，即：先对R(s),key，R(t).key和R[└(s+t)/2┘].key，进行相互比较，取关键字为“三者之中”的记录为枢纽记录。

4、快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递归调用层数与上述二叉树的深度一致。因而，存储开销在理想情况下为O(log2n)，即树的高度，其空间复杂度也就为O(logn)；在最坏情况下，需要进行n-1次递归调用，即二叉树是一个单链，为O(n)；平均情况，空间复杂度也为O(logn)。

OOOO参考文献排序规则

1、排序算法是数据结构这门课程核心内容之一。它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛应用于信息学、系统工程等各种领域。学习排序算法是为了将实际问题中涉及的对象在计算机中进行处理。本OOOO对直接插入排序、直接选择排序、起泡排序快速排序关键字：；泡排序；；快速排序；排序是计算机科学中最重要的研究问题之一, 它在计算机图形、计算机辅助设计、机器人、模式识别及统计学等领域具有广泛的应用。由于它固有的理论上的重要性,2000年它被列