算法系列

  算法对程序员来说是熟悉的陌生人,编过大量代码后突然被哪个问到算法是什么也有时不知从何说起,简单来说是没有好好总结过仔细分析过。大学里面导师整天苦口婆心的教导算法有多么多么重要,但哪个能真正听得进去,即使认真的学了出了社会过个两三个月就忘到九霄云外了,记得算法的排序有几种就算不错了的。说到底还是没有真正的理解,而理解是建立在应用之上,用多了亲历了也就知道其中的道理,学好了也能锻炼自己的抽象能力,因此平时没事就多拿出来多练哈,没准哪天突然开窍了也说不定。

  自己也是意识到学好算法的重要性,因此一直也在找一些好的资料,之前是准备找一本数据结构的书好好从头开始看,不过书上理论太多,而且都是伪代码,因此看完后也只能记住一些名词定义达不到灵活现用的地步。后来在网上找一些牛人的文章,以下谈谈自己的一点点总结吧。

  算法不分语言的,只要有思想不论哪种语言都能实现算法。在此也就说排序,排序分为4种:1.交换排序:冒泡与快排;2.选择排序:选排与堆排序;3.插入排序:插排与希尔排序;4.合并排序;

  冒泡:冒泡的思想可以看做是一堆石头沉入水底,小的不断往下浮,大的往下沉,小的从底下不断与它上面的想交换,不断的重复这个过程

那么我们就数组:50 、10、30、20、40      

要达到冒泡的效果,我们就要把一组数字竖起来看,大家想想,如何冒泡?如何来体会重的沉底,轻的上浮?

第一步:  我们拿40跟20比,发现40是老大,不用交换。

第二步:  然后向前推一步,就是拿20跟30比,发现30是老大,就要交换了。

第三步:拿交换后的20跟10比,发现自己是老大,不用交换。

第四步:拿10跟50交换,发现50是老大,进行交换。

最后,我们经过一次遍历,把数组中最小的数字送上去了

以下是js实现的实例:

    //冒泡排序    function BubbleSort(arr){var temp=0;

