文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 天文/地理 > 排序算法的时间复杂度和空间复杂度
侵权投诉

排序算法的时间复杂度和空间复杂度

排序算法的时间复杂度和空间复杂度

常用的内部排序方法有:交换排序(冒泡排序、快速排序)、选择排序(简单选择排序、堆排序)、插入排

序(直接插入排序、希尔排序)、归并排序、基数排序(一关键字、多关键字)。

一、冒泡排序:

1.基本思想:

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

为止。

2.排序过程:

设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之

下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上"漂浮",如此反复进行,直

至最后任何两个气泡都是轻者在上,重者在下为止。

【示例】:

49 13 13 13 13 13 13 13

38 49 27 27 27 27 27 27

65 38 49 38 38 38 38 38

97 65 38 49 49 49 49 49

76 97 65 49 49 49 49 49

13 76 97 65 65 65 65 65

27 27 76 97 76 76 76 76

49 49 49 76 97 97 97 97

二、快速排序(Quick Sort)

1.基本思想:

在当前无序区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]均非空时,分别对它们进行上述的划分过程,直至所有无序子区

第1页

你可能喜欢

  • 测试工程师
  • Excel使用技巧大全(超
  • Linux系统命令及其使用详解
  • C语言经典算法
  • 使用技巧
  • 算法复杂度分析

热门文档

相关文档

  • 常用的排序算法的时间复杂度和空间复杂度

    常用的排序算法的时间复杂度和空间复杂度_数学_自然科学_专业资料 暂无评价0人阅读0次下载举报文档 常用的排序算法的时间复杂度和空间复杂度_数学_自然科学_...

  • 算法的时间复杂度和空间复杂度

    算法的时间复杂度和空间复杂度_理学_高等教育_教育专区。c++相关知识介绍(所有定义只为帮助读者理解相关概 念,并非严格定义) : 1、稳定排序和非稳定排序 、 简单...

  • 请简述各种排序算法的时间复杂度

    1、在各种排序算法中,哪些是稳定的?哪些是不稳定的? 2、请简述各种排序算法的时间复杂度,空间复杂度(最好情况,最差情况,平均情况) 答:1.快速排序、希尔排序、...

  • 算法之排序3(排序算法归类、排序时间、空间复杂度、稳...

    算法之排序3(排序算法归类、排序时间、空间复杂度、稳定性总结)_计算机软件及应用_IT/计算机_专业资料。算法之排序3(排序算法归类、排序时间、空间复杂度、稳定性总...

  • 排序算法时间复杂度的研究

    、 冒泡法 、 计数法) 、 比较排序 、 堆排序 、快 速排序等多种方法实现 , 这些算法执行效率差别较大 , 我们通常用时间复杂度和空间复杂度来衡量算法效率 ....

  • 线性时间复杂度排序算法研究及应用

    龙源期刊网 http://www.qikan.com.cn 线性时间复杂度排序算法研究及应用 作者:郭威 来源:《软件导刊》2013 年第 06 期 摘要:算法在程序设计中起着至关重要的...

  • 各种排序算法的稳定性和时间复杂度小结

    各种排序算法的稳定性和时间复杂度小结_解决方案_计划/解决方案_应用文书。计算机...合并排序比堆排序稍微快一点, 但是需要比堆排序多一倍的内存空间, 因为它需要...

  • 排序算法时间复杂度的研究

    排序算法时间复杂度的研究_IT/计算机_专业资料。排序算法时间复杂度的研究维普...们通 常用时 间复 杂度 和空间 复杂 度 来衡 量算法效率. 间复 杂度比...

  • 算法复杂度——时间复杂度和空间复杂度

    算法复杂度——时间复杂度和空间复杂度_自然科学_专业资料。算法复杂度——时间复杂...按数量级递增排列,常见的时间复杂度有:常数阶 O(1),对数阶 O(log n),线性...

  • 排序算法时间复杂度的实验统计分析

    排序算法时间复杂度的实验统计分析_工学_高等教育_教育专区。排序算法时间复杂度的...供软件 开发 人员 得 分析上述表格中所显示的数据我们可 要 占用 的空间等 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email