hi,少年。咱们来一起学习算法啦。这套课程特别适合自学算法的小白。每节课程最后还有一道练习题,边学边练,可以帮你及时巩固学习到的知识。
您也可以在该网站免费学习到更多课程
好,那我们正式开始!算法,可以简单理解为,完成一个任务的方法。你可以把它想象成食谱。要想做出一道菜肴,只需要按食谱的步骤一步步操作。
编程中的算法,就是用计算机解决一个问题的方法。食谱和算法的最大区别,在于算法是严密的,只要遵循步骤就一定能解决特定的问题;而食谱经常会有模糊描述的部分,不同厨师按照一个食谱做出来的菜可能口味天差地别。
算法也有优劣之分,如果让你在图书馆找到一本书算法一:在图书馆乱逛,随便抓起一本书看是不是要找的,如果不是,就再逛到另一个地方,随便抓起一本书算法二:从图书馆的第一排书架最顶层开始,从左到右,一本本地找。找完一层,再找下一层。如果整个书架找完了,就到下一个书架,再这样找。算法三:根据图书的索引编号,到图书馆的特定区域(如文学区、科技区),找到编号对应的书架、在哪一层,然后从左到右一本本找到。
代码实现
好,接下来我们做一道练习题,请移步到该网站的《算法基础简介》课程中,习题在内容最后。
说说冒泡排序(英语:Bubblesort),它是一种简单的排序算法。由于在算法的执行过程中,较小的元素像是气泡般慢慢「浮」到数列的顶端,故叫做冒泡排序。
如图所示是对无序表的第一次冒泡排序,最终将无序表中的最大值97找到并存储在表的最后一个位置,第一次冒泡结束;由于97已经判断为最大值,所以第二次冒泡排序时就需要找出除97之外的无序表中的最大值,比较过程和第一次完全相同。
经过第二次冒泡,最终找到了除97之外的又一个最大值76,比较过程完全一样,这里不再描述。通过一趟趟的比较,一个个的“最大值”被找到并移动到相应位置,直到检测到表中数据已经有序,或者比较次数等同于表中含有记录的个数,排序结束,这就是冒泡排序。具体实现代码为:
假设我们现在对“61279345108”这10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,这就是一个用来参照的数,待会儿你就知道它用来做啥了)。为了方便,就让第一个数6作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放在6的右边,比基准数小的数放在6的左边,类似下面这种排列:31254697108在初始状态下,数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置,假设这个位置是k。现在就需要寻找这个k,并且以第k位为分界点,左边的数都小干等于右边的数都大于等于6。
分别从初始序列“61279345108"两端开始“探测"、先从右往左我一个小于6的数,再从左往右找一个大干6的教,然后交换它们。这里可以用两个变量i和j,分别指向最左和最右边。具体的流程请参考:
现在基准数6已经归位,它正好处在序列的第6位。此时我们已经将原来的序列,以6为分界点拆分成了两个序列,左边的序列是“31254”,右边的序列是“97108”,接下来还需要分别处理这两个序列,因为6左边和右边的序列目前都还是很混乱的。不过不要紧,我们已经掌握了方法,接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列吧。左边的序列是“31254”。请将这个序列以3为基准数进行调整,使得3左边的数都小于等于3,右边的数都大于等于3。
最后你来将选择排序的关键代码补全,请移步到该网站的《排序算法》课程中,习题在内容最后。
好,我们这次先讲到这里,请进入作者主页继续学习后续的算法课程。或进入上面的地址免费学习完整的算法课程。