哈喽,大家好,我是不务正业的吴师兄,今天给大家找点乐子,分享几个好玩的排序算法。
根据CPU的调度算法实现的,对一组数据进行排序,不能存在负数值,这个数是多大,那么就在线程里睡眠它的10倍再加10,不是睡眠和它的数值一样大的原因是,当数值太小时,误差太大,睡眠的时间不比输出的时间少,那么就会存在不正确的输出结果。
随机打乱数组,检查是否排好序,若是,则输出,否则再次打乱,再检查…最佳情况O(n),平均O(n*n!),最坏可执行直到世界的尽头。
一个有趣的理论:一只猴子随机敲打打字机键盘,如果时间足够长,总是能打出特定的文本,比如莎士比亚全集。
首先去买一捆面条,我喜欢手擀面。找到数组中最大和最小的两个数(O(n)),让最大的数对应一根很长的面条,最小的数对应一根很短的面条。
重新遍历数组,每遇到一个数,就取一根面条,把它切成这个数对应的长度,可以得到n根面条。这里的数与面条长度的对应可以用一个严格递增的函数来映射。
接下来,一手握住这n根面条,稍微用力,别握太紧,在平放的桌面上直立着放下,让所有的面条底端接触到桌面。另一只手平行于桌面,从面条上方缓慢往下移动,每当这只手碰到一根面条,移走它,并把对应的数输出到结果数组中,直到移走全部面条。
鸡尾酒排序,也就是定向冒泡排序,鸡尾酒搅拌排序,搅拌排序(也可以视作选择排序的一种变形),涟漪排序,来回排序或快乐小时排序,是冒泡排序的一种变形。
此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
排序过程:
在这一轮操作中,没有元素位置交换,证明已经有序,排序结束。
对比冒泡排序,鸡尾酒排序只需要 3 轮操作就可以完成排序。
“Gnome 排序(地精排序),起初由 Hamid Sarbazi-Azad 于 2000 年提出,并被称为 stupid 排序,后来被 Dick Grune 描述并命名为 “地精排序” 。 ”
地精排序和插入排序类似,除了移动一个元素到最终的位置,是通过交换一系列的元素实现,就像冒泡排序一样。概念上十分简单,不需要嵌套循环。
时间复杂度为O(n^2),但是如果初始数列基本有序,时间复杂度将降为O(n)。实际上 Gnome 算法可以和插入排序算法一样快。
平均运行时间为O(n^2)。
将无序数列:6,2,4,1,5,使用地精排序使其从小到大排序。
通过设计标识 i = 0 ,然后从头开始判断,什么时候 ( i < 4 ) 不成立,什么时候排序结束。
这里的核心点就是如何控制 i 的值。
先让 i 自增 1 ,达到值为 1 才开始比较 :
交换前 [ 6 2 4 1 ] 『 i = 0 』
交换后 [ 6 2 4 1 ] 『 i = 1 』
比较 6 和 2 ,发生交换,只要发生交换 i 就减 1 。
交换前 [ 6 2 4 1 ]『 i = 1 』
交换后 [ 2 6 4 1 ]『 i = 0 』
i 变成 0 了,啥也不干,自增变成 1 再说。
交换前 [ 2 6 4 1 ]『 i = 0 』
交换后 [ 2 6 4 1 ]『 i = 1 』
比较 2 和 6 ,不交换,只要不要换就自增 1。
交换前 [ 2 6 4 1 ]『 i = 1 』
交换后 [ 2 6 4 1 ]『 i = 2 』
比较 6 和 4 ,发生交换,只要发生交换 i 就减 1 。
交换前 [ 2 6 4 1 ]『 i = 2 』
交换后 [ 2 4 6 1 ]『 i = 1 』
比较 2 和 4 ,不交换,只要不要换就自增 1 。
交换前 [ 2 6 4 1 ]『 i = 1 』
交换后 [ 2 4 6 1 ]『 i = 2 』
比较 4 和 6 ,不交换,只要不要换就自增 1 。
交换前 [ 2 4 6 1 ]『 i = 2 』
交换后 [ 2 4 6 1 ]『 i = 3 』
比较 6 和 1 ,发生交换,只要发生交换 i 就减 1 。
交换前 [ 2 4 6 1 ]『 i = 3 』
交换后 [ 2 4 1 6 ]『 i = 2 』
比较 4 和 1 ,发生交换,只要发生交换 i 就减 1 。
交换前 [ 2 4 1 6 ]『 i = 2 』
交换后 [ 2 1 4 6 ]『 i = 1 』
比较 2 和 1 ,发生交换,只要发生交换 i 就减 1 。
交换前 [ 2 1 4 6 ]『 i = 1 』
交换后 [ 1 2 4 6 ]『 i = 0 』
啥也不干,先让 i 自增1,达到值为 1 才开始真正的比较。
『 i = 1 』时,比较 1 和 2 ,不交换,只要不交换就自增 1 。 『 i = 2 』时,比较 2 和 4 ,不交换,只要不交换就自增 1 。 『 i = 3 』时,比较 4 和 6 ,不交换,只要不交换就自增 1 。 『 i = 4 』时,表达式 ( i < n ) 不成立,排序结束。
顺序输出为 [ 1 2 4 6 ]。
你学会了么。