以图明志

计算机算法

[专题] 快速排序里的学问:枢纽元选择与算法效率

枢纽元选择也有学问
通常的、没有经过充分考虑的选择是将第一个或最后一个元素用作枢纽元。如果输入是随机的,那么这是可以接受的,但是如果输入是预排序的或者是反序的,那么这样的枢纽元就产生一个劣质的分割,因为所有的元素不是被划入S1就是被划入S2。更有甚者,这种情况发生在所有的递归调用中。

计算机算法

平方根sqrt()函数的底层算法效率

数学在程序设计中是非常有用的
虽然有可能你平时没有想过这个问题,不过正所谓是“临阵磨枪,不快也光”,你“眉头一皱,计上心来”,这个不是太简单了嘛,用二分的方法,在一个区间中,每次拿中间数的平方来试验,如果大了,就再试左区间的中间数;如果小了,就再拿右区间的中间数来试。比如求sqrt(16)的结果,你先试(0+16)/2=8,8*8=64,64比16大,然后就向左移,试(0+8)/2=4,4*4=16刚好。
1 / 1 首页 < Prev 1 Next > 尾页 页码: