jchap009-电商2013.ppt

3．理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。 4. 了解外部排序的基本过程及其时间分析。 * 每次插入开始的时候 j=0指向标头, k = SL[0].next 即指向第一个元素 在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端点。那么能否用队列来代替这个栈? 为什么? 【解答】 可以用队列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分为两个子区间，然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时，保存另一个子区间的上界和下界，待该区间处理完成后再从栈中取出另一子区间的边界，对其进行处理。这个功能利用队列也可以实现，只不过是处理子区间的顺序有所变动而已。 * “三者之中”:即取三个值中的中间值 设待排序文件有n ( n0 )个记录，试编写算法，不经全部排序，将第j (0j≤n)个元素放在适当位置（即在排序后它应在的位置）。 　　　【分析】 将该记录作枢轴，进行一趟快速排序，则可将该记录放在其排序后应在的位置上。 　　　【算法】 　　　　PROC quickpass(VAR r:listtype;j:integer); ｛本算法将第j个记录快速放到它排序后的位置上｝ IF j1 THEN r[j] ←→ r[1]; i:=1; k:=n; rp:=r[i]; x:=r[1].key; WHILE ik DO [ WHILE (ik) AND (r[k].key≥x) DO k:=k-1; IF ik THEN [ r[i]:=r[k];i:=i+1 ]; WHILE (ik) AND (r[i].key≤x) DO i:=i+1; IF ik THEN [ r[k]:=r[i];k:=k-1] ] r[i]:=rp; ENDP;{quickpass} * for ( i=H.length/2; i0; --i ) //因为若将待排序序列看成一个完全二叉树，则最后一个非终端结点是n/2向下取整。 因为n=n0+n1+n2 n0=n2+1 n=n1+n0+n0-1 2n0=n-n1+1 n0=(n-n1+1)/2 非叶子结点数为n-n0=(n+n1-1)/2 对于完全二叉树 n1=0或者n1=1 * “1. 对深度为 k 的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)； ” 因为每一层只比较两次 例如： p→369→367→167→239→237→138→230→139 进行第一次分配 进行第一次收集 f[0] e[0] f[7] e[7] f[8] e[8] f[9] r[9] p→230 →230← →367 ← →167 →237 →367→167→237 →138 →368→239→139 →369 ←e →239 →139 →138← 进行第二次分配 p→230→237→138→239→139 p→230→367→167→237→138→368→239→139 f[3] r[3] f[6] r[6] →230 ← →237 →138 →239 →139 →367 ← →167 →368 →367→167→368 进行第二次收集 进行第三次收集之后便得到记录的有序序列 f[1] r[1] p→230→237→138→239→139→367→167→368 进行第三次分配 f[2]