PPT《东南大学计算机学院 方效林》

16 35

08 左端点 右端点 中点 取21,25*,08三个元素中的21为基准 选择排序 直接选择排序在待排序序列中选择最小的元素xx与第一个元素对换剔除x,对剩下元素执行以上步骤 *

21 25

49 25*

16 08 初始

08 25

49 25*

16 21 第1步08

16 49 25*

25 21 第2步08

16 21 25*

25 49 第3步08

16 21 25*

25 49 第4步08

16 21 25*

25 49 第5步 选择排序 直接选择排序算法分析设有n个元素,第i趟比较次数为n-i-1次总比较次数为移动次数最好情况为0最坏情况为3(n-1)直接选择排序是不稳定算法 * 堆排序 算法思想建立最大堆循环执行以下步骤,直至所有元素出堆每次堆顶元素(即最大元素)与堆中最后一个元素交换剔除最大元素后调整为最大堆

49 08

25 25*

16 21 i=2

21 25

49 25*

16 08 最后一元素的父节点i=2开始调整 i=1

21 25

49 25*

16 08 调整i=1 i=0 调整i=0

21 25

49 25*

16 08

49 08

25 25*

16 21

49 08

25 25*

16 21 形成最大堆

49 25

21 25*

16 08

21 08

25 25*

16 49 堆排序 算法思想建立最大堆循环执行以下步骤,直至所有元素出堆每次堆顶元素(即最大元素)与堆中最后一个元素交换剔除最大元素后调整为最大堆 堆顶49与堆尾08交换

49 25

21 25*

16 08

21 25 25*

16 49

08 21

49 25*

08 16

25 25 25*

21 08

16 49 虚线内调整为最大堆 堆顶25与堆尾16交换 虚线内调整为最大堆

21 49

16 08

25 25* 25*

16 21

08 25

49 堆顶25*与堆尾08交换 虚线内调整为最大堆 堆排序 算法思想建立最大堆循环执行以下步骤,直至所有元素出堆每次堆顶元素(即最大元素)与堆中最后一个元素交换剔除最大元素后调整为最大堆

49 16 25*

25 21

21 16

08 25*

25 49 堆顶21与堆尾08交换 虚线内调整为最大堆

08 49 25*

25 16

08 21 25*

25 49 堆顶16与堆尾08交换 虚线内调整为最大堆

21 08

16 49 25*

25 08

16 21 25*

25 49 虚线内调整为最大堆

21 16

08 堆排序 堆排序算法分析建立最大堆设堆中有n个元素, 对应完全二叉树有k层(2k-1≤n........