我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:小鱼儿主页 > 调度模块 >

简述各种排序算法的优缺点

归档日期:07-24       文本归类:调度模块      文章编辑:爱尚语录

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

  已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。首先比较a[1]与 a[2]的值,若a[1]大于a[2]则交换 两者的值,否则不变。再比较a[2]与a[3]的值,若a[2]大于a[3]则交换两者的值,否则不变。再比 较a[3]与a[4],以此 类推,最后比较a[n-1]与a[n]的值。这样处理一轮后,a[n]的值一定是这组数据中最大的。再对a[1]~a[n- 1]以相同方法 处理一轮,则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮,以此类推。共处理 n-1 轮 后a[1]、a[2]、……a[n]就以升序排列了。

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

  n 个记录的文件的直接选择排序可经过n-1 趟直接选择排序得到有序结果:

  ②第1 趟排序 在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1 个记录R[1]交换,使R[1..1]和R[2..n]分别变 为记录个数增加1 个的新有序区和记录个数减少1 个的新无序区。

  第i 趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟 排序从当前无序区中选出关键字最 小的记录 R[k],将它与无序区的第1 个记录R 交换,使R[1..i]和R 分别变为记录个数增加1 个的新有序区和记录个数减少 1 个的新无序区。

  这样,n 个记录的文件的直接选择排序可经过n-1 趟直接选择排序得到有序结果。

  已知一组升序排列数据a[1]、a[2]、……a[n],一组无序数据b[1]、 b[2]、……b[m],需将二者合并成一个升序数列。 首先比较b[1]与a[1]的值,若b[1]大于a[1],则跳过,比较b[1]与a[2]的值, 若b[1]仍然大于a[2],则继续跳过,直 到b[1]小于a 数组中某一数据a[x],则将a[x]~a[n]分别向后移动一位,将b[1]插入到原来 a[x]的位置这就完成了b[1] 的插入。b[2]~b[m]用相同方法插入。(若无数组a,可将b[1]当作n=1 的数组a)

  缺点:比较次数不一定,比较次数越少,插入点后的数据移动越多,特别是当数据总量庞大的时候,但用链表可以解决 这个问题。

  缺点:不稳定,d= 的取值是多少,应取多少个不同的值,都无法确切知道,只能凭经验来取。=

  展开全部排序的算法有很多,对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序,他们对空间的要求不高,但是时间效率却不稳定;而后面三种排序相对于简单排序对空间的要求稍高一点,但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。

  首先新建一个空列表,用于保存已排序的有序数列(我们称之为有序列表)。

  从原数列中取出一个数,将其插入有序列表中,使其仍旧保持有序状态。

  插入排序的平均时间复杂度为平方级的,效率不高,但是容易实现。它借助了逐步扩大成果的思想,使有序列表的长度逐渐增加,直至其长度等于原列表的长度。

  从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换。

  冒泡排序的平均时间复杂度与插入排序相同,也是平方级的,但也是非常容易实现的算法。

  第一步:从第一位开始找最小的元素,654中4最小,与第一位交换。结果为465

  第二步:从第二位开始找最小的元素,65中5最小,与第二位交换。结果为456

  现在开始,我们要接触高效排序算法了。实践证明,快速排序是所有排序算法中最高效的一种。它采用了分治的思想:先保证列表的前半部分都小于后半部分,然后分别对前半部分和后半部分排序,这样整个列表就有序了。这是一种先进的思想,也是它高效的原因。因为在排序算法中,算法的高效与否与列表中数字间的比较次数有直接的关系,而保证列表的前半部分都小于后半部分就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了,大大减少了数字间不必要的比较。但查找数据得另当别论了。

  首先新建一个空列表,作用与插入排序中的有序列表相同。

  找到数列中最大的数字,将其加在有序列表的末尾,并将其从原数列中删除。

  堆排序的平均时间复杂度为nlogn,效率高(因为有堆这种数据结构以及它奇妙的特征,使得找到数列中最大的数字这样的操作只需要O(1)的时间复杂度,维护需要logn的时间复杂度),但是实现相对复杂(可以说是这里7种算法中比较难实现的)。

  看起来似乎堆排序与插入排序有些相像,但他们其实是本质不同的算法。至少,他们的时间复杂度差了一个数量级,一个是平方级的,一个是对数级的。

本文链接:http://i-zyczenia.net/diaodumokuai/1042.html