算法与数据结构是计算机专业学生的必修课,基础中的基础,所以快速上手,找到学习方向和感觉十分重要。我在学习过程中遇到一本好书,《我的第一本算法书》,把算法讲得很浅显易懂,所以基于这本书的内容,提炼出其中的精华,再加上个人的理解,旨在把最干的干货分享给大家。推荐大家去阅读原书!
排序
由于排序是一个比较基础的问题,所以排序算法的种类也比较多。
冒泡排序
从序列右边开始比较相邻两个数字的大小,再根据结果交换两个数字的位置。数字会像泡泡一样,慢慢从右往左“浮”到序列的顶端。
选择排序
从待排序的数据中寻找最小值,将其与序列最左边的数字进行交换。
插入排序
从序列左端开始依次对数据进行排序的算法。在排序过程中,左侧的数据陆续归位,而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出一个数据,然后将它插入到已排序区域内合适的位置上。 跟冒泡没什么区别,每次从右边取值后就弄一次冒泡。
堆排序
堆排序的特点是利用了数据结构中的堆。首先,在堆中存储所有的数据,并按降序来构建堆。所有数据都存进堆里了。为了排序,需要再从堆中把数据一个个取出来。每次取数只取堆顶(当前最大值),将数放至数组的末尾,然后重新构造堆,再取堆顶,放数至数组末尾前面,不断重复直到数组填满。
归并排序
归并排序算法会把序列分成长度相同的两个子序列,当无法继续往下分时(也就是每个子序列中只有一个数据时),就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行,直到所有子序列都归并为一个整体为止。
有点小复杂,不过看图秒懂,重点就是每次比较序列的首位数字。
快速排序
快速排序算法首先会在序列中随机选择一个基准值(pivot),然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别,再将其排列成以下形式。
接着,对两个“[ ]”中的数据进行排序之后,整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序。
数组的查找
线性查找
线性查找的操作很简单,只要在数组中从头开始依次往下查找即可。
二分查找
二分查找也是一种在数组中查找数据的算法。和线性查找不同,它只能查找已经排好序的数据。二分查找通过比较数组中间的数据与目标数据的大小,可以得知目标数据是在数组的左边还是右边。因此,比较一次就可以把查找范围缩小一半。重复执行该操作就可以找到目标数据,或得出目标数据不存在的结论。 就是人们脑里猜数经常用的方法。
上一篇 ! 下一篇 !加油!