【导读】:如果有人问你哪种排序算法最奇怪,可能你会先在冒泡排序、选择排序、快速排序等常见排序算法中「搜索」了。
有人在Quora上也发帖问了这个问题。于是乎,各种脑洞大开的奇特算法就被列出来了。它们可能存在性能问题或无法实现,但是不可否认其创造性。
睡眠排序(Nipun Ramakrishnan 的回答)
这个搞笑算法流传于 4chan 的 /prog/ 板块。无从查证具体出自哪位程序员,伪代码如下
procedure printNumber(n)
sleep n seconds
print n
end
for arg in args
run printNumber(arg) in background
end
wait for all processes to finish算法运行如下: 对于数组中每个元素 x,开启一个新程序:
休眠 x 秒
打印 x 所有元素同时开始计时。 只适用于非负数字。
Bogo 排序/猴子排序 (Ryan Turner的回答)
Bogo 排序/猴子排序,名字很奇怪。它是愚蠢排序中的一员。
主要来说,算法就是你把元素随机排列。
如果没有排好序,再次把元素随机排列。
如果还没有排好序,你懂的。下面是个例子:
4, 7, 9, 6, 5, 5, 2, 1 (未排序)
2, 5, 4, 7, 5, 9, 6, 1 (随机排列)
1, 4, 5, 6, 9, 7, 5, 2 (再次随机排列)
1, 2, 4, 5, 5, 6, 7, 9 (天呐,真幸运)你不停地随机排序,直到得到一个有序数组。
毫无疑问这是最低效的排序算法之一,除非你非常非常幸运。它时间复杂度是令人窒息的 O(n!),而且随着元素数量增加,很有 O(∞) 的趋势。
量子 Bogo 排序(Tyler Schroeder 的回答)
我是量子 Bogo 排序的粉丝:
随机排列数组中元素。
如果数组没有排好序,摧毁当前宇宙(这一步就拜托你了)
存活的宇宙将会有排好序的数组。 时间复杂度仅仅 O(n) 注意:这种算法依赖于量子力学的平行宇宙理论的可靠性。如果量子力学的平行宇宙理论不准确,这个算法时间复杂度达不到 O(n)
打印店页码排序 (Yi Wang的回答)
这并不是我发明的,我从别处看到的。
一个学生去打印店打印材料。他需要两份,但并没有直接打印两份,而是将每一页打印了两次,像下面这样:
需要的页码顺序: 1 2 3 4 … N; 1 2 3 4 … N
手上的页码顺序: 1 1 2 2 3 3 4 4 …. N N
他开始对打印材料排序,取一页放在左边,然后取一页放在右边。打印店老板看不下去了,直接把材料拿过来。
老板首先取一页放在左边,然后两页放在右边,再然后两页左边,两页右边…… 排序速度瞬间翻倍 ……
(有网友评论提醒:这是归纳,不是排序)
下面是其他网友的回答:
慢排序
这是一个非常幽默却没什么用的排序算法。它基于“合而不治”的原则(分治算法基本思想“分而治之”的反义词,文字游戏),它由 Andrei Broder 和 Jorge Stolfi 于 1986 年发表在论文《Pessimal Algorithms and Simplexity Analysis(最坏排序和简单性分析)》中,伪代码如下:
function slowSort(array,start,end){
if( start >= end ) return; //已经不能再慢了
middle = floor( (start+end)/2 );
//递归
slowSort(array,start,middle);
slowSort(array,middle+1,end);
//比较得出最大值放在队尾
if( array[end] < array[middle] )
swap array[end] and array[middle]
//去掉最大值之后再排序
slowsort(array,start,end-1);
}递归排序好前一半
递归排序好后一半
比较中间和队尾的值,得到整个数组的最大值,将最大值放到队尾。
去掉最大值,递归整个数组
Stack 排序
从 StackOverflow 上搜索标题含有“数组排序”的帖子,复制粘贴并运行其中的代码片段,直到数组排好序。我认为这种排序算法事实上验证了整个数组。它被发表在xkcd网站上,这里有一个在线版的具体实现stacksort
随机排序
运行如下: 创建一个随机程序。 传入数组并运行随机程序。 如果程序的输出恰好是排好序的,完成。 否则重复上面过程。
太阳能比特翻转排序
太阳发出的阿尔法粒子偶尔能够翻转内存中的比特位,所以这种算法主要基于希望这种翻转能够使元素正确排序。运行方式如下:
检查数组是否排好序。 如果排好序,返回这个数组。 如果没有,等 10 秒钟并祈祷太阳辐射使得比特位翻转,而且使得数组排好序,重复第一步。
意大利面排序
这是一种线性时间算法,是需要 O(n) 空间的稳定排序。它需要并行处理器。简单来说,假设我们排序一列自然数。排序方法需要使用很多根生的意大利面条。
将数据按比例转换成表示意大利面条长度的数字。 在每根面条上写下数字,并将面条折断成数字表示的长度。 把所有面条攥成一捆并把底部在平面上敲击。 取出最突出的一根面条,也就是最长的一根,获取上面的数字,转换成原始的数据并记录下来。 重复这个过程直到处理完所有意大利面。
指鹿为马排序
这个算法时间复杂度 O(n)。 聚集一帮人并向他们展示数组。 询问他们这个数组是否是排序好的。 干掉其中认为没有排序好的人。 重复几次,直到所有人同意这个数组是排序好的。
智能设计排序
无论你的数组状态是什么样的,它都算是排好序的。 解释:原始输入按照某种顺序的概率是 1/(n!)。概率是如此小,(当前的顺序)归结于运气成分显然是荒谬的,所以它是按照“智能设计”排序过的。所以完全可以说数组已经排好序了,只是不是我们传统意义上的“升序”。如果按照我们传统观点对它进行操作,只会让它乱序。(“智能设计”涉及宗教和哲学,不过多解释)
互联网排序
这是一种冒泡排序,但每次比较都依靠互联网的搜索。比如 “0.211 和 0.75 哪个大?”
委员会排序
排序一个包含 N 个自然数的数组,首先用纸打印出 N 份整个数组。 然后在办公室周围选择几个恰好路过的倒霉委员。每个委员对应数组中的一个数字。 给每个委员一份打印的数组,并让他们通过开会或其他手段,来决定自己代表的数字应该在有序数组中的位置。 当这些委员有结论并答复你时,数组自然排好序了。
有序数组是一种特殊的数组,里面的元素,按一定的顺序排列,我们这里假设由小到大排列。
概念
对于这种特殊的数组,我们可以采用前面提到的二分法来查找数组中特定的元素,这种算法的思想是:每查找一次,便将查找的范围缩小一半,所以叫做二分法查找。
有序数组的优点就是增加了查询的效率,但是它并没有提高删除和插入元素的效率,因此,对于有序数组更适合用于查询的领域。
只要是按一定顺序排列的数组,就是有序数组。不一定是从小到大或者从大到小的排列。
没有挤公交来上班过,就不知道生活的压力有多大。
算法的时间复杂度和空间复杂度合称为算法的复杂度。
1.时间复杂度
(1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
(2)时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
时间频度不同,但时间复杂度可能相同。如:T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。
按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
(3)最坏时间复杂度和平均时间复杂度 最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,这就保证了算法的运行时间不会比任何更长。
在最坏情况下的时间复杂度为T(n)=0(n),它表示对于任何输入实例,该算法的运行时间不可能大于0(n)。 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,算法的期望运行时间。
指数阶0(2n),显然,时间复杂度为指数阶0(2n)的算法效率极低,当n值稍大时就无法应用。
(4)求时间复杂度
【1】如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
x=91; y=100;
while(y>0) if(x>100) {x=x-10;y--;} else x++;
解答: T(n)=O(1),
这个程序看起来有点吓人,总共循环运行了1100次,但是我们看到n没有?
没。这段程序的运行是和n无关的,
就算它再循环一万年,我们也不管他,只是一个常数阶的函数
【2】当有若干个循环语句时,算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。
x=1;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x++;
该程序段中频度最大的语句是(5),内循环的执行次数虽然与问题规模n没有直接关系,但是却与外层循环的变量取值有关,而最外层循环的次数直接与n有关,因此可以从内层循环向外层分析语句(5)的执行次数: 则该程序段的时间复杂度为T(n)=O(n3/6+低次项)=O(n3)
【3】算法的时间复杂度不仅仅依赖于问题的规模,还与输入实例的初始状态有关。
在数值A[0..n-1]中查找给定值K的算法大致如下:
i=n-1;
while(i>=0&&(A[i]!=k))
i--;
return i;
此算法中的语句(3)的频度不仅与问题规模n有关,还与输入实例中A的各元素取值及K的取值有关: ①若A中没有与K相等的元素,则语句(3)的频度f(n)=n; ②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。
(5)时间复杂度评价性能
有两个算法A1和A2求解同一问题,时间复杂度分别是T1(n)=100n2,T2(n)=5n3。(1)当输入量n<20时,有T1(n)>T2(n),后者花费的时间较少。(2)随着问题规模n的增大,两个算法的时间开销之比5n3/100n2=n/20亦随着增大。即当问题规模较大时,算法A1比算法A2要有效地多。它们的渐近时间复杂度O(n2)和O(n3)从宏观上评价了这两个算法在时间方面的质量。在算法分析时,往往对算法的时间复杂度和渐近时间复杂度不予区分,而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度,其中的f(n)一般是算法中频度最大的语句频度。
2.空间复杂度
一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度,可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。
(1)固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。
(2)可变空间,这部分空间的主要包括动态分配的空间,以及递归栈所需的空间等。这部分的空间大小与算法有关。
一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)) 其中n为问题的规模,S(n)表示空间复杂度。
PHP 经典算法
怎么在thinkphp的视图模板中把固定的时间戳转为时间格式
用实例化Model类的方法,从数据库里获取出来的时间戳,如何在模板中用正常的时间格式来显示?
1、使用date函数进行转换即可。
2、先在控制器中将时间戳分配给模板:
3、在模板里面:
查询按in排序
thinkphp 如何实现在用in条件查询时,返回结果按in排序。
order()里条件应该怎么写。
php怎么根据数组中其中的一个值排序
php数组按键值排序
说明
array_multisort() 函数对多个数组或多维数组进行排序。
参数中的数组被当成一个表的列并以行来进行排序 - 这类似 SQL 的 ORDER BY 子句的功能。第一个数组是要排序的主要数组。数组中的行(值)比较为相同的话,就会按照下一个输入数组中相应值的大小进行排序,依此类推。
第一个参数是数组,随后的每一个参数可能是数组,也可能是下面的排序顺序标志(排序标志用于更改默认的排列顺序)之一:
随后可以指定排序的类型:
PHP str_ireplace() 函数 php替换字符串替换
注意返回值,返回类型,原变量,新变量
"Hello world!"不变,产生新替换变量,区别上面数组,排序后原数组改变,返回