《第二章数据结构与算法》由会员分享，可在线阅读，更多相关《第二章数据结构与算法（13页珍藏版）》请在金锄头文库上搜索。
1、第二章数据结构与算法 2 8排序技术1 交换类排序所谓交换排序是指借助数据元素之间的相互交换进行排序的一种方法 冒泡排序与快速排序属于交换类的排序方法 1 冒泡排序冒泡排序是一种最简单的交换排序方法 它是通过相邻数据元素的交换逐步将线性表变成有序 第二章数据结构与算法 基本过程如下 首先 从表头开始往后扫描线性表 在扫描过程中逐次比较相邻两个元素的大小 若相邻两个元素中 前面的元素大于后面的 则将它们互换 显然 在扫描过程中 不断的将相邻的元素中的大者往后移动 最后就将线性表中的最大者换到了表的后面 这也是线性表中最大元素应有的位置 第二章数据结构与算法 然后 从后到前扫描剩下的线性表 同样
2、在扫描过程中逐次比较相邻两个元素的大小 若相邻两个元素中 后面的元素小于前面的元素 则将它们互换 在剩下的线性表中重复上述过程 直到剩下的线性表变为空为止 第二章数据结构与算法 2 快速排序快速排序的基本思想如下 从线性表中选取一个元素 设为T 然后将线性表后面小于T的元素移动到前面 而前面大于T的元素移动到后面 结果就将线性表分成了两部分 T插入到其分界线的位置处 这个过程称为线性表的分割 通过对线性表的一次分割 就以T为分界线 将线性表分成了前后两个子表 且前面子表中的所有元素均不大于T 而后面的都不小于T 第二章数据结构与算法 如果对分割后的各子表在按上述的原则进行分割 并且 这种分割过
3、程可以一直作下去 直到所有子表为空为止 则此时的线性表变成了有序表 由此可知 快速排序的关键是对线性表的分割 以及对各分割过程可以一直做下去 直到所有子表为空 则此时的线性表就变成了有序表 在一般情况下 快速排序的速度要比冒泡排序卡 但在最坏情况下 快速排序要的比较的次数与冒泡排序一样 都是n n 1 2 第二章数据结构与算法 2 插入排序 1 简单插入排序所谓插入排序 是指将无序序列中的各元素依次插入到已经有序的线性表中 在线性表中 只包含第一个元素的子表显然可以看成是有序表 接下来的问题是 从线性表的第二个元素到最后一个元素 依次将其中的每个元素插入到前面已经有序的子表中 一般来说 假设线
4、性表中前j 1个元素已经有序 现在将线性表中第j个元素插入到前面的有序子表中 插入过程如下 第二章数据结构与算法 首先 将第j个元素放到一个变量T中 然后从有序子表的最后一个元素开始 往前逐个与T比较 将大于T的元素依次向后移一个位置 直到发现一个元素不大于T为止 此时就将T插入到刚移出的空位置张 有序子表的长度就变为j了 再简单插入排序中 每一次比较后最多移掉一个逆序 因此 这种排序方法的效率与冒泡排序法相同 在最坏情况下 简单插入排序需要n n 1 2次比较 第二章数据结构与算法 2 希尔排序希尔排序的基本思想如下 将整个无序序列分割成若干个下的子序列分别进行插入排序 子序列的分割方法如下
5、 第二章数据结构与算法 将相隔某个增量h的元素构成一个子序列 在排序过程中 逐次减小这个增量 最后当h减到1时 进行一次插入排序 排序就完成 增量序列一般取ht n 2k k 1 2 log2n 其中n为待排序序列的长度 在希尔排序过程中 虽然对于每一个子表采用的仍然四插入排序 但是 在子表中每进行依次比较就有可能移去整个线性表的多个逆序 从而改善了整个排序过程的性能 第二章数据结构与算法 3 选择类排序 1 简单选择排序选择排序的基本思想如下 扫描整个线性表 从中选出最小的元素 将它交换到表的最前面 然后对剩下的子表采用同样的方法 直到子表空为止 对于长度为n的序列 选择排序需要扫描 n 1
6、 遍 每一遍扫描均从剩下的子表中选出最小的元素 然后将该最小的元素与子表中的每一个元素进行比较 第二章数据结构与算法 2 堆排序堆的定义如下 具有n个元素的序列 h1 h2 hn 当且仅当满足h h2jhi h2jh h2i 1hi h2i 1 i 1 2 n 2 时称为堆 由堆的定义可以看出 堆顶的元素必须为最大 在实际处理中 可以用一维数组H 1 n 来存储堆序列中的元素 也可以用完全二叉树来直观地表示堆的结构 第二章数据结构与算法 根据堆的定义 可以得到堆排序的方法如下 1 首先将一个无序序列建成堆 2 然后将堆顶元素与堆中的最后一个元素交换 不考虑已经换到最后的那个元素 只考虑前n 1个构成的子序列 显然 该子序列已不是堆了 但左右子树仍然是堆 可以将该子序列调整为堆 反复做第 2 步 直到剩下的子序列为空为止 第二章数据结构与算法 堆排序的方法对于规模较小的线性表并不合适 但对于较大规模的线性表来说是很有效的 在最坏情况下 堆排序需要比较的次数为0 nlong2n
