常用算法

1.插入排序

基本思想:

 在已排序的i条记录中插入一条新记录，得到有序的i+1条记录。

特别提示：可以牺牲数组０的空间来作为插入的中间变量。 

改进插入顺序：如果在插入过程中奖顺序查找改为折半查找，那么关键字的比较次数可以减少，记录的移动次数不变。 

链式插入排序：不用数组而用链表存储数据，就不需要移动数据而仅仅需要改变链即可以实现

 

要点：设立哨兵，作为临时存储和判断数组边界之用。

 

直接插入排序示例：

 

 

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

 

2、插入排序—希尔排序

基本思想：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

操作方法：

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行k 趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

希尔排序的示例：

 

算法实现：

我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数

即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

 

3. 选择排序

基本思想：

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

简单选择排序的示例：

 

操作方法：

第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；

第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；

以此类推.....

第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，

直到整个序列按关键码有序。

 

4. 交换排序—冒泡排序（Bubble Sort）

基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

冒泡排序的示例：

 

 

他的改进算法： 快速排序

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

 

百度文库：

http://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95?fr=aladdin

 

5、归并排序 

基本思想

将两个有序的列表归并成一个有序列表的方法

归并操作

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

如　设有数列{6，202，100，301，38，8，1}

初始状态：6,202,100,301,38,8，1

第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；

第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

总的比较次数为：3+4+4=11,；

逆序数为14；

算法描述

归并操作的工作原理如下：

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

 

6、堆排序 

基本思想

堆实质是满足如下性质的完全二叉树，树中任一非叶节点的关键字不大于（或不小于）其左右孩子结点的关键字。 

根节点的关键字是堆里所有节点关键字中最小者的堆称为小顶堆； 堆是一种完全二叉树，一般使用数组来实现。

 

算法分析

堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。

平均性能

O(N*logN)。

其他性能

由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

堆排序是就地排序，辅助空间为O(1）.

它是不稳定的排序方法。

 

7、哈夫曼算法

基本思想：

它是由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树。

因为这种树最早由哈弗曼（Huffman）研究，所以称为哈弗曼树，又叫最优二叉树。

 

哈夫曼树创建用了两种的方法，一种是基于顺序表，另一种是基于最小堆。

 

建立Huffman树的基本思路：

给定有权重的一系列数据（带权重），从中挑选最小权重的两个数据，组成一棵树，得到的父节点再插入到数据系列当中。

 

8、哈夫曼压缩算法

哈夫曼压缩思路

假设一字符串是，“abcabcabcabcabcabcddddddddd”，统计各字符出现的次数如下表。

字符 出现次数

a 6

b 6

c 6

d 9

按照一搬的存储方法，一个字符占用一个字节，那么共花费(6+6+6+9)*sizeof(char) = 27字节，27字节确实不算什么，但是如果是海量数据的时候，就可能要考虑存储空间的问题了。

 

来看看哈夫曼压缩算法是怎么做的，同样是上面的例子，我们试着建立哈夫曼树，出现的次数就当做是权重，出现的次数越多的话，越靠近根节点，那么编码越短，如下图：

 

于是上面的“abcabcabcabcabcabcddddddddd”，就可以转化为“0001,1000,0110,0001,1000,0110,0001,1000,0110,1111,1111,1111,1111,11”，注意这里采用的按位存储的，也就是说0和1都是位，而非char型。那么之前的27字节就被我们转换成了7个字节（7字节不足，不足的话就补零），而这就达到了压缩的效果。

所以总结一下：利用哈夫曼树编码的特点，权重越大越靠近根节点，得到的编码就越短的原理，而如果把字符出现次数作为权重的话，文本当中出现次数最多的字符就被压缩成了很短的编码。

 

//todo

 http://zhu-zhiguo.iteye.com/blog/2148134