填空题
公共基础知识
题号 #603860
请写出用希尔排序法对序列(5,1,7,3,1,6,9,3,2,7,6)进行第一遍扫描后的中间结果是( )。
参考答案
暂无
答案解析
(5,l,3,2,1,6,9,7,3,7,6)
【分析】希尔排序法的基本思想:将整个无序序列分割成若干小的子序列分别进行插入排序(插入排序:开始线性表中只有第l个元素,然后从线性表的第2个元素开始直到最后一个元素,逐次将其中的每一个元素插入到前面已经有序的子表中)。
子序列的分割方法:将相隔某个增量h(ht=n/2k(k=1,2,3,…,[10g2n]n为待排序的线性表的长度))的元素构成一个子序列。在排序过程中,逐次减小这个增量,最后当h减到l时进行一次插入排序,排序完成。
按以上分析,第1次分割子序列h=n/2=11/2=5,构成的子序列有:5—6、1—9、7—3、3—2、l一7、6(最后一个元素6成单),每一个序列进行插入排序,结果为:5—6、l一9、3—7、2—3、l一7、6(最后一个元素6成单),所以第一遍扫描后的中间结果是(5,l,3,2,1,6,9,7,3,7,6)。
【分析】希尔排序法的基本思想:将整个无序序列分割成若干小的子序列分别进行插入排序(插入排序:开始线性表中只有第l个元素,然后从线性表的第2个元素开始直到最后一个元素,逐次将其中的每一个元素插入到前面已经有序的子表中)。
子序列的分割方法:将相隔某个增量h(ht=n/2k(k=1,2,3,…,[10g2n]n为待排序的线性表的长度))的元素构成一个子序列。在排序过程中,逐次减小这个增量,最后当h减到l时进行一次插入排序,排序完成。
按以上分析,第1次分割子序列h=n/2=11/2=5,构成的子序列有:5—6、1—9、7—3、3—2、l一7、6(最后一个元素6成单),每一个序列进行插入排序,结果为:5—6、l一9、3—7、2—3、l一7、6(最后一个元素6成单),所以第一遍扫描后的中间结果是(5,l,3,2,1,6,9,7,3,7,6)。