每一趟一个“最轻〞的气泡冒到顶部-上升法。 也可从上向下扫描,这时每一趟是一个“最重〞的气泡沉到底部 -下沉法。 每次交换时,其中一个总沿着最终方向,另一个那么未必(取决于 上升法还是下降法)。
例:对(49, 38, 65, 97, 76, 13, 27, 49)冒泡排序。
趟次 0(初始) ┌┐ 49
➢稳定:相邻元素比较和移动
➢可用于链表
➢适用于根本(正向)有序或n较少的情况
7.2.2 希尔排序
一、根本思想
排序表分成假设干组,相隔为某个“增量〞的记录为一组,各组 内直接插入排序;初始增量d1较大,分组较多(每组的记录数少), 以后增量逐渐减少,分组减少(每组的记录数增多),直到最后增 量为1(d1>d2>…>dt=1),所有记录放为同一组,再整体进展 一次直接插入排序。
《数据库结构》PPT课件
本课件PPT仅供大家学习使用 学习完请自行删除,谢谢! 本课件PPT仅供大家学习使用 学习完请自行删除,谢谢! 本课件PPT仅供大家学习使用 学习完请自行删除,谢谢! 本课件PPT仅供大家学习使用 学习完请自行删除,谢谢!
7.1 根本概念
一、概念 关键字(key):记录中可用来标识一个记录的数据项或其组合。关 键字也简称键,它的值称为键值。 ➢主关键字(Primary Key):可唯一标识记录的关键字,即不同记录该 关键字的值不同。 ➢次关键字(Secondary Key):不能唯一标识记录的关键字。 排序(Sorting):简单地说,就是将一组记录按关键字域递增(由小到 大)或递减(由大到小)的次序重新排列。 排序码(Sort Key):作为排序依据的关键字。 ➢有序表: ➢无序表:
两种根本操作: 1〕比较:比较关键字的大小 2〕移动:将记录从一个位置移动到另一个位置。 时间开销主要指关键字的比较次数和记录的移动次数。 当键值是字串时,比较要占用较多的时间; 当记录很大时,交换记录时移动要占较多时间。 比较一般都需要,但移动可改变存储方式来防止。