几种排序以及其时间复杂度 堆排序时间复杂度

看了学姐的面试题,突然很想知道答案,就去百度上搜了一下:

1.选择排序:不稳定,时间复杂度 O(n^2)

选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的位置已经是正确的了。

2.插入排序:稳定,时间复杂度 O(n^2)

插入排序的基本思想是,经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置,使得L[1..i]又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。首先比较L[i]和L[i-1],如果L[i-1]≤L[i],则L[1..i]已排好序,第i遍处理就结束了;否则交换L[i]与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),使得L[j]≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程,共需要(a),(b),(c)三次插入。

3.冒泡排序:稳定,时间复杂度 O(n^2)

冒泡排序方法是最简单的排序方法。这种方法的基本思想是,将待排序的元素看作是竖着排列的“气泡”,较小的元素比较轻,从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理,就是自底向上检查一遍这个序列,并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对,即“轻”的元素在下面,就交换它们的位置。显然,处理一遍之后,“最轻”的元素就浮到了最高位置;处理二遍之后,“次轻”的元素就浮到了次高位置。在作第二遍处理时,由于最高位置上的元素已是“最轻”元素,所以不必检查。一般地,第i遍处理时,不必检查第i高位置以上的元素,因为经过前面i-1遍的处理,它们已正确地排好序。

4.堆排序:不稳定,时间复杂度 O(nlog n)

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

5.归并排序:稳定,时间复杂度 O(nlog n)

设有两个有序(升序)序列存储在同一数组中相邻的位置上,不妨设为A[l..m],A[m+1..h],将它们归并为一个有序数列,并存储在A[l..h]。

6.快速排序:不稳定,时间复杂度 最理想 O(nlogn)最差时间O(n^2)

快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后,使得排序序列的长度能大幅度地减少。在冒泡排序中,一次扫描只能确保最大数值的数移到正确位置,而待排序序列的长度可能只减少1。快速排序通过一趟扫描,就能确保某个数(以它为基准点吧)的左边各数都比它小,右边各数都比它大。然后又用同样的方法处理它左右两边的数,直到基准点的左右只有一个元素为止。

7.希尔排序:不稳定,时间复杂度 平均时间 O(nlogn) 最差时间O(n^s)1<s<2

在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。

排序类别

时间复杂度

空间复杂度

稳定

1

插入排序

O(n2)

1

2

希尔排序

O(n2)

1

×

3

冒泡排序

O(n2)

1

4

选择排序

O(n2)

1

×

5

快速排序

O(Nlogn)

O(logn)

×

6

堆排序

O(Nlogn)

1

×

7

归并排序

O(Nlogn)

O(n)

  

爱华网本文地址 » http://www.413yy.cn/a/25101014/209024.html

更多阅读

获得小米优惠卷的几种方式 小米邀请码获得方式

获得小米优惠卷的几种方式——简介在小米官网成功购机的用户(以支付时间为准)可以到小米官网领取700元优惠券1张,可无条件购买小米网包括手机在内的任何商品,有效期3个月!到小米手机新品发布会现场签到的购票及门票F码用户将会享受到与门

地毯有哪几种材质? 地毯材质

地毯有哪几种材质?——一、地毯按材质的分类:地毯有哪几种材质? 1、地毯小知识:地毯有哪几种材质? 2、地毯,是以棉、麻、毛、丝、草等天然纤维或化学合成纤维类原料,经手工或机械工艺进行编结、栽绒或纺织而成的地面铺敷物。它是世界范围

常见的瓷砖粘合剂有哪几种? 瓷砖粘合剂配方

常见的瓷砖粘合剂有哪几种?——简介瓷砖粘合剂是一种无毒、无味、无污染、无腐蚀性,绿色环保专用的胶粘剂,可以分为三类:聚合物型、普通型、重砖型。它是选用进口聚合物胶结料改性优质水泥,再配以石英砂、多种添加剂、填料经精细加工而成

吐槽是什么意思——几种网络语言解释 膜是什么意思网络语言

吐槽是什么意思——几种网络语言解释——简介现在网络生活越来越显得重要了,一段时间不上网,别人在网上说的话你可能都听不懂了,这些语言在我们平时生活中很少用。但是随着网络的发展,这些语言也进入了我们的生活当中。下面就几个常用网

声明:《几种排序以及其时间复杂度 堆排序时间复杂度》为网友瞬间里忘记分享!如侵犯到您的合法权益请联系我们删除