以图明志

计算机算法

JavaScript排序算法之堆排序

堆排序
堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素。堆排序(HeapSort)是一树形选择排序。堆排序的特点是:在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构),在当前无序区中选择关键字最大(或最小)的记录。

计算机算法

JavaScript排序算法之希尔排序

希尔排序
希尔排序,也称递减增量排序算法,是插入排序的一种高速而稳定的改进版本。希尔排序是基于插入排序的以下两点性质而提出改进方法的:插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率。但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位。希尔排序按其设计者希尔(Donald Shell)的名字命名,该算法由1959年公布。

计算机算法

JavaScript排序算法之选择排序

选择排序
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。选择排序的交换操作介于0和(n − 1)次之间。选择排序的比较操作为n(n − 1) / 2次之间。选择排序的赋值操作介于0和3(n − 1)次之间。

计算机算法

JavaScript排序算法之插入排序

插入排序
插入排序(straight insertion sort)的做法是:每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序属于稳定的排序,时间复杂性为o(n^2),空间复杂度为O(1)。

计算机算法

JavaScript排序算法之快速排序

快速排序
快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

计算机算法

JavaScript排序算法之冒泡排序

冒泡排序
冒泡排序(BubbleSort)的基本概念是:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后。

计算机算法

合并排序算法解说与例子

合并算法采用分治法的思路
合并算法采用分治法的思路,即问题划分成n个规模较小而结构和原来问题相似的子问题,递归解决这些子问题,然后合并结果,最终得到原来问题的解。合并算法主要分为三个部分,第一个部分是分解,将运来的问题分解成两个包含n/2个元素的数组的排序的问题,然后分别递归调用函数解决这两个数组的排序问题。

计算机算法

计算机编程中一些重要的算法

了解一下这些算法来拓宽视野
下面是一些比较重要的算法,原文罗列了32个,但我觉得有很多是数论里的,和计算机的不相干,所以没有选取。下面的这些,有的我们经常在用,有的基本不用。有的很常见,有的很偏。不过了解一下也是好事。也欢迎你留下你觉得有意义的算法。(注:本篇文章并非翻译,其中的算法描述大部份摘自Wikipedia,因为维基百科描述的很专业了)

计算机算法

蚂蚁爬木杆问题的算法思路

其实更像一个脑筋急转弯
题目如下:有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细,不能同时通过两只蚂蚁。开始时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序,求所有蚂蚁都离开木杆 的最小时间和最大时间。

计算机算法

面试中常见的一些算法问题

在面试中你也许会遇到其中的一些
Problem 1 : Is it a loop ? (判断链表是否有环?)方法:使用两个指针,从头开始,一个一次前进一个节点,一个前进2个节点,则最多2N,后两个指针可以重合;如果无环,则正常停止。同样的,可以找到链表的中间节点。同上。Problem 2:设计一个复杂度为n的算法找到链表倒数第m个元素。最后一个元素假定是倒数第0个。提示:双指针查找。

计算机算法

欧几里德算法(辗转相处法)练手

定理:gcd(a,b) = gcd(b,a mod b)
欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理: 定理:gcd(a,b) = gcd(b,a mod b)。证明:a可以表示成a = kb + r,则r = a mod b。假设d是a,b的一个公约数,则有:a % d == 0 , b % d == 0,而r = a - kb,因此 r % d == 0 。因此d是(b,a mod b)的公约数。

计算机算法

二叉搜索树的一些相关算法介绍

二叉搜索树知识整理
二叉搜索树中,左子树值大于根节点,右子树值大于根节点,每一层子树都遵守以上规则。二叉搜索能够大大加快搜索速度,常规的搜索只能一个个比较,算法复杂度为n,二叉搜索树由于其结果特点能够将搜索负载度减小为log(n)。首先考虑节点的插入:从根节点开始,如果待插入节点的值大于根节点则向右子树查找,否则向左子树查找,直到到达叶节点。

计算机算法

如何判断单链表中是否存在环

判断两个链表是否相交问题详解
有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。现在需要解决的问题有以下两个:如何判断一个链表是不是这类链表?如果链表为存在环,如果找到环的入口点?

计算机算法

平方根sqrt()函数的底层算法效率

数学在程序设计中是非常有用的
虽然有可能你平时没有想过这个问题,不过正所谓是“临阵磨枪,不快也光”,你“眉头一皱,计上心来”,这个不是太简单了嘛,用二分的方法,在一个区间中,每次拿中间数的平方来试验,如果大了,就再试左区间的中间数;如果小了,就再拿右区间的中间数来试。比如求sqrt(16)的结果,你先试(0+16)/2=8,8*8=64,64比16大,然后就向左移,试(0+8)/2=4,4*4=16刚好。

计算机算法

趣味算法之猴子吃桃问题

倒推的思想
猴子第一天摘下若干桃子,当即吃了一半,还不过瘾,又多吃了一个。第二天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时,见只剩下一个桃子了。求第一天共摘多少桃子。此题用倒推的办法,所以注意循环结束的条件。多数情况下用循环为递增方式,本题中用递减方式,因此是: i >= 1 。

计算机算法

趣味算法之兔子产子问题

斐波那契(Fibonacci)数列的运用
假定你有一雄一雌一对刚出生的兔子,它们在长到一个月大小时开始交配,在第二月结束时,雌兔子产下另一对兔子,过了一个月后它们也开始繁殖,如此这般持续下去。每只雌兔在开始繁殖时每月都产下一对兔子,假定没有兔子死亡,在一年后总共会有多少对兔子? 在一月底,最初的一对兔子交配,但是还只有1对兔子。
5 / 6 首页 < Prev 2 3 4 5 6 Next > 尾页 页码: