- 浏览: 994637 次
- 性别:
- 来自: 广州
文章分类
- 全部博客 (394)
- OSGI (14)
- 多线程 (10)
- 数据库 (30)
- J2ME (1)
- JAVA基础知识 (46)
- 引用包 (1)
- 设计模式 (7)
- 工作流 (2)
- Ubuntu (7)
- 搜索引擎 (6)
- QT (2)
- Ubuntu下编程 (1)
- 小程序 (2)
- UML (1)
- Servlet (10)
- spring (16)
- IM (12)
- 文档视频转为flash格式在线播放 (19)
- Maven (8)
- 远程调用 (2)
- PHPRPC (1)
- EXTJS学习 (2)
- Hibernate (16)
- 技术文章 (38)
- flex (5)
- 海量数据处理 (5)
- FTP (8)
- JS (10)
- Struts (1)
- hibernate search (13)
- JQuery (2)
- EMail (3)
- 算法 (4)
- SVN (7)
- JFreeChart (4)
- 面试 (4)
- 正规表达式 (2)
- 数据库性能优化 (10)
- JVM (6)
- Http Session Cookie (7)
- 网络 (12)
- Hadoop (2)
- 性能 (1)
最新评论
-
hy1235366:
能够随便也发一下,你退火算法程序使用的DistanceMatr ...
模拟退火算法总结(含例子)(转) -
梅强强:
感谢分享。。帮大忙了
swftools转换文件时线程堵塞问题的解决方法 -
wenlongsust:
openoffice和文件不在同一个服务器上,用过吗?
[JODConverter]word转pdf心得分享(转) -
2047699523:
如何在java Web项目中开发WebService接口htt ...
利用Java编写简单的WebService实例 -
abingpow:
唉,看起来好像很详细很不错的样子,可惜不是篇面向初学者的文章, ...
Spring与OSGi的整合(二)(转)
(1)冒泡排序 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。 (2)选择排序 选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的。…… 例子说明好多了。序列5 8 5 2 9, 我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了, 所以选择排序不稳定的排序算法 。 (3)插入排序 (4)快速排序 快速排序有两个方向,左边的i下标一直往右走(往后),当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走(往前),当a[j] > a[center_index]。如果i和j都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 9 10 11, 现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法。(不稳定发生在中枢元素和a[j]交换的时刻) (5)归并排序 (6)基数排序 (7)希尔排序(shell) (8)堆排序 一、排序 排序法 平均时间 最差情形 稳定度 额外空间 备注 冒泡 O(n2) O(n2) 稳定 O(1) n小时较好 交换 O(n2) O(n2) 不稳定 O(1) n小时较好 选择 O(n2) O(n2) 不稳定 O(1) n小时较好 插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好 Shell O(nlogn) O(ns) 1<s<2 不稳定 O(1) s是所选分组 快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好 归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好 堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好 基数 O(logRB) O(logRB) 稳定 O(n) B是真数(0-9),R是基数(个十百)
二、查找 未写…… 三 树图 克鲁斯卡尔算法的时间复杂度为O(eloge) 普里姆算法的时间复杂度为O(n2) 迪杰斯特拉算法的时间复杂度为O(n2) 拓扑排序算法的时间复杂度为O(n+e) 关键路径算法的时间复杂度为O(n+e)
插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果和插入元素相等,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变。所以插入排序是稳定的。
归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列。不断合并直到原序列全部排好序。相等时不发生交换。所以,归并排序也是稳定的排序算法。
基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。
希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。
我们知道堆的结构是节点i的孩子为2*i和2*i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序是不稳定的排序算法
发表评论
-
Java线程(二):线程同步synchronized和volatile(转)
2014-03-17 00:09 875转载自:http://blog.csdn.net/ghsau ... -
浅谈Java多线程的同步问题(l转)
2014-03-17 00:07 909非常好的使用线程同步的文章 转载自http://www.c ... -
JVM的垃圾回收机制详解和调优(转)
2013-06-20 10:31 7091.JVM的gc概述 gc即垃圾 ... -
深入探讨 Java 类加载器(转)
2013-06-20 10:17 868转载自:http://www.ibm.com/develop ... -
java反射详解(推荐转)
2013-05-15 10:42 875载自:http://www.cnblogs.com/roll ... -
java静态方法、非静态代码块{}、静态代码块static{}(转)
2012-07-13 14:33 1473转自:http://www.cn-java.com/www1/ ... -
error 与 Exception区别(转)
2012-07-13 14:31 1073Error类和Exception类都继承自Throwab ... -
java面试题有哪些常见的(转)
2012-07-13 14:30 1192第一,谈谈final, finally, finaliz ... -
java Math.round()(转)
2012-07-11 14:17 1176public class MathTest { ... -
Java异常的分类(转)
2012-07-11 08:57 1039转载自:http://blog.csdn.net/ilibab ... -
java 内联函数(转)
2012-06-28 23:40 1815以前用过C++,知道它 ... -
堆栈,堆栈,堆和栈的区别(转)
2011-05-08 00:36 1179不防看看这篇文章:http://www.cppblog.com ... -
第二十章 指针 二 为指针分配和释放空间(转)
2011-05-08 00:10 1482载自<白话c++>:http://17de.com ... -
C#之int挑战Java之Integer(转)
2011-04-28 14:24 1330可能有些图会看不到,可以到转载处去阅读:http://kb.c ... -
Java: 堆 & 栈(转)
2011-04-28 14:16 1381栈是运行时的单位,而堆是存储的单位。栈解决程序的运行问题,即程 ... -
native2ascii 使用方法 及 Java字符编码(转)
2011-04-18 01:17 2709在做Java开发的时候,常 ... -
Unicode,ISO-8859,GBK,UTF-8编码及相互转换(java)(转)
2011-04-18 01:15 68681、函数介绍在Java中,字符串用统一的Unicode编码 ... -
GBK与UTF-8 转换乱码详解(转)
2011-04-18 01:07 3439getBytes 的功能是将字符转换成字节数组, gbk. ... -
Java TreeMap的简单实现(转)
2011-04-18 00:29 1091TreeMap的实现与二叉搜索树显示,其对应的节点格式为 E ... -
Java乱码问题分析(转)
2011-04-17 02:22 1491java采用unicode编码来处理字符。Java程序无论是从 ...
相关推荐
数据结构时间复杂度
好不容易找到的~超详细..相信看了之后都能战胜时间复杂度这个难题!
当我们评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度,因此,在算 法分析时,往往对两者不予区分,经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复 杂度,其中的f(n)一般是算法中频度最大的语句...
数据结构的基本概念和术语,算法的时间复杂度,讲述了数据结构的一些概念点,也就是最基本的一些东西,还有如何计算算法的时间复杂度之类的一些问题及举例
这是数据结构算法课程中算复杂度的作业及答案。
数据结构与算法笔记:时间复杂度和空间复杂度
时间复杂度大小比较
数据结构算法时间复杂度的计算.doc
数据结构预算法——时间复杂度分析实例课件 数据结构预算法.pdf
数据结构时间复杂度讲解.doc
数据结构有关时间复杂度的复习资料,比较全。
比较了两种排序的时间复杂度,序列一般大于10000,采用非递归的快速排序
时间复杂度和空间复杂度,大O表示法【数据结构和算法入门2】
各种基本数据结构在不同场景下的时间复杂度1
数据、数据元素、数据结构、数据类型、抽象数据类型、逻辑结构和存储结构、算法及其设计原则、算法五个要素、 问题的规模、语句频度、时间复杂度、空间复杂度。 2.理解算法五个要素的确切含义 3.掌握计算语句频度和...
对若干个数据进行操作,实现快速排序、选择排序、直接插入排序、堆排序算法时间复杂度的比较;并在排序数据中快速查找某一数据,给出查找是否成功,以及数据所在的位置信息。
算法的时间复杂度是反映算法优劣的重要指标是数 据 结 构的 重 要 理 论 基 础是学习和教学过程中贯穿始终的主要线索 该文提出 几种常用的时间复杂度计算方法使对该知识点的教学和学习变得系统和简单
对时间复杂度和空间复杂度进行超级详细的讲解
数据结构,算法的时间复杂度计算方法,算法算法时间复杂度