|
快速排序执行过程 快速排序执行的全过程可用递归树来描述 分析 ()递归执行的路线如图中带箭头的包络线所示 () 递归树上每一结点左旁方括号表示当前待排序的区间结点内的关键字是划分的基准关键字 注意 叶结点对应的子区间只有一个关键字无须划分故叶结点内没有基准关键字 () 划分后得到的左右两个子区间分别标在该结点的左右两个孩子结点的左边方括号内 【例】根结点左旁方括号[ ]表示初始待排序的关键字根内的表示所选的划分基准记录的关 键字划分结果是[][ _]其左右子区间分别标在根结点的两个孩子的左边 () 每个分支结点右旁圆括号中的内容表示对该结点左旁区间的排序过程结束之后返回的结果它是其左右孩子对应的区间排 序完成之后将左右孩子对应的排序结果分别放在该分支结点的关键字前后所得到的关键字序列 【例】分支结点的左右孩子对应的区间排序后的结果分别是(_)和()将它们分别放在的前后即得( )这是对结点左旁区间[ ]排序的结果 () 算法的执行顺序是递归树中的箭头顺序实际上当把划分操作视为访问结点的操作时快速排序的执行过程相当于是先序 遍历其递归树 注意 任何递归算法均可用递归树来描述其执行过程 快速排序各次划分后的状态变化 [ ] //初始关键字 [ ] [ ] //第次划分完成之后对应递归树第层 [ ] [ ] [ ] [ ] //对上一层各无序区划分完成后对应递归树第层 [ ] //对上一层各无序区划分完成后对应递归树第层 //最后的排序结果 |
