简单选择排序与堆排序.ppt

《简单选择排序与堆排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、3.3.3简单选择排序与堆排序1.简单选择排序1第3章查找与排序技术输入：无序序列P(1：n)。输出：有序序列P(1：n)。PROCEDUDESELESORT(P，n)FORi＝0TOn－2DO{k＝iFORj＝i＋1TOn－1DOIFP(j)＜P(k)THENk＝jIF(k≠i)THEN{d＝P(i)；P(i)＝P(k)；P(k)＝d}}RETURN2第3章查找与排序技术selesort(p，n)intn；ETp[]；{inti，j，k；ETd；for(i＝0；i＜＝n－2；i＝i＋1){k＝i；for(j＝i＋1；j＜＝n－1；j＝j＋1)if(p[j]＜p[

2、k])k＝j；if(k!＝i){d＝p[i]；p[i]＝p[k]；[k]＝d；}}return；}3第3章查找与排序技术2.堆排序堆的定义：具有n个元素的序列(h1，h2，…，hn)，当且仅当满足(i＝1，2，…，n/2)时称之为堆。由堆的定义可以看出，堆顶元素(即第一个元素)必为最大项。4第3章查找与排序技术或具有n个元素的序列(h1，h2，…，hn)，当且仅当满足(i＝1，2，…，n/2)时称之为堆。5第3章查找与排序技术序列(91，85，53，36，47，30，24，12)是一个堆6第3章查找与排序技术调整建堆在一棵具有n个结点的完全二叉树（用一维数组H(1：n)

3、表示）中，假设结点H(m)的左右子树均为堆，现要将以H(m)为根结点的子树也调整为堆。7第3章查找与排序技术8第3章查找与排序技术9第3章查找与排序技术10第3章查找与排序技术堆排序(1)首先将一个无序序列建成堆。(2)然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n－1个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。反复做第(2)步，直到剩下的子序列为空为止。11第3章查找与排序技术调整建堆输入：完全二叉树数组H(1：n)。其中结点H(m)的左右子树均为堆。输出：

4、以H(m)为根结点的子树为堆。PROCEDURESIFT(H，n，m)t＝H(m)；j＝2mWHILE(j≤n)DO{IF(j＜n)and(H(j)＜H(j＋1))THENj＝j＋1IF(t＜H(j))THEN{H(m)＝H(j)；m＝j；j＝2m}elsej＝n＋1}H(m)＝tRETURN12第3章查找与排序技术堆排序输入：无序序列H(1：n)。输出：无序序列H(1：n)。PROCEDUREHEAPSORT(H，n)k＝n/2FORi＝kTO1BY－1DOSIFT(H，n，i)[无序序列建堆]FORi＝nTO2BY－1DO{t＝H(1)；H(1)＝H

5、(i)；H(i)＝t[堆顶元素换到最后]SIFT(H，i－1，1)[调整建堆]}RETURN13第3章查找与排序技术heapsort(p，n)intn；ETp[]；{inti，k；ETt；k＝n/2；for(i＝k－1；i＞＝0；i－－)sift(p，n－1，i)；/*无序序列建堆*/for(i＝n－1；i＞＝1；i－－){t＝p[0]；p[0]＝p[i]；p[i]＝t；/*堆顶元素换到最后*/sift(p，i－1，0)；/*调整建堆*/}return；}14第3章查找与排序技术staticsift(h，n，m)intn，m；ETh[]；{intj；ETt；t＝h

6、[m]；j＝2*(m＋1)－1；while(j＜＝n){if((j＜n)&&(h[j]＜h[j＋1]))j＝j＋1；if(t＜h[j]){h[m]＝h[j]；m＝j；j＝2*(m＋1)－1；}elsej＝n＋1；}h[m]＝t；return；}15第3章查找与排序技术