科学的研究方法(摘录至文明之光一书)
- 不盲从,不接受任何自己不清楚的真理。不管有什么权威的结论,只要没有经过自己的研究,都可以怀疑。
- 对于复杂的问题,尽量分解为多个简单的小问题来研究,一个一个地分开解决。
- 解决这些小问题时,应该按照先易后难的次序,逐步解决。
- 解决每个小问题之后,再综合起来。看看是否彻底解决了原来的问题。
内存溢出和内存泄露
内存溢出
内存溢出主要是指,要装的数据要超过容器本身了,这是则会导致溢出。类似与生活中的水桶、杯子等,容量是有限的,所以不能进行无限的填装。像Java中的OOM,就属于内存溢出。因为Java中GC的存在,所以并不会发生内存泄露。
内存泄露
上一章用到C语言制造链表,对于链表中结点的删除操作,会有一个free()函数的调用。free()函数的作用是释放内存空间。所谓的释放内存空间,是指把对内存地址的操作权限移交给操作系统。如果没有做free()这个操作,删除该结点时,会导致该结点在已经无法找到了,但却还拥有控制权限。操作系统在分配内存时,会认为当前内存地址有人还在使用,就不会分配给其他的应用程序,从而会导致内存空间,越用越少。
排序
排序的稳定性
所谓稳定性是指,如果序列中两个数据元素相等,即r[i]==r[j],排序前r[i]在r[j]前,排序后r[i]仍然在r[j]前,则这个排序算法是稳定的,反之是不稳定的。
选择排序
其基本思想是从待排序的无序区中找出最小的元素,将该元素与该区中的第一个元素交换位置。该排序算法是不稳定的。
插入排序
其核心思想是把待排序区中的第一个元素拿出来,把位置给空出来。然后用该元素,跟有序区中的元素进行比较。假设是从小到大排序,则比该元素大的,往后移动一次。依次进行即可。把该元素插入到不能移动的元素后边的空间中。该排序算法是稳定的。
冒泡排序
其基本思想是通过相邻元素之间的比较和交换,来完成排序。有向上冒泡和向下下沉。该排序算法是稳定的。
希尔排序
其核心思想是对数据进行分组,然后再对分组后的数据进行插入排序算法。该排序算法是不稳定的。
快速排序
其基本思想是从待排序序列中找一个基准数,以基准数进行左右分区,其中一部分的所有数据都比另外一部分所以数据小,基准数排在两个分区序列中间。然后再按此方法对这两部分数据分别进行快速排序,递归进行,达到变成有序序列。该排序算法是不稳定的。
归并排序
其基本思想是使用辅助空间,首先是对待排序序列进行拆分,以递归的方式,拆成只剩下一个的时候,再两两进行归并操作,按指定的条件进行排序。再执行最后一次归并时,如果最后一次比较后,某个序列中有多余的元素,会直接插入到辅助空间后面。
查找
二分查找法
二分查找又称折半查找,效率较高,但有限制条件。只能对线性表的顺序存储结构并且元素有序进行查找。可采用递归、非递归方式。
二叉排序树
又称二叉查找树,其特点是如果右子树非空,右子树上所有结点的值均大于根节点的值。如果左子树非空,左子树上所有结点的值均小于根结点的值。左右子树又各是一棵二叉排序树。中序遍历即可获得一个有序序列。Java中的TreeSet,其实就是一个二叉排序树,根据左小右大来放置元素。
其他代码实现
顺序栈
|
|
进制转换
借助栈空间,根据基数对原数取余数,把取到余数入栈,再对原数取整,循环该过程,直到取整的数为0时停止。最后再栈内元素全部出栈。
判断回文数
回文的特点是:倒着写跟原来是一样的。代码的实现,用了三种方式。
第一种是判断非负整数是否是个回文数。采用的方式,是把原来的数值给回转过来,再跟原数值进行一次比较,相等则是回文数。
第二种是采用栈,对数值的长度进行劈叉,把前一半的数值一次入栈。然后再进行出栈,并与后一半数值进行比较,都相等则是回文数。该方式有一个BUG,当长度是奇数时,前一半数据的长度跟后一半数据的长度并不相等,会导致12321这种类型的数据,判断出来不是回文数。
第三种是获取数据的字节数组,采用头指针跟尾指针,每循环一次,拿头指针上的数据与尾指针上的数据进行比较,相等则头指针往前挪一位,尾指针往后挪一位。直到头指针小于等与尾指针,循环结束。