for (var i=0;i<arr.length -1;i++){//有5个数,不与自己比较要比较4次        for(var j=arr.length-1;j>i;j--){//每次都从 最后一位开始,每次比较后次数都在减少1            if(arr[j-1]>arr[j]){            temp=arr[j-1];            arr[j-1]=arr[j];            arr[j]=temp;            }        }     }return arr;    }

以上是http://www.cnblogs.com/huangxincheng/archive/2011/11/14/2249046.html 算法系列15天速成中介绍的思想,以C#实现且算法之间进行了效率比较,这里自己以JS代码自己重新实现了。

  每天一小步,信心一大步。

 

时间: 2024-10-28 19:09:02

算法系列的相关文章

缓存淘汰算法系列之3——FIFO类

缓存淘汰算法系列之3--FIFO类 1 FIFO 1.1. 原理 按照"先进先出(First In,First Out)"的原理淘汰数据. 1.2. 实现 FIFO队列,具体实现如下: 1. 新访问的数据插入FIFO队列尾部,数据在FIFO队列中顺序移动: 2. 淘汰FIFO队列头部的数据: 1.3. 分析 l 命中率 命中率很低,因为命中率太低,实际应用中基本上不会采用. l 复杂度 简单 l 代价 实现代价很小. 2. Second Chance 2.1. 原理 FIFO算法的改进

算法系列(二十) 计算中国农历(二)

所谓的"天文算法",就是利用经典力学定律推导行星运转轨道,对任意时刻的行星位置进行精确计 算,从而获得某种天文现象发生时的时间,比如日月合朔这一天文现象就是太阳和月亮的地心黄经(视黄 经)差为0的那一瞬间.能够计算任意时刻行星位置的一套理论就被称为星历表,比较著名的星历表有美 国国家航空航天局下属的喷气推进实验室发布的DE系列星历表,还有瑞士天文台在DE406基础上拓展的瑞 士星历表等等.根据行星运行轨道直接计算行星位置通常不是很方便,更何况大多数民用天文计算用不上 那么多精确的轨道参

算法系列(十九) 用天文方法计算日月合朔(新月)

中国农历的朔望月是农历历法的基础,而朔望月又是严格以日月合朔发生的那一天作为月首,因此日 月合朔时间的计算是制定农历历法的关键.本文将介绍ELP-2000/82月球运行理论,以及如何用ELP- 2000/82月球运行理论计算日月合朔时间. 要计算日月合朔时间, 首先要对日月合朔这一天文现象进行数学定义.朔望月是在地球上观察到的月相周期,平均长度约等于 29.53059日,而恒星月(天文月)是月亮绕地球公转一周的时间,长度约27.32166日.月相周期长度比恒 星月长大约两天,这是因为在月球绕地球

算法系列(十四) 狼、羊、菜和农夫过河问题

题目描述:农夫需要把狼.羊.菜和自己运到河对岸去,只有农夫能够划船,而且船比较小,除农 夫之外每次只能运一种东西,还有一个棘手问题,就是如果没有农夫看着,羊会偷吃菜,狼会吃羊. 请考虑一种方法,让农夫能够安全地安排这些东西和他自己过河. 这个题目考察人的快速逻辑运算和短期记忆力.分析一下,在狼->羊->菜这个食物链条中 ,"羊"处在关键位置,解决问题的指导思想就是将"羊"与"狼"和"菜"始终处于隔离状态,也 就是说

数据结构与算法系列(1)时间测试

前言 好久都把数据结构和算法的东西忘完了,最近想重温下这些知识.因此就写了<<数据结构与 算法系列>的文章,希望能和大家共同学习,共同探讨这方面的知识.希望大家多多指异. 1.时间测试 由于本部分内容采用了一种实用的方法来分析数据结构与算法检测,所以在这里避开了使用大O分 析法,而采用运行简单基准测试的方法来代替.这种测试将会说明运行一段代码需要多少秒数(或者 无论什么时间单位). 基准法测试是使用时间测试的方法来衡量运行完整算法所花费的时间长度.如同科学一样,基准测 试也像是一门艺术,

[算法系列之二十四]后缀树(Suffix Tree)

之前有篇文章([算法系列之二十]字典树(Trie))我们详细的介绍了字典树.有了这些基础我们就能更好的理解后缀树了. 一 引言 模式匹配问题 给定一个文本text[0-n-1], 和一个模式串 pattern[0-m-1],写一个函数 search(char pattern[], char text[]), 打印出pattern在text中出现的所有位置(n > m). 这个问题已经有两个经典的算法:KMP算法 ,有限自动机,前者是对模式串pattern做预处理,后者是对待查证文本text做预处

[算法系列之十九]最长公共子序列

题目 最长公共子序列 分析 有两个字符串S1和S2,求一个最长公共子串,即求字符串S3,它们同时是S1和S2的子串,且要求它们的长度最长,并确定这个长度.这个问题我们称之为最长公共子序列问题. 与求最长递增子序列一样,我们首先将原问题分割成一些子问题,我们用dp[i][j]表示S1中前i个字符和S2中前j个字符分别组成的两个前缀字符串的最长公共子串长度.显然的,当i,j较小时我们可以直接给出答案,如dp[0][j] 必等于0.那么,假设我们已经求的dp[i][j](0 <= i < x,0 &

[算法系列之十七]数据压缩之位图

概述 在之前的文章([算法系列之十六]数据压缩之游程编码)中,我们知道了如何压缩一段重复元素组成的数据.这种压缩称为"游程编码",该算法在无损数据压缩传输时非常方便.但问题是数据必须遵循特定格式.比如,字符串"aaaaaaaabbbbbbbb"可以被压缩成"a8b8".此时,16个字符的字符串被压缩成4个字符,没有丢失任何信息,而长度却只有原始长度的25%.但当字符(元素)以不同方式分散时,问题就会出现.如果字符不变,但是没有连续出现,会是什么情

[算法系列之二十三]线段树(Interval Tree)

一 背景 在信息学竞赛中,我们经常会碰到一些跟区间有关的问题,比如给一些区 间线段求并区间的长度,或者并区间的个数等等.这些问题的描述都非常简单,但是通常情况下数据范围会非常大,而朴素方法的时间复杂度过高,导致不能在规定时间内得到问题的解.这时,我们需要一种高效的数据结构来处理这样的问题,在本文中,我们介绍一种基于分治思想的数据结构--线段树. 二 简介 线段树是一种二叉树形结构,属于平衡树的一种.它将线段区间组织成树形的结构,并用每个节点来表示一条线段.一棵[1,10)的线段树的结构如图1.1

[算法系列之二十六]字符串匹配之KMP算法

一 简介 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特-莫里斯-普拉特操作(简称KMP算法).KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的. 二 基于部分匹配表的KMP算法 举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含搜索串"ABCDABD"? 步骤1:字符串"BBC ABC