ITeye博客

shmilyyy的博客

shmilyyy · 共 12 篇文章

将阿拉伯数字转换成中文数字表示

package contest.numtochi; import java.util.HashMap; import java.util.Scanner; public class NumToChi{ //创建数字和中文数字一一对应的映射 private HashMap<Integer, String> map; //创建位数和中文单位的一一映射 private HashMap<Integer, String> unit; // 判断输入的字符串是否全是数字 public boolean isNum(String str) { boolean flag = true; try { Integ…

2013-08-19 22:38 · 随写 · 评论(1)

五种常见算法之贪心算法

贪心算法 贪心算法: 贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。 贪心算法基本思路: 从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的求的更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。 贪心算法存在的问题: 1.不能保证求的最后解是最佳的。 2.不能用来求最大或最小解问题。 3.只能求满足某些约束条件的可行解的范围。 贪心算法的基本要求: 1.贪心选择性质:指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。 2.具有最优子结构性质:一个问题的最优解包含其子问题的最优解。 物…

2013-04-09 15:17 · 算法 · 评论(0)

五种常见算法之分治策略

分治策略 分治法基本思想: 1.大问题分解为子问题,这些子问题相互独立且与原问题相同。 2.分别求解子问题。如果子问题的规模依然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。 3.合并解集,自底向上逐步求出原来问题的解。 4.分治发的设计思想是,讲一个难以直接解决的大问题分割成一些规模较小的相同问题,以便各个击破,分而治之。 分治法的使用条件: 1.该问题的规模缩小到一定程度就可以容易的解决。 2.该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质(当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质)。 3.利用该…

2013-04-09 10:18 · 算法 · 评论(0)

基数排序

基数排序算法 (radixsort)则是属于“分配式排序”(distribution sort),基数排序法又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的比较性排序法。 基数排序(Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,…

2013-04-08 10:08 · 算法 · 评论(0)

计数排序

计数排序 计数排序思想: 就是对于每一个输入元素x,确定出小于x的元素个数。有了这一信息就可以把x直接放在它最终输出的数组中的位置。(当有元素相同时,此方案还要修改)。 package com.countingsort.yy; /** * 计数排序算法 *@author yuyang_csu *@data 2013-4-7 */ class CountingSort { /** * 计数排序方法 * * @param a * :待排序数组 * @param b * :存放排序好的数组 * @param k * :大于数组中所有整数的最小整数 */ private static void co…

2013-04-07 17:08 · 算法 · 评论(0)

快速排序算法

快速排序算法 基本思想: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都小,然后再按此方法对这两部分数据进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 算法过程: step1:指定枢纽 step2:通过一趟排序将以枢纽为中心,把待排记录分割为独立的两部分,使得左边记录的关键字小于枢纽值,右边记录的关键字大于枢纽值。 step3:对左右两部分记录序列重复上述过程,依此类推,直到子序列中只剩下一个记录或不含记录为止。 package com.quicksort.yy; /** * 快速排序 *@author yuyang_cs…

2013-04-07 14:48 · 算法 · 评论(0)

冒泡排序

冒泡排序算法 冒泡排序基本思想: 设数组arr中存放了n个元素,循环n-1次如下的排序过程: step1:一次比较相邻两个数据元素,若a*>a,则交换两个数据元素,否则不交换。 step2:当完成一趟交换以后,最大的元素将会出现在数组的最后一个位置。 step3:一次重复以上过程,当第n-1趟结束时,整个n个数据元素集合中次小元素被放在a中,a中放置最小的数据元素 package com.bubblesort.yy; /** * 冒泡排序 * * @author yuyang_csu *@data 2013-4-7 */ public class BubbleSort { // 声明待排序的…

2013-04-07 11:32 · 算法 · 评论(0)

归并排序

归并排序算法 归并排序思想:将待排序的元素分成大小大致相同的2个子集合,分别对2个子集合进行排序,最终将排序好的子集合合并成为索要要求的排好序的集合。 step1:把待排序的n个记录看作是长度为1的有序序列。将相邻的子序列两两归并成为长度为2或1的有序序列。 step2:把得到的n/2个长度为2的有序子序列在归并为长度为2*2的有序序列。 step3:按step2的方式,重复对相邻的有序子序列进行归并操作,直到成为一个有序序列为止。 package com.mergesort.yy; /** * 归并排序 *@author yuyang_csu *@data 2013-4-6 */ publ…

2013-04-06 21:17 · 算法 · 评论(0)

堆排序

堆排序算法 首先介绍一下什么是堆,这里所说的堆其实是二叉堆。二叉堆是完全二叉树的应用,此外二叉堆又分为最小和最大二叉堆之分。最小二叉堆满足父节点的值小于儿子节点的值(除根节点外,因为根节点没有父节点)。很明显,说道这里最大二叉堆大家也就知道了,就不再叙述。 堆排序分为两个阶段:第一个阶段就是构建一个最小或者最大二叉堆。第二阶段就是采用选择排序的思想,将根节点交换到后面,再将其余的节点进行调整,成为新的二叉堆,重复进行,直到排序完成。下面将为大家展示如何用堆排序输出降序排列的序列。 按降序排列 package com.heapsort.yy; /** * 堆排序算法 *@author yuya…

2013-04-06 19:23 · 算法 · 评论(0)

优先队列(堆)

优先队列(堆) 1.优先队列模型: 优先队列是允许下列两种操作的数据结构:insert(插入)以及deleteMin(删除最小者)。insert操作等价于入队,而deleteMin操作则等价于出队,它的工作是找到,返回并删除优先队列中的最小元素。 2.二叉堆: 结构性质: 堆是一棵完全二叉树---深度为h的二叉树,其他各层的节点数都达到了最大,h层的节点也是从左向右填入的。由于完全二叉树很有规律,所以可以用数组来存储完全二叉树中的节点。该数组0位置空出,从下表为1的位置开始填充。以广度遍历存储。 堆序性质: 父母节点的关键字不大于孩子节点的关键字(除根节点,因为根节点没有父母节点)。这样我们…

2013-04-05 21:44 · 数据结构 · 评论(0)

希尔排序

希尔排序 希尔排序的思想是分组的直接插入排序。由直接插入排序可知,若数据序列越接近有序,则时间效率越高;再者,当n越小时,时间效率越高。希尔排序就是基于这两点对直接插入排序进行改进的。 希尔排序算法描述如下 : 1.将一个数据序列分成若干组,每组由若干相隔一段距离的元素组成,这段距离称为增量,在一个组内采用直接插入排序算法进行排序。 2.增量的初值通常为数据序列长度的一半,以后每趟增量逐渐缩小,最后为1.随着增量的逐渐减小,组数也减少,组内元素个数增加,整个序列接近有序。当增量为1时,只有一组,元素是整个序列,在进行一次直接插入排序即可。 package com.shellsort.yy; …

2013-04-05 20:05 · 算法 · 评论(0)

插入排序

插入排序 插入排序是最简单的排序算法之一。插入排序由N趟排序组成。当i从1至N趟,插入排序保证数组下标i-1之前的元素为已排序状态。进行排序时,若arr*<arr则将arr 和arr交换,再将arr与前一个元素比较,直到不比前一个元素小为止。若arr >arr,则不作任何操作。 package com.insertionsort.yy; /** * 直接插入排序(升序) *@author yuyang_csu *@data 2013-4-5 */ public class InsertionSort { private int arr[]; public InsertionSort(int …

2013-04-05 14:36 · 算法 · 评论(0)