|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 >
|
被考次数：1次
被考频率：低频率
总体答错率：46%
知识难度系数： 
|
由 软考在线 用户真实做题大数据统计生成
|
|
考试要求：掌握
相关知识点：11个
|
|
|
|
|
快速排序的基本思想是：通过一趟排序将待排的记录划分为独立的两部分，称为前半区和后半区，其中，前半区中记录的关键字均不大于后半区记录的关键字，然后再分别对这两部分记录继续进行快速排序，从而使整个序列有序。
|
|
|
|
一趟快速排序的过程称为一次划分，具体做法是：附设两个位置指示变量i和j，它们的初值分别指向序列的第一个记录和最后一个记录。设枢轴记录（通常是第一个记录）的关键字为pivot，则首先从j所指位置起向前搜索，找到第一个关键字小于pivot的记录时将该记录向前移到i指示的位置，然后从i所指位置起向后搜索，找到第一个关键字大于pivot的记录时将该记录向后移到j所指位置，重复该过程直至i与j相等为止。
|
|
|
|
|
|
|
|
|
|
|
|
快速排序算法的时间复杂度为O（nlog2n），在所有算法复杂度为此数量级的排序方法中，快速排序被认为是平均性能最好的一种。但是，若初始记录序列按关键字有序或基本有序时，即每次划分都是将序列划分为某一半序列的长度为0的情况，此时快速排序的性能退化为时间复杂度是O（n2）。快速排序是不稳定的排序方法。
|
|
|
