搜索

排序法都有哪些

gecimao 发表于 2019-08-13 22:25 | 查看: | 回复:

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止。

  每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。

  两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。

  设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上漂浮,如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。

  在当前无序区R[1..H]中任取一个数据元素作为比较的基准(不妨记为X),用此基准将当前无序区划分为左右两个较小的无序区:R[1..I-1]和R[I+1..H],且左边的无序子区中数据元素均小于等于基准元素,右边的无序子区中数据元素均大于等于基准元素,而基准X则位于最终排序的位置上,即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H),当R[1..I-1]和R[I+1..H]均非空时,分别对它们进行上述的划分过程,直至所有无序子区中的数据元素均已排序为止。

  堆排序是一树形选择排序,在排序过程中,将R[1..N]看成是一颗完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

  2.堆的定义:N个元素的序列K1,K2,K3,...,Kn.称为堆,当且仅当该序列满足特性:

  堆实质上是满足如下性质的完全二叉树:树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆,它对应的完全二叉树如上图所示。这种堆中根结点(称为堆顶)的关键字最小,我们把它称为小根堆。反之,若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字,则称之为大根堆。

  堆排序正是利用小根堆(或大根堆)来选取当前无序区中关键字小(或最大)的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是:将当前无序区调整为一个大根堆,选取关键字最大的堆顶记录,将它和无序区中的最后一个记录交换。这样,正好和直接选择排序相反,有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。

  【示例】:对关键字序列42,13,91,23,24,16,05,88建堆

  (1)若n较小(n=50),则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多,因而当记录本身信息量较大时,用直接选择排序较好。

  (2)若文件的初始状态已按关键字基本有序,则选用直接插入或冒泡排序为宜。

  (3)若n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序。

  (4)在基于比较排序方法中,每次比较两个关键字的大小之后,仅仅出现两种可能的转移,因此可以用一棵二叉树来描述比较判定过程,由此可以证明:当文件的n个关键字随机分布时,任何借助于比较的排序算法,至少需要O(nlog2n)的时间。

  这句话很重要它告诉我们自己写的算法是有改进到最优当然没有必要一直追求最优

  说明:逐个将后一个数加到前面的排好的序中。在直接插入排序过程中,对其中一个记录的插入排序称为一次排序;直接插入排序是从第二个记录开始进行的,因此,长度为n的记录序列需要进行n-1次排序才能完成整个序列的排序。时间复杂度为O(n2)。

  说明:每次将后面的最小的找出来插入前面的已排好的序中。同理,具有n个记录的序列要做n-1次排序。

  说明:两个两个比较,将大的往后移。通过第一次冒泡排序,使得待排序的n个记录中关键字最大的记录排到了序列的最后一个位置上。然后对序列中前n-1个记录进行第二次冒泡排序。。。对于n个记录的序列,共需进行n次冒泡排序。时间复杂度为O(n2)。void BubbleSort(elemtype x[],int n)

  说明:所谓归并排序就是将两个或两个以上的有序数据序列合并成一个有序数据序列的过程。

  简单排序法也称序列评定法,是指管理者把本部门的所有员工从绩效最高者到绩效最低者(或从最好者到最差者)进行排序,即对一批考核对象按照一定标准排出“1、2、3、4……”的顺序。

  该方法也应用也工作评价上,由负责工作评价的人员,根据其对企业各项工作的经验认识和主观判断,对各项工作在企业中的相对价值进行整体的比较,并加以排队。在对各项工作进行比较排序时,一般要求工作评价人员综合考虑以下各项因素:工作职责、工作权限、岗位资格、工作条件、工作环境等。权衡各项工作在各项因素上的轻重程度并排定秩序后,将其划入不同的工资等级内。

  简单排序法的优点:该方法的优点是简便易行,具有一定的可信性,可以完全避免趋中倾向或宽严误差。

  缺点是考核的人数不能过多,以5—15人为宜,而且只适用于考核同类职务的人员,应用范围受限,不适合在跨部门人事调整方面应用。

  交替排序法则是指管理者对被评估员工的名单进行审查后,从中找出工作绩效最好的员工列为第一名,并将其的名字从名单上划去。然后从剩下的名单中找出工作绩效最差的员工排为最后一名,也把其名字从名单中划去。随后,在剩下的员工中管理者再找出一名工作绩效最好的员工将其排为第二名,找出一名最差的员工列为倒数第二名,以此类推,直到将所有的员工排序完。

本文链接:http://baumseelen.com/duipaixu/773.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部