电脑入门基础知识( 六 )


计算机入门必备算法——快速排序法
1.引言今天的运气不是很好 , 再加上项目的压力 。准备停止学习一周 , 等把项目这一关过了 , 再继续深入学习分享算法 。后来吧今天遇到的事情都比较郁闷 , 也无心情继续开发项目 。便想转移一下注意力 , 继续学习快速排序算法的内容 。
昨天了解了递归的使用原理 。今天可以使用这个新技能来解决一个新的问题————快速排序 。快速排序是一种排序算法 , 这个算法比前天学习的选择排序要快得多 , 实属优雅代码的典范 。

2.快速排序2.1 学习准备这里讲解一个比较著名的递归式问题解决方法————分而治之(divide andcomquer , D&C) 。为了方便理解 , 还是使用一个示例给大家讲解一下这是个什么样的使用原理 。给定一个数字数组arr=[2,4,6],我们可以将这些数字相加并返回结果 , 使用循环其实可以很容易得出结论(具体代码可以自行来敲哦!可以粘到留言板我帮你检查哦~),那么如何使用递归函数解决这个需求呢?这里给出一种思路实现:
1.找出基线条件我们首先考虑最简单的数组是什么样的?一种是空数组或者数组中只有一个元素 , 这完全可以直接计算出来 , 结果要么就是null或者就是这个元素的值 。
计算总和非常容易 , 这就是我们需要找的基线条件(不明白基线条件可以看昨天的文章哦) 。
2.缩小数组我们需要算出这个数组的和 , 其实可以表示为sum([2,4,6]),那么如何缩小数组的规模呢?那么sum([2,4,6])=2+sum([4,6]) = 2+ 4 + sum([6])(达到基线条件) = 2+4+6=1
2.?
3.函数的运行过程下图解释了函数是如何运行的 , 递归保存了运行的状态!2.2 快速排序的原理使用快速排序算法对数组进行排序 , 首先考虑对于排序算法而言 , 最简单的数组上面介绍要么是空数组或者只有一个元素的数组 。因此基线条件为空或者只包含一个元素 。
在这种情况 , 可以直接返回该数组 。我们再在数组里加一个元素 , 两个元素应该如何排序呢?思路也很简单 , 如果从小到大排序 , 就需要将这两个元素进行比较 , 如果前一个比较小 , 直接返回;如果前一个比较大 , 就需要互相交换 , 然后返回数组 。那么包含三个元素或者更长的数组应该怎么排序呢?此时我们可以考虑分而治之算法 , 将数组进行分解 , 直到满足基线条件 。
第一步 , 从数组中选择一个基准值 , 理论上这个基准值是可以随意挑选的 , 你可以选择数组首项也可以选择中项甚至可选择尾项 。(有什么区别在后面讲)我们暂时先将数组中的第一个值用作基准值 , 接下来 , 我们需要找出比基准值大的和小的元素 , 这被称为"分区" , 这样操作之后 , 你会有一个比基准值小的数字组成的子数组、基准值、一个比基准值大的数字组成的子数组 。但是这里只是进行了分区 , 但这个分区数组并不一定就是有序的 。但是我们三项的数组就可以在选出一个基准值的情况下 , 然后对后面的数组(只含有两项)进行排序(这个很容易) , 这样我们也得到了有序数组 , 那么四项数组、五项数组甚至更多项呢?2.2 代码实现书上使用的python代码 , 我将其翻译为java语言 , 快速排序算法利用python语言是很好实现的 , 但是java实现起来还是比较麻烦的 。
通过网上查阅 , 先将编译好的java代码进行展现 。2.3 运行时间快速排序的运行时间在于你选择的基准值 。假设你一直都选择第一个元素作为基准值 , 且要处理的数组是有序的 。
快速排序不检查数组元素的顺序 , 因此还是会尝试对其排序 , 但是这会有一个问题 , 每次选择第一个作为基准值 , 导致比基准值小的数组都是空的 , 使得调用栈非常高 。运行时间较长 。栈长表示为O(n) 。那有没有更好的办法呢?有的 , 我们可以参考二分查找的实现方法 , 每次选择中间的元素作为基准值 , 就会发现调用栈被减短了许多? 。
新手学电脑的基本知识

电脑入门基础知识

文章插图
新手学电脑的基本知识:要想入门 , 以下五个基础知识是必不可少的 , 他们分别是键盘的认识、鼠标的使用、硬盘图标的认识、桌面图标的认识和输入法的使用 。基础知识一:键盘的认识 , 二十六个按键键盘是电脑主要的输入工具 , 学电脑可以先从认识二十六个英文字母的布局开始 , 可以通过键盘字母游戏进行熟悉 。