第九章 排序：本章介绍了排序的概念及常用排序方法，包括插入排序中的直接插入、折半插入排序和希尔排序，交换排序中的冒泡排序和快速排序，选择排序中的简单选择和堆排序等。每种排序算法分别介绍了基本思想、排序过程、具体实现及主要性能指标。9.1排序基本概念:本节首先介绍了和排序相关的基本概念，主要包括排序的定义、目的、分类及排序算法的性能重要评价指标，最后给出了本章排序算法中所需使用的数据类型定义。[单选题]对同一组数据分别采用直接插入排序和折半插入排序进行排序，二者可能存在的不同之处在于（ ）。
9.2直接插入排序及折半插入排序:直接插入排序与折半排序
9.3希尔排序:本节介绍了插入排序中的直接插入和折半插入排序。二者的区别为在有序表中查找插入位置时，分别采用了顺序查找和折半查找。在平均情况下，由于折半插入排序减少了查找过程关键字的比较次数，其性能高于直接插入排序。
9.4冒泡排序:本节介绍了交换排序中的冒泡排序，其核心思想是对待排序范围内相邻元素关键字进行比较，发现逆序则交换。单向冒泡排序的冒泡方向有自下至上和自上至下两种，通过采用双向冒泡算法可有效提高原有单向冒泡算法的效率。
9.5快速排序:本节介绍了交换排序中的快速排序。快速排序在每趟排序中通过左右交替方向的扫描将基准元素定位在数据表的恰当位置上。将当数据表规模较大时，在平均情况下它是所有内部排序方法中速度最快的一种。
9.6简单选择排序:本节介绍了选择排序中的简单选择排序。简单选择排序通过每趟排序在待排序范围中选择出关键字最小或最大的元素，之后和待排序范围中第一个元素进行交换的方法来实现数据表的有序排列。
9.7堆排序:堆排序通过引入树形选择思想对简单选择排序进行了改进，将待排序的数据表看作是完全二叉树的顺序存储形式。本节介绍了最大及最小堆的概念，堆排序基本思想，初始堆建立和利用最大堆实现升序排列的堆排序具体实现方法。
9.8归并排序:归并排序
9.9基数排序:基数排序
占用的辅助内存空间大小
排序的总趟数
整个排序过程中的关键字比较次数
整个排序过程中的元素移动次数
答案：整个排序过程中的关键字比较次数
[单选题]希尔排序属于（ ）类排序方法。
插入
归并
交换
选择[单选题]堆排序中所采用的堆的形态为一棵（ ）。
平衡二叉树
满二叉树
完全二叉树
二叉排序树[单选题]以下关于排序算法的说法中正确的是（ ）。
稳定的排序算法执行效率优于不稳定的排序算法
在顺序表上可以应用的排序算法都可以应用在链表上
对同一组数据采用不同的排序算法，排序的结果有可能不同
排序算法都是应用在顺序表上的，在链表上无法应用[单选题]n个元素构成的降序顺序表，采用冒泡排序按照关键字升序排列时共需进行（ ）趟排序。
1
log2n
n-1
趟数不确定[多选题]四种排序方法中，排序的趟数与数据表的初始排列顺序无关的是（ ）。
堆排序
冒泡排序
简单选择排序
直接插入排序
快速排序[多选题]以下排序方法中，具有稳定性的是（ ）。
冒泡排序
快速排序
折半插入排序
堆排序
直接插入排序
希尔排序
简单选择排序[多选题]以下排序方法中，空间复杂度为O(1)的是（ ）。
堆排序
希尔排序
快速排序
直接插入排序
冒泡排序[判断题]若采用某种排序方法对某一组数据进行排序后，关键字值相同的元素的相对次序与排序前保持一致，则说明该排序算法具有稳定性。
对
错[判断题]在外排序中需要使用外存储器来保存待排序的数据。
错
对[判断题]空间复杂度是衡量排序算法在执行过程中存储全部待排序数据所使用的总空间大小的一个指标。
错
对[判断题]对于任意一组数据，采用折半插入排序时的关键字比较次数一定小于直接插入排序。
错
对[判断题]快速排序当数据表每次划分得到的子表长度均衡时，算法的效率最高，时间复杂度为O(n)。
对
错
温馨提示支付 ￥1.00 元后可查看付费内容,请先翻页预览!
