数据结构考研分类复习真题 第十章 排序[55]

数据结构考研分类复习真题 第十章 排序[55]  

　　 ．图

　　注 a是整数数组 存放要排序的数组集合 n是a的长度 p i j k m t是临时变量 p为整型数组 i j k m t为整型变量 本题给出的是将数组a的元素a a … an从大到小排序的子程序的框图 如上图 填空完善此算法框图 该子程序采用改进的选择排序方法 该方法基于以下思想 在选择第一大元过程中 a 与aj (j=n n … )逐个比较 若发现aj >a 则aj 与a 交换 交换后新的aj 有性质aj >= at( j <t<n ) 若再有aj >ai(j <j ) aj 与a 交换 则交换后的aj 也有性质aj >=at(j <t<=n ) 如在挑选第一大元过程中 与a 交换的元素有k(k>= )个 依次为aj aj … ajk 则它们都满足这一性质 它们的下标满足n>=j >j >…>jk> 有了这些下标 在确定第二大元时 可只考虑a 与aj(j=jk jk … )逐一比较 倘若jk= 则可不经比较就知道a 就是第二大元 在选择第二大元的过程中 将与a 交换过的元素下标也记录下来 可供选择其他大元使用 但在选择第二大元时 应保证与a 交换的那些位置上的新值也都满足上述性质 依次类推 顺序选择第一 第二 … 第n 大元 实现对a的排序 【哈尔滨工业大学   六 ( 分)】