[其它考试]第1章_数据结构与算法.ppt

* 查找23的过程： mid=(low+high)/2不进位取整 high=mid-1 ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low mid ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low mid high high low=mid+1 ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) * 1.8 排序技术 主要掌握各类排序方法的原理及其时间复杂度 1、排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。 2、排序过程的组成步骤： 首先比较两个关键字的大小； 然后将记录从一个位置移动到另一个位置。 * 排序方法 插入排序 选择排序 交换排序 归并排序 简单插入排序 希尔插入排序 简单选择排序 堆排序 冒泡排序 快速排序 * 考点20：交换类排序 交换排序的基本思想：交换数据元素的顺序 1、冒泡排序：依次比较相邻的元素，若逆序则交换。 最坏情况下，需要比较的次数为 n(n-1)/2，最好的情况下比较n-1次。 * 49 36 41 65 11 78 36 65 36 41 56 36 41 65 41 36 41 56 11 78 36 36 41 49 11 56 49 25 25 25 11 49 49 56 11 11 11 25 25 25 25 * 2、快速排序：取一元素T，将小于T的元素移至前面，大于T的元素移至后面，如此下去。 最坏情况下时间复杂度为O(n2) 快速排序需要占用较多的存储空间 * 考点21：插入类排序 基本思想：依次将元素插入到有序的线性表中。 1、简单插入排序：依次将无序序列中的各元素插入到有序的线性表中。 最坏情况下，需要比较的次数为 n(n-1)/2 * 待排元素序列：[53] 27 36 15 69 42 第一次排序： [27 53] 36 15 69 42 第二次排序： [27 36 53]15 69 42 第三次排序： [15 27 36 53]69 42 第四次排序： [15 27 36 53 69]42 第五次排序： [15 27 36 42 53 69] 简单插入排序示例 * 2、希尔排序：将整个待排序元素分成若干个子序列分别进行直接插入排序 最坏情况下，需要比较的次数为O(n1.5) * 考点22：选择类排序 基本思想：选择最小的元素将其交换到最前面。 1、简单选择排序：选择最小的元素将其交换到最前面，对剩下的元素也按此原则处理。（P44图1.40） 最坏情况下，需要比较的次数为 n(n-1)/2 * 2、堆排序：用完全二叉树进行处理，最坏情况下，需要比较的次数为nlog2n。它适合较大规模的线性表排序。 * 各种排序方法的时间复杂度对比 排序方法 时间复杂度 平均情况 最坏情况 最好情况 直接插入排序 O(n2) O(n2) O(n) 冒泡排序 O(n2) O(n2) O(n) 希尔排序 O(nlog2n) O(n1.5) 　 快速排序 O(nlog2n) O(n2) O(nlog2n) 简单选择排序 O(n2) O(n2) O(n2) 堆排序 O(nlog2n) O(nlog2n) O(nlog2n) * 各种排序方法各有优缺点，故在不同情况下可作不同的选择。 若待排序的记录个数n较小时，可采用简单选择排序方法。 若n较大时，应采用快速排序或堆排序 若待排序的记录已基本有序，可采用冒泡排序。 * 例题讲解 * 1、在长度为n的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为 【1】 。 2、对长度为n的线性表进行顺序查找，在最坏的情况下所需要的比较次数为 Ａ) n+1 B) n C) (n+1)/2 D) n/2 log2n B * 3、假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为 A) log2n B) n2 C) O(n1.5) D) n(n-1)/2 4、已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是 A) 堆排序 B) 直接插入排序 C) 快速排序 D) 直接选择排序 D D * 5、 冒泡排序算法在最好的情况下的元素交换次数为 【3】 。 6、在最坏情况下，堆排序需要比较的次数为 【4】 。 7、最简单的交换排序方法是 A) 快速排序 B) 选择排序 C) 堆排序