排序算法-软考在线

排序算法


知识路径： > 计算机科学基础 > 常用算法 > 常用的排序算法 >
被考次数：20次被考频率：高频率总体答错率：48% 知识难度系数：	由软考在线用户真实做题大数据统计生成
相关知识点：8个

简单排序

简单排序包括直接插入排序、冒泡排序、简单选择排序等方法。

1）直接插入排序

直接插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。

2）冒泡排序

首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即 r[1].key>r[2].key），则交换两个记录，接着比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。这个过程称为第一趟冒泡排序，使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，结果是使关键字次大的记录被安置到第n-1个记录的位置上。当进行完第n-1趟冒泡排序时，所有记录都已有序排列。

3）简单选择排序

简单选择排序的基本思想是：在进行每趟排序时，从无序的记录中选择出关键字最小（或最大）的记录，将其插入到有序序列（初始时为空）的尾部。

希尔排序

希尔排序又称"缩小增量排序"，是对直接插入排序方法的改进。希尔排序的基本思想是：先将整个待排记录序列分割成若干序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

快速排序

快速排序是对冒泡排序的一种改进。先通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分记录继续进行排序，使得整个序列有序。

堆排序

1）堆的概念

对于n个元素的关键字序列｛k_1,k_2,…,k_n｝，当且仅当所有关键字都满足下列关系时称其为堆：

或

从序列元素间的关系来看，堆是一棵完全二叉树的层次序列。显然，堆顶元素为序列中n个元素的最小值（或最大值）。若堆顶为最小元素，则称为小根堆；若堆顶为最大元素，则称为大根堆。

2）堆排序的基本思想（小根堆）

对一组待排序记录的关键字，首先把它们按堆的定义排成一个堆序列，从而输出堆顶的最小关键字，然后将剩余的关键字再调整成新堆，便得到次小的关键字，如此反复进行，直到全部关键字排成有序序列。

归并排序

归并排序是不断将多个小而有序的序列合成一个大而有序的序列的过程。其中最常用的归并排序是二路归并排序，它是将整个序列中的元素进行分组，相邻的两个元素为一组，然后分别为每个小组进行排序，随后将两个相邻的小组合成一个组，继续进行组内排序；直到所有元素被合并成一个组内，并使组内元素有序，此时排序结束。

基数排序

基数排序的思想是按组成关键字的各个数位的值进行排序，它是分配排序的一种。基数排序把一个关键字K_i看成一个d元组，即

其中

称为最高有效位，@

称为最低有效位。基数排序可以从最高有效位开始，也可以从最低有效位开始。

基数排序的基本思想是：设立r个队列（r为基数），队列的编号为0, 1, 2, …,r-1。首先按最低有效位的值，把n个关键字分配到这r个队列中；然后从小到大将各队列中的关键字再依次收集起来；接着再按次低有效位的值把刚收集起来的关键字再分配到r个队列中。重复上述收集过程，直至最高位有效。这样得到了一个从小到大有序的关键字序列。

本知识点历年真题：

隶属试卷

题号/题型

题干

难度系数/错误率

   2018年下半年
   程序员
   上午试卷综合知识

第43题
选择题

通过设置基准(枢轴)元素将待排序的序列划分为两个子序列，使得其一个子序列的元素均不大于基准元素，另一个子序列的元素均不小于基准元素，然后再分别对两个子序列继续递归地进行相同思路的排序处理，这种排序方法称为（）。

63%

   2017年上半年
   程序员
   上午试卷综合知识

第35题
选择题

采用（）算法对序列{18,12,10,11,23,2,7}进行一趟递增排序后，其元素的排列变为{12,10,11,18,2,7,23}。

54%

>> 更多本知识点历年真题


	相关知识点：
	查找算法动态查找表静态查找表算法的描述算法与数据结构算法的基本概念及特性哈希表算法

	软考在线指南
	优惠劵及余额
	在线支付
	修改密码
	下载及使用
	购买流程
	取消订单

	联系我们
	关于我们
	联系我们
	商务合作

旗下网站群

高级资格科目
信息系统项目管理师	系统分析师
系统架构设计师	网络规划设计师
系统规划与管理师
初级资格科目
程序员	网络管理员
信息处理技术员	信息系统运行管理员

中级资格科目
系统集成项目管理工程师	网络工程师
软件设计师	信息系统监理师
信息系统管理工程师	数据库系统工程师
多媒体应用设计师	软件评测师
嵌入式系统设计师	电子商务设计师
信息安全工程师

本网站所有产品设计（包括造型，颜色，图案，观感，文字，产品，内容），功能及其展示形式，均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部，违者将依法追究责任，特此声明。
本站部分内容来自互联网或由会员上传，版权归原作者所有。如有问题，请及时联系我们。

工作时间：9:00-20:00

客服

商务合作

客服邮箱service@rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5 |