数据结构语言描述.ppt

**********************************************************************************************************************************************************************************************************10.4选择排序简单选择排序算法思想:简单选择排序(SimpleSelectionSort)的基本操作是通过n-i次关键字的比较，从n-i+1个元素中选出关键字最小的元素，并和第i(1=i=n)个元素交换之。整个排序过程共进行n-1趟(i从1变化至n-1)选择。VoidSelectSort(SqListL){ //完成一次完整的简单选择排序for(i=1;iL.length;++i){ //选择第i小的元素，并交换到位j=SelectMinKey(L,i); //在L.r[i..L.length]中选择key最小的元素if(i!=j)L.r[i]与L.r[j]交换； //与第i个元素交换}}//SelectSort第165页,共175页，星期六，2024年，5月1338659776492749*i＝10491234567838659776132749*初始关键字简单选择排序i＝21327659776493849*i＝31327389776496549*i＝41327384976976549*i＝51327384949*976576i＝61327384949*659776i＝71327384949*657697第166页,共175页，星期六，2024年，5月稳定性：简单选择排序方法是不稳定的排序方法适用情况：*元素个数较少10.4选择排序（续）性能分析:时间复杂度T(n)=O(n2)空间复杂度S(n)=O(1)正序： 比较次数:n(n-1)/2; 元素不移动逆序： 比较次数:n(n-1)/2; 移动次数:3(n-1)第167页,共175页，星期六，2024年，5月10.4选择排序（续）堆排序堆(Heap)：n个元素的序列{k1,k2,…,kn},当且仅当满足以下关系时，称之为堆。 ki=k2i且ki=k2i+1或ki=k2i且ki=k2i+1.满足前一约束的堆称之为小顶堆，满足后一约束的堆称之为大顶堆。小顶堆的第一个元素为序列中最小者；大顶堆的第一个元素为序列中最大者。堆可以用完全二叉树来描述(堆的本质仍然是一个序列)。第168页,共175页，星期六，2024年，5月97133849*76276549小顶堆：{13,38,27,49*,76,65,49,97}顺序存储的堆01234567813382749*7665499710.4选择排序（续）第169页,共175页，星期六，2024年，5月10.4选择排序（续）堆排序算法思想:堆排序(HeapSort)的思路是：下一趟选择排序时尽可能利用上一趟排序过程中已有的比较结果信息，从而提高排序效率。堆排序完整过程：首先对初始序列建堆；然后，在输出堆顶的最小值之后，使得剩余n-1个元素的序列重新又建成一个堆，则得到n个元素中的次小值。如此反复进行，通过n-1趟，便能得到一个有序序列。堆排序实现的两个问题： *如何由初始序列建成一个堆； *如何在输出堆顶元素之后，调整剩余元素成为一个新的堆这两个问题的解决都归结到一个实现：筛选(自堆顶至叶子的调整过程)第170页,共175页，星期六，2024年，5月筛选(自堆