计算机科学导论---算法


算法:它是一组明确步骤的有序集合,它能产生结果,并在有限的时间内终止。


计算机科学中,最普遍的应用是排序,即根据数据的值对它们进行顺序排列。 这里介绍三种最基础的排序算法:选择、冒泡、插入。它们也是其他排序算法的基础。数据列表可看成两个子列表(已排序和未排序),它们通过假想的墙分开。

选择排序:每一轮排序,从未排序的列表中寻找最小的元素,与未排序列表的第一个元素交换,然后已排序列表长度加一,即:每一轮最小值追加到了已排序列表最后。


冒泡排序:每一轮排序,从未排序列表中寻找最小元素排追加到已排序列表后面。即:第一轮找第一小的,第二轮找第二小的,依此类推。


插入排序:每一轮排序,从未排序列表中的元素,在已排序列表中寻找适当位置,插入进去。就好比打牌,每拿到一张牌,就和手中的所有牌一一对比,然后插入到相应位置。

其他排序:其他更高效的排序算法都以上述排序法为基础,如:快速排序、堆排序、shell 排序、桶式排序、合并排序、基排序等。之所以有这么多排序算法,是因为有的算法对部分已排序的数据很有效,而另一种算法对完全未排序的数据很有效。要选择适合的算法,就需要通过算法复杂度去衡量。


查找:在列表中确定目标所在位置的算法叫作查找。

顺序查找:通过对列表元素一一比对,确定查找元素所在位置,通常用在无序列表的查找元素。


折半查找:用于在有序列表查找元素。折半查找是从列表的中间开始查找的,然后判断出目标在列表前半部分还是分半部分,这样每一轮就可以缩小一半的查找范围。重复 这个过程,直到找到目标为止。


子算法:结构化编程的原则要求将算法拆分成几个单元,称为子算法。例入选择排序法,在未排序的列表中寻找最小值就可以当作一个独立的任务,它能被看一个子算法。使用子算法的优点是使程序更容易理解和子算法可被复用。

迭代:如果算法的定义不涉及算法本身,则算法是迭代的。

递归:每一个算法出在它本身的定义中。主要思想是先将问题从高至低进行分解,然后从低到高逐级解决。

原文地址:https://www.cnblogs.com/zbseoag/p/10884086.html