大学计算机第四章.pptVIP

第*页 冒泡排序的方法 设待排数据元素的关键字为（18，20，15，32，4，25），第一趟冒泡排序后的序列状态如图所示： 　　18 20 15 32 4 25 18 20 15 32 4 25 18 15 20 32 4 25 18 15 20 32 4 25 18 15 20 4 32 25 18 15 20 4 25 32 最大数 第*页 Q：第二趟冒泡排序后的结果是什么样的？达到了最终的排序目标吗？一共需要多少次能够最后成为有序序列？ Q：你觉得冒泡排序的效率如何？如果是你，你会用什么方法来排序？ 冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低。 冒泡排序终止条件: 本趟排序未发生交换，终止排序算法 第*页 初始 第一趟 第二趟 第三趟 第四趟 第五趟 序列 排序后 排序后 排序后 排序后 排序后 26 18 18 18 18 9 18 26 26 26 9 15 32 32 32 9 15 18 54 47 9 15 26 47 9 15 32 9 15 47 15 54 设待排数据元素的关键字为（26,18,32,54,47,9,15 ) 第*页 选择排序 选择排序的方法： 扫描整个线性表，从中找出最小的元素，与第一个元素交换； 除第一个元素，对剩下的子表采用相同的方法找出次小的数，与第二个数交换； 重复上述过程； 对于长度为n的线性表，选择排序需要对表扫描n-1遍。 在最坏的情况下，选择排序需要比较n(n-1)/2次 第*页 选择排序方法：先找出表中关键字最小的元素，将其与第一个元素交换，然后在其余元素中找出关键字最小的元素，将其与第二个元素交换，依次类推，最终所有关键字按从小到大排列。 例：设待排数据元素的关键字为（15，14，22，30，37，11），每一趟排序后的序列状态如图所示： 第*页 初态： [15，14，22，30，37，15，11] 第一趟： [11] [14，22，30，37，15，15] 第二趟： [11，14] [22，30，37，15，15] 第三趟： [11，14，15] [30，37，22，15] 第四趟： [11，14，15，15] [37，22，30] 第五趟： [11，14，15，15，22] [37，30] 第六趟： [11，14，15，15，22，30] [37] 有序序列 第*页 插入排序 12 23 11 15 56 77 待排序元素 12 所谓插入排序是将无序列中的各元素依次插到已经有序的线性表中。 有序表 12 23 11 15 56 77 11 12 23 12 23 11 15 56 77 12 23 23 11 15 在最坏的情况下，选择排序需要比较n(n-1)/2次，还不算移动 第*页 练习: 1.长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为 【 B 】  A. n+1 B. n C. (n+1)/2 D. n/2 2．在长度为N的线性表中进行二分查找，在最快的情况下，需要比较的次数为【 log2N 】。 3.长度为N的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为【 】 。N*(N+1)/2 *(1/N)=(N+1)/2 第*页 练习: 4. 设待排数据元素的关键字为（67，43，14，22，33，15，11，43），用选择法将其按升序排