1.直接选择排序 4)算法分析 ˉ算法由两层循环构成,外层循环表示共需进行n-1趟排序,内层循环 需进行n-I次比较,也许会做一次交换,即记录移动次数最多为3。 总的时间性能为 ①比较次数:n(n-1)/2 ②移动次数:最坏情况下为3(n-1) 所以总的时间复杂度为:0(n2) 空间复杂度为:0(1)交换记录时用 直接选择排序是一种不稳定的排序算法 计算机软件技术基础 查找与排序
1. 直接选择排序 4）算法分析 ▪ 算法由两层循环构成，外层循环表示共需进行n-1趟排序，内层循环 需进行n-I次比较，也许会做一次交换，即记录移动次数最多为3。 ▪ 总的时间性能为 ① 比较次数：n(n-1)/2 ② 移动次数：最坏情况下为3(n-1) ▪ 所以总的时间复杂度为：O(n2) ▪ 空间复杂度为：O(1) 交换记录时用 ▪ 直接选择排序是一种不稳定的排序算法 计算机软件技术基础 查找与排序
96 选择排序 83 27 2.堆排序 1)堆 38 设有序列{k1,k2,…,kn},若满足: k≤k2 k.≥k 或 (i=1,2,…, < 2i+1 2i+1 则称该序列构成的完全二叉树是一个堆。 例如,有序列:{96,83,27,38,11,9 构成的完全二叉树如上图所示,它是一个堆 易知堆顶元素为所有元素中的最小值或最大值 计算机软件技术基础 查找与排序
二、选择排序 2. 堆排序 1) 堆 设有序列{ k1,k2,…,kn }，若满足： 或 （ｉ ，， ， ） = + + 2 2 1 2 2 1 2 1 2 n i i i i i i i i k k k k k k k k 则称该序列构成的完全二叉树是一个堆。 ▪ 例如，有序列：{ 96，83，27，38，11，9 } ▪ 构成的完全二叉树如上图所示,它是一个堆。 ▪ 易知堆顶元素为所有元素中的最小值或最大值 96 83 38 11 9 27 计算机软件技术基础 查找与排序
2.堆排序 2)堆排序的过程由两部分组成: ①将现有的序列构成一个堆 ②输出堆顶元素,重新调整元素,构成新的堆,直到堆空为止 3)堆的构造: ①由所给序列生成对应的完全二叉树 ②设完全二叉树a[1.n中结点a[k]的左右子树均为堆,为构成以 a[k]为根结点的堆,需进行调整。方法是将a[k]的值与其左右子树 的根结点进行比较,若不满足堆的条件,则将a[k]与其左右子树中 根结点大的交换,继续进行比较,直到所有子树均满足堆的定义为 止 计算机软件技术基础 查找与排序
2. 堆排序 2）堆排序的过程由两部分组成： ① 将现有的序列构成一个堆 ② 输出堆顶元素，重新调整元素，构成新的堆，直到堆空为止。 3）堆的构造： ① 由所给序列生成对应的完全二叉树； ② 设完全二叉树a[1..n]中结点a[k]的左右子树均为堆，为构成以 a[k]为根结点的堆，需进行调整。方法是将a[k]的值与其左右子树 的根结点进行比较，若不满足堆的条件，则将a[k]与其左右子树中 根结点大的交换，继续进行比较，直到所有子树均满足堆的定义为 止。 计算机软件技术基础 查找与排序
建立初始的最大维 2 2 3 56 56 2125492541608 2125492541608 初始排序码集合 i=2时的局部调整 计算机软件技术基础 查找与排序
建立初始的最大堆 21 25 25* 49 16 08 1 2 3 4 5 6 i 21 25 49 25* 16 08 初始排序码集合 21 25 49 25* 16 08 4 21 25 25* 16 49 08 1 3 5 6 2 i i = 2 时的局部调整 计算机软件技术基础 查找与排序
3 3 4 56 56 212549251608 A4925|2125+1608 i=1时的局部调整 i=0时的局部调整 形成最大堆 计算机软件技术基础 查找与排序
4 21 25 25* 49 16 08 1 2 3 5 6 i 21 25 49 25* 16 08 i = 1 时的局部调整 4 49 25 25* 16 21 08 1 3 5 6 2 49 25 21 25* 16 08 i = 0 时的局部调整 形成最大堆 计算机软件技术基础 查找与排序