1.插入排序
基本思想:
在已排序的i条记录中插入一条新记录,得到有序的i+1条记录。
特别提示:可以牺牲数组0的空间来作为插入的中间变量。
改进插入顺序:如果在插入过程中奖顺序查找改为折半查找,那么关键字的比较次数可以减少,记录的移动次数不变。
链式插入排序:不用数组而用链表存储数据,就不需要移动数据而仅仅需要改变链即可以实现
要点:设立哨兵,作为临时存储和判断数组边界之用。
直接插入排序示例:
如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。
2、插入排序—希尔排序
基本思想:
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。
操作方法:
- 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
- 按增量序列个数k,对序列进行k 趟排序;
- 每趟排序,根据对应的增量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、归并排序
基本思想
将两个有序的列表归并成一个有序列表的方法
归并操作
算法描述
6、堆排序
基本思想
堆实质是满足如下性质的完全二叉树,树中任一非叶节点的关键字不大于(或不小于)其左右孩子结点的关键字。
根节点的关键字是堆里所有节点关键字中最小者的堆称为小顶堆; 堆是一种完全二叉树,一般使用数组来实现。
算法分析
平均性能
其他性能
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
相关推荐
数学建模30个常用算法(Python)数学建模30个常用算法(Python)数学建模30个常用算法(Python)数学建模30个常用算法(Python)数学建模30个常用算法(Python)数学建模30个常用算法(Python)数学建模30个常用算法...
模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+...
常用算法 常用算法 常用算法 常用算法 常用算法
嵌入式系统软件设计中的常用算法。第1章介绍常用线性方程组求解算法; 第2章介绍常用代数插值和曲线拟合算法; 第3章介绍常用数值积分算法; 北京航空航天大学出版社第4章介绍常用能谱处理算法; 第5章介绍常用数字滤波...
C常用算法程序集C常用算法程序集C常用算法程序集C常用算法程序集
计算机常用算法 计算机常用算法 计算机常用算法计算机常用算法 计算机常用算法 计算机常用算法
嵌入式系统软件设计中的常用算法(完整版)
下篇为算法程序篇, 主要讲述以下方面常用算法的 MATLAB 实现,包括插值、函数逼近、矩阵特征值计算、数值微分、数值积分、方程求根、非线性方程组求解、解线性方程组的直接法、解线性方程组的迭代法、随机数生成、...
资源名称:Java常用算法手册内容简介:现代的设计任务大多通过计算机编程来完成,而算法起到了至关重要的作用。可以毫不夸张地说,算法是一切程序设计的灵魂和基础。选择合理的算法,可以起到事半功倍的效果。 赵...
VB常用算法大全:VB常用算法大全VB常用算法大全:VB常用算法大全
杨克昌 计算机常用算法与程序设计教程杨克昌 计算机常用算法与程序设计教程杨克昌 计算机常用算法与程序设计教程杨克昌 计算机常用算法与程序设计教程
常用算法及例题常用算法及例题常用算法及例题
VB常用算法大全 VB常用算法大全 VB常用算法大全
C++常用算法关于数据存储经典编程算法实例
Matlab常用算法大集合: Floyd算法.rar 免疫算法.rar 分治算法.rar 动态规划.rar 图论.rar 学习路线.png 搜索算法.rar 概率算法.rar 模拟退火算法.rar 灰色预测.rar 穷举法求解0-1整数规划的matlab程序.rar 类比法....
常用算法程序集第6版
C常用算法程序集-徐士良著,第6章,包括c文件和dat文件
C常用算法集(都是比较经典的算法 chm)
常用算法程序集-徐士良 常用算法程序集-徐士良 常用算法程序集-徐士良 常用算法程序集-徐士良 常用算法程序集-徐士良