等级考基础数据结构.pptVIP

冒泡排序的效率分析 若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0； 若待排序的元素为逆序，则需进行n-1趟排序，比较次数为(n2-n)/2，移动次数为3(n2-n )/2， 最坏情况比较n(n-1)/2 因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。 6.3.2 快速排序 基本思想是：取待排序序列中的某个元素（一般第一个元素）作为基准，通过一趟排序，将待排元素分为左右两个子序列， 左子序列元素的排序码均小于或等于基准元素的排序码， 右子序列的排序码则大于基准元素的排序码， 然后分别对两个子序列继续进行快速排序，直至整个序列有序。 元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面，排序码较小的记录一次就能够交换到前面，记录每次移动的距离较远，因而总的比较和移动次数较少。 例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图7-4所示。 3．快速排序的效率分析 若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点数n与二叉树深度h应满足log2nhlog2n+1 ，所以总的比较次数不会超过(n+1) log2n。因此，快速排序的最好时间复杂度应为O（nlog2n）。 已经证明，快速排序的平均时间复杂度也为O（nlog2n）。 若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，总的比较次数为n(n-1)/2 。因此，快速排序的最坏时间复杂度为O(n2)。 快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。 快速排序是一种不稳定的排序方法。 6．4 选择排序 6 . 4.1 直接选择排序 基本思想 直接选择排序是一种简单的排序方法。基本思想是：第一次从array[0]~array[n-1]中选取最小值，与array[0]交换，第二次从array[1]~array[n-1]中选取最小值，与array[1]交换，第三次从array[2]~array[n-1]中选取最小值，与array[2]交换，…，第i次从array[i-1]~array[n-1]中选取最小值，与array[i-1]交换，…, 第n-1次从array[n-2]~array[n-1]中选取最小值，与array[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。 例如，给定n=8，数组R中的8个元素的排序码为：（8，3，2，1，7，4，6，5），则直接选择排序过程如图7-5所示。 直接选择排序的效率分析 在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要进行n-i次比较（1≤i≤n-1），而每次交换最 多需3次移动，因此，总的比较次数C= =(n2-n)/2， 总的移动次数M= =3(n-1)。 直接选择排序的时间复杂度为O(n2)数量级，所以当记录占用的字节数较多时，通常比直接插入排序的执行速度要快一些。 最坏情况比较n(n-1)/2 7．5 归并排序 1、基本思想：将两个有序子区间（有序表）合并成一个有序子区间，一次合并完成后，有序子区间的数目减少一半，而区间的长度增加一倍，当区间长度从1增加到n（元素个数）时，整个区间变为一个，即为有序序列. 例如，给定排序码46，55，13，42，94，05，17，70，二路归并排序过程如图7-10所示。算法P284 归并排序的效率分析 归并排序的时间复杂度为O(nlog2n)。 归并排序时，需要利用与待排序数组相同的辅助数组作临时单元，故该排序方法的空间复杂度为O(n)，比前面介绍的其它排序方法占用的空间大。 对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是　A) 冒泡排序为n/2 ?????? B) 冒泡排序为n 　　C) 快速排序为n? ????? D) 快速排序为n(n-1)/2 D B 例:线性表的顺序存储结构和线性表的链式存储结构分别是?A) 顺序存取的存储结构、顺序存取的存储结构B) 随机存取的存储结构、顺序存取的存储结构C) 随机存取的存储结构、随机存取的存储结构D) 任意存取的存储结构、任意存取的存储结构 在单链表中，增加头结点的目的是A) 方便运算的实现B) 使单链表至少有一个结点C) 标识表结点中首结点的位置 D) 说明单链表是线性表的链式存储实现  A 例:对于长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为?　A) log2n ?? B) n/2???