常用算法的应用
-
常用算法的应用
1
．
递推算法（常用级数、数列求和、二分法、梯形积分法、穷举法等）；
2
．排序算法（选择法、冒泡法）；
3
．查找算法（顺序查找、折半查找）；
4
．有序数列的插入、删除操作；
5
．初等数论问题求解的有关算法（最大数、最小数、最大公约
数、最小公倍数、素数等）；
6
．矩
阵的处理（生成、交换及基本运算）；
7
．递归算法（阶乘、最大公约数等）；
8
．字符串处理（插入、删除、连接和比较等）
1.
相对于递归算法
,
递推算法免除了数据进出栈的过程，也就是说
,
不需要函数不断的向边界
值靠拢
,
而直接从边界出发
,
直到求出函数值
.
比如阶乘函数：
f(n)=n*f(n-1)
在
f(3
)
的运算过程中
,
递归的数据流动过程
如下
:
f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0
){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}
而递推如下
:
f(0)-->f(1)-->f(2)-->f(3)
由此可见
,
递推的效率要高一些
,
在可能的情况
下应尽量使用递推
.
但是递归作为比较基础
的算法
,
它的作用不能忽视
.
所以
,
在把握这两种算法的时候应该特别注
意
.
2.
所谓排序，就是使一串记录
，按照其中的某个或某些关键字的大小，递增或递减的排列起
来的操作。
分类
在计算机科学所使用的排序算法通常被分类为：
计算的
复杂度（最差、平均、和最好表现），依据串列（
list
）的
大小（
n
）。一般而言，
好的表现是<
/p>
O
。
(n log n)
，且坏的行为是
Ω(n2)
。对於一个排序理想的表现
是
O(n)
。仅使用
一个抽象关键比较
运算的排序算法总平均上总是至少需要
Ω(n log
n)
。
记忆体使用量（以及其他电脑资源的使用）
稳定度
：
稳定排序算法会依照相等的关键（换言之就是值）
维持纪录的
相对次序。也就是
一个排序算法是稳定的，就是当有两个有相等关键的纪录
R
和
S
，且在原本的串列中
R
出
现在
S<
/p>
之前，在排序过的串列中
R
也将会是在<
/p>
S
之前。
一般的方法：插入、交换、选择、
合并等等。交换排序包含冒泡排序（
bubble sort
）
和快
速排序（
quicksort
）。
选择排序包含
shaker
排序和堆排序（
heapsort
）。
当相等的元素是无法分辨的，
比如像是整数，稳定度并不是一个问题。然而，假设以下的
数对将要
以他们的第一个数字来排序。
(4, 1) (3, 1) (3, 7) (5, 6)
在这个状况下，
< br>有可能产生两种不同的结果，
一个是依照相等的键值维持相对的次序，
而
另外一个则没有：
(3, 1) (3, 7)
(4, 1) (5, 6) (
维持次序
)
(3, 7) (3, 1)
(4, 1) (5, 6) (
次序被改变
)
不稳定排序算法可能会在相等的键
值中改变纪录的相对次序，
但是稳定排序算法从来不会
如此。<
/p>
不稳定排序算法可以被特别地时作为稳定。
作这件事情的一个方式
是人工扩充键值的
比较，
如此在其他方面相同键值的两个物件间
之比较，
就会被决定使用在原先资料次序中的
条目，当作一个同
分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。
排序算法列表
在这个表格中，
< br>n
是要被排序的纪录数量以及
k
是不同键值的数量。
稳定的
冒泡排序（
bubble
sort
）
—
O(n2)
鸡尾酒排序
(Cocktail
sort,
双向的冒泡排序
)
—
O(n2)
插入排序
（
insertion
sort
）
—
O(n2)
桶排序
（
bucket
sort
）
—
O(n);
需要
O(k)
额外
记忆体
计数排序
(counting
sort)
—
O(n+k);
需要
O(n+k)
额外
记忆体
归并排序
（
merge
sort
）
—
O(n log
n);
需要
O(n)
额外记忆体
原地归并排序
—
O(n2)
二叉树排序
（
Binary tree
sort
）
—
O(n log n);
需要
O(n)
额外记忆体
鸽巢排序
(Pigeonhole sort)
—
O(n+k);
需要
O(k)
额外记忆体
基数排序
（
radix
sort
）
—
O(n·
k);
需要
O(n)
额外记忆体
Gnome sort
—
O(n2)
Library sort
—
O(n log n) with high probability,
需要
(1+
ε
)n
额外记忆体
不稳定
选择排序
（
selection
sort
）
—
O(n2)
希尔排序
（
shell
sort
）
—
O(n log n)
如果使用最佳的现在版本
Comb sort
—
O(n log n)
堆排序
（
heapsort
）
—
O(n log n)
Smoothsort
—
O(n log n)
快速排序
（
quicksort
）
—
O(n log n)
期望时间
, O(n2)
最坏情况
;
对於大的、乱数串列
一般相信是最快的已知排序
Introsort
—
O(n log n)
Patience
sorting
—
O(n log n + k)
最外情况时间
,
需要
额外的
O(n + k)
空间
,
也需要
找到最长的递增子序列（
longest
increasing subsequence
）
不实用的排序算法
Bogo
排序
—
O(n ×
n!)
期望时间
,
无穷的最坏情况。
Stupid sort
—
O(n3);
递回版本需要
O(n2)
额外记忆体
Bead sort
—
O(n) or O(√n),
但需要特别的硬体
Pancake sorting
—
O(n),
但需要特别的硬体
排序的算法
排序的算法有很多，
对空间的要求及其时间效率也不尽相同。
下面列出了一些常见的排序
算法。
这里面插入排序和冒泡排序又被称作简单排序，
< br>他们对空间的要求不高，
但是时间效
率却不稳定；
而后面三种排序相对于简单排序对空间的要求稍高一点，
但时间效率却
能稳定
在很高的水平。
基数排序是针对关键字在一个较小范围内
的排序算法。
插入排序
冒泡排序
选择排序
快速排序
堆排序
归并排序
基数排序
希尔排序
插入排序
插入排序是这样实现的：
首先新
建一个空列表，用于保存已排序的有序数列（我们称之为
有序列
表
）。
从原数列中取出一个数，将其插入
有序列表
中，
使其仍旧保持有序状态。
重复
2
号步
骤，直至原数列为空。
插入排序的平均时间复杂度为平方级的，效率不高，但是容易
实现。它借助了
逐步扩大
成果
的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。<
/p>
冒泡排序
冒泡排序是这样实现的：
首先将所有待排序的数字放入工作列表中。
从列表
的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，
则将它
与它的下一位交换。
重复
2
号步
骤，直至再也不能交换。
冒泡排序的平均时间复杂度与插入排序相同，
也是平方级的，
但也是非常容易实现的算法。
选择排序
选择排序是这样实现的：
设数组内存放了
< br>n
个待排数字，数组下标从
1
开
始，到
n
结束。
i=1
从数组
的第
i
个元素开始到第
n
个元素，寻找最小的元素。
将上一步找到的最小元素和第
i
位元素交换。
如果
i=
n
－
1
算法结束，否则回到第
3
步
选择排序的平均时间复杂度也是<
/p>
O(n²
)
的。
快速排序
现在开始，
我们要接触高效排序算法
了。
实践证明，
快速排序是所有排序算法中最高效的
一种。
它采用了分治的思想：
先保证列表的前半部
分都小于后半部分，
然后分别对前半部分
和后半部分排序，这样
整个列表就有序了。这是一种先进的思想，
也是它高效的原因。
因为
在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而
保证列表的
前半部分都小于后半部分
就使得前半部分的任何一个数从此以后都不再跟后半部分的数进
行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。
堆排序
堆排序与前面的算法都不同，它是这样的：
首先新
建一个空列表，作用与插入排序中的
有序列表
< br>
相同。
找到数列中最大的数字，将其加在
有序列表
的末
尾，并将其从原数列中删除。
重复
2
号步
骤，直至原数列为空。
堆排序的平均时间复杂度为
nlog
n,
效率高
（因为有堆这种数据结构以及它奇妙的特征，
使
得
找到数列中最大
的数字
这样的操作只需要
O(1)
的时间复杂度，维护需要
logn
的时间复
杂度），但是实现相对复杂（可以说是这里
7
< br>种算法中比较难实现的）。
看起来似乎堆排序与插入排序有些相像，
但他们其实是本质不同的算法。
至少，
他们的时
间复杂度差了一个数量级，一个是平方级的，一个是对数级的。
平均时间复杂度
插入排序
O(n2)
冒泡排序
O(n2)
选择排序
O(n2)
快速排序
O(n log n)
堆排序
O(n log n)
归并排序
O(n log n)
基数排序
O(n)
希尔排序
O(n1.25)
3.
索引查找是在索引表和主表
(
即线性表的索引存储
结构
)
上进行的查找。
索引查找的过程
是：
首先根据给定的索引值
K1
，
在索引表上查找出索引值等于
KI
的索引项
，
以确定对应予表在
主表中的开始位置和长度，然后再根据给定
的关键字
K2
，茬对应的子表中查找出关键字等
于
K2
的元素
(
结点
)
。对索引表或子表进行查找时，若表是顺序存
储的有序表，则既可进行
顺序查找，也可进行二分查找，否则只能进行顺序查找。
设数组
A
是具有
mainlist
< br>类型的一个主表，
数组
B
是具有
inde)dist
类型的在主表
A
上建
立的一个索引表，
m
为索引表
B
的实际长度，即所含的索引项的个数，<
/p>
KI
和
K2
分别
为给
定待查找的索引值和关键字
(
当然
它们的类型应分别为索引表中索引值域的类型和主表中关
键字域在索引存储中，
不仅便于查找单个元素，
而且更便于查找一个子表中的全部元素。
当
需要对一个子袁中的全部元素依次处理时，只要从索引表中查找出该
子表的开始位
< br>置即可。
由此开始位置可以依次取出该子表中的每一个元素，
所以整个查找过程的时间复
杂度为，
若不是采用索引存储，
而是采用顺序存储，
即使把它组织成有序表而进行二分查找
时，索引查找一个子表中的所有元素与二分查找一个子表中的所有元素相比。
若在主表中的每个子表
后都预留有空闲位置，
则索引存储也便于进行插入和删除运算，
因
为其运算过程只涉及到索引表和相应的子表，只需要对相应子表中的元素进行比较和移
动，
与其它任何子表无关，不像顺序表那样需涉及到整个表中的所有元素，即牵一发而动
全身。
在线性表的索引存储结构上进行插入和删除运算的算法，也同查找算法类似，其过程为：
首先根据待插入或删除元素的某个域
(
假定子表就是按照此域的
值划分的
)
的值查找索引表，
确定出对
应的子表，
然后再根据待插入或删除元素的关键字，
在该子表中
做插入或删除元素
的操作。
因为每个子表不是顺序存储，
就是链接存储，
所以对它们做插入或删除操作都是很
< br>简单的。
4.
插入法排序
#define N 10
#include
main()
{ int i,j,k,t,a[N];
clrscr();
printf(
for(i=0;i
scanf(
for(i=1;i
-
-