排序算法的时间复杂度和空间复杂度
常用的内部排序方法有:交换排序(冒泡排序、快速排序)、选择排序(简单选择排序、堆排序)、插入排
序(直接插入排序、希尔排序)、归并排序、基数排序(一关键字、多关键字)。
一、冒泡排序:
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]均非空时,分别对它们进行上述的划分过程,直至所有无序子区
常用的排序算法的时间复杂度和空间复杂度_数学_自然科学_专业资料 暂无评价0人阅读0次下载举报文档 常用的排序算法的时间复杂度和空间复杂度_数学_自然科学_...
算法的时间复杂度和空间复杂度_理学_高等教育_教育专区。c++相关知识介绍(所有定义只为帮助读者理解相关概 念,并非严格定义) : 1、稳定排序和非稳定排序 、 简单...
1、在各种排序算法中,哪些是稳定的?哪些是不稳定的? 2、请简述各种排序算法的时间复杂度,空间复杂度(最好情况,最差情况,平均情况) 答:1.快速排序、希尔排序、...
算法之排序3(排序算法归类、排序时间、空间复杂度、稳定性总结)_计算机软件及应用_IT/计算机_专业资料。算法之排序3(排序算法归类、排序时间、空间复杂度、稳定性总...
、 冒泡法 、 计数法) 、 比较排序 、 堆排序 、快 速排序等多种方法实现 , 这些算法执行效率差别较大 , 我们通常用时间复杂度和空间复杂度来衡量算法效率 ....
龙源期刊网 http://www.qikan.com.cn 线性时间复杂度排序算法研究及应用 作者:郭威 来源:《软件导刊》2013 年第 06 期 摘要:算法在程序设计中起着至关重要的...
各种排序算法的稳定性和时间复杂度小结_解决方案_计划/解决方案_应用文书。计算机...合并排序比堆排序稍微快一点, 但是需要比堆排序多一倍的内存空间, 因为它需要...
排序算法时间复杂度的研究_IT/计算机_专业资料。排序算法时间复杂度的研究维普...们通 常用时 间复 杂度 和空间 复杂 度 来衡 量算法效率. 间复 杂度比...
算法复杂度——时间复杂度和空间复杂度_自然科学_专业资料。算法复杂度——时间复杂...按数量级递增排列,常见的时间复杂度有:常数阶 O(1),对数阶 O(log n),线性...
排序算法时间复杂度的实验统计分析_工学_高等教育_教育专区。排序算法时间复杂度的...供软件 开发 人员 得 分析上述表格中所显示的数据我们可 要 占用 的空间等 ...
热门文档