- Posted by Admin on January 15, 2012
经典排序算法 - 冒泡排序Bubble sort
原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,
这样一趟过去后,最大或最小的数字被交换到了最后一位,
然后再从头开始进行两两比较交换,直到倒数第二位时结束,其余类似看例子
例子为从小到大排序,
原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 |
第一趟排序(外循环)
第一次两两比较6 > 2交换(内循环)
交换前状态| 6 | 2 | 4 | 1 | 5 | 9 |
交换后状态| 2...
[More]
- Posted by Admin on January 15, 2012
经典排序算法 - 归并排序Merge sort
原理,把原始数组分成若干子数组,对每一个子数组进行排序,
继续把子数组与子数组合并,合并后仍然有序,直到全部合并完,形成有序的数组
举例
无序数组[6 2 4 1 5 9]
先看一下每个步骤下的状态,完了再看合并细节
第一步 [6 2 4 1 5 9]原始状态
第二步 [2 6] [1 4] [5 9]两两合并排序,排序细节后边介绍
第三步 [1 2 4 6] [5 9]继续两组两组合并
第四步 [1 2 4 5 6 9]合并完毕,排序完毕
输...
[More]
- Posted by Admin on January 15, 2012
原理类似桶排序,同样需要一个很大的鸽巢[桶排序里管这个叫桶,名字无所谓了]
鸽巢其实就是数组啦,数组的索引位置就表示值,该索引位置的值表示出现次数,如果全部为1次或0次那就是桶排序
例如
var pigeonHole = new int[100];
pigeonHole[0]的值表示0的出现次数...
pigeonHole[1]的值表示1的出现次数...
pigeonHole[2]的值表示2的出现次数...
举例
var pigeonHole = new int[10];//10个位置
var A =...
[More]
- Posted by Admin on January 15, 2012
经典排序算法 - 基数排序Radix sort
原理类似桶排序,这里总是需要10个桶,多次使用
首先以个位数的值进行装桶,即个位数为1则放入1号桶,为9则放入9号桶,暂时忽视十位数
例如
待排序数组[62,14,59,88,16]简单点五个数字
分配10个桶,桶编号为0-9,以个位数数字为桶编号依次入桶,变成下边这样
| 0 | 0 | 62 | 0 | 14 | 0 | 16 | 0 | 88 | ...
[More]
- Posted by Admin on January 15, 2012
经典排序算法 – 插入排序Insertion sort
插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。
插入排序方法分直接插入排序和折半插入排序两种，这里只介绍直接插入排序，折半插入排序留到“查找”内容中进行。
图1演示了对4个元素进行直接插入排序的过程，共需要(a),(b),(c)三次插入。
代码
public class InsertionSorter
...
[More]
- Posted by Admin on January 15, 2012
经典排序算法 - 桶排序Bucket sort
补充说明三点
1,桶排序是稳定的
2,桶排序是常见排序里最快的一种,比快排还要快…大多数情况下
3,桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法
我自己的理解哈,可能与网上说的有一些出入,大体都是同样的原理
无序数组有个要求,就是成员隶属于固定(有限的)的区间,如范围为[0-9](考试分数为1-100等)
例如待排数字[6 2 4 1 5 9]
准备10个空桶,最大数个空桶
[6 2 4 1 5 9] ...
[More]
- Posted by Admin on August 10, 2011
Java中产生随机数1 . 调用java.lang下面Math类中的random()方法产生随机数 新建一个文件后缀名为java的文件，文件名取为MyRandom,该类中编写如下的代码： public class MyRandom { &nb...
[More]
- Posted by Admin on July 15, 2011
当我们想要获得一个唯一的key的时候，通常会想到GUID。这个key的长度是36位，如果将这个36为的字符串存储或是用url传递的时候就会感觉非常的难看。就算去掉-分隔符也有32位，如 EAA82B2DA9EA4E5B95330BAF9944FB35，如果转为数字序列 如将guid转为int64数字序列，长度也会有19位。如byte[] buffer = Guid.NewGuid().ToByteArray(); long long_guid=BitConverter.ToInt64(buffer, 0);这样就会得到一个类似于 5472976187161141196 ...
[More]
- Posted by Admin on October 4, 2010
【什么是堆】 概念：堆是一种特殊的二叉树，具备以下两种性质 1）每个节点的值都大于（或者都小于，称为最小堆）其子节点的值 2）树是完全平衡的，并且最后一层的树叶都在最左边 这样就定义了一个最大堆。如下图用一个数组来表示堆：那么下面介绍二叉堆：二叉堆是一种完全二叉树，其任意子树的左右节点（如果有的话）的键值一定比根节点大，上图其实就是一个二叉堆。你一定发觉了，最小的一个元素就是数组第一个元素，那么二叉堆这种有序队列如何入队呢？看图：假设要在这个二叉堆里入队一个单元，键值为2，那只需在数组末尾加入这个元素，然后尽可能把这个元素往上挪，直到挪不动，经过了这种复...
[More]
- Posted by Admin on October 4, 2010
【什么是Bit-map】所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。如果说了这么多还没明白什么是Bit-map，那么我们来看一个具体的例子，假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟64Bytes的空间，将这些空间的所有Bit位都置为0(如下图：)然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置为1（可以...
[More]
- Posted by Admin on October 4, 2010
【什么是Hash】 Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。HASH主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说，hash就是找到一...
[More]
- Posted by Admin on October 4, 2010
【什么是Bloom Filter】Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。 这里有一篇关于Bloom Filter的详细介绍，不太懂的博友可以看看。【适用范...
[More]