真空中的
球形算法很棒。 但是,让我们从天堂降落到罪恶的大地,看看所有这些理论上的美将如何在实践中证明自己。
对下一类排序的分析将以对类排序的测试结束。 今天,我们将进行排序交换(不是从扔掉的意义上说,而是从测试的意义上说)。 其他种类的类将稍后运行。
在今天的比赛中:
最弱的群体
由于降低了时间复杂度,这些算法没有任何要求。 我们仅对其进行测试以供参考。
愚蠢的排序
排序缓慢
哑分类
更有趣的是,不仅它们有多出色,而且在业务上有多糟糕,其中哪一个最差。
主要组
在这里,交换交换排序为la O(
n 2 )。 矮小排序(及其优化)+气泡排序的各种变体。
矮人排序
矮人分类(优化)
气泡排序
鸡尾酒分选
奇偶排序
这是当今测量中最有趣的部分。 在主要团体的代表中,最顽固的斗争有望发生。
最强的群体
气泡的一种变化-通过梳子进行分类-克服了障碍O(
n 2 )并达到了历史悠久的O(
n log n )。 因此,在我们的竞争中,快速分类是一个值得竞争的对手。 另外,尝试一下
新发明的k-sort ,它是快速排序的一种变体。
整理梳子
快速分类
K排序
顺便说一句,最强者不仅可以相互媲美。 在某些数据集上,主要群体将处于激烈的竞争之中。
源代码
Python交换排序def stooge_rec(data, i = 0, j = None): if j is None: j = len(data) - 1 if data[j] < data[i]: data[i], data[j] = data[j], data[i] if j - i > 1: t = (j - i + 1) // 3 stooge_rec(data, i, j - t) stooge_rec(data, i + t, j) stooge_rec(data, i, j - t) return data def stooge(data): return stooge_rec(data, 0, len(data) - 1) def slow_rec(data, i, j): if i >= j: return data m = (i + j) // 2 slow_rec(data, i, m) slow_rec(data, m + 1, j) if data[m] > data[j]: data[m], data[j] = data[j], data[m] slow_rec(data, i, j - 1) return data def slow(data): return slow_rec(data, 0, len(data) - 1) def stupid(data): i, size = 1, len(data) while i < size: if data[i - 1] > data[i]: data[i - 1], data[i] = data[i], data[i - 1] i = 1 else: i += 1 return data def gnome(data): i, size = 1, len(data) while i < size: if data[i - 1] <= data[i]: i += 1 else: data[i - 1], data[i] = data[i], data[i - 1] if i > 1: i -= 1 return data def gnome_opt(data): i, j, size = 1, 2, len(data) while i < size: if data[i - 1] <= data[i]: i, j = j, j + 1 else: data[i - 1], data[i] = data[i], data[i - 1] i -= 1 if i == 0: i, j = j, j + 1 return data def bubble(data): changed = True while changed: changed = False for i in range(len(data) - 1): if data[i] > data[i+1]: data[i], data[i+1] = data[i+1], data[i] changed = True return data def shaker(data): up = range(len(data) - 1) while True: for indices in (up, reversed(up)): swapped = False for i in indices: if data[i] > data[i+1]: data[i], data[i+1] = data[i+1], data[i] swapped = True if not swapped: return data def odd_even(data): n = len(data) isSorted = 0 while isSorted == 0: isSorted = 1 for i in range(1, n - 1, 2): if data[i] > data[i + 1]: data[i], data[i + 1] = data[i + 1], data[i] isSorted = 0 for i in range(0, n - 1, 2): if data[i] > data[i + 1]: data[i], data[i + 1] = data[i + 1], data[i] isSorted = 0 return data def comb(data): gap = len(data) swaps = True while gap > 1 or swaps: gap = max(1, int(gap / 1.25))
时间
时间无处不在,以秒为单位,精确到微秒。
如果将一包数组(十个,一百个甚至一百万个数组中的一个)立即送入算法,则表明总时间。
铁是我忠实的旧笔记本电脑,它拥有更好的时代。 因此,很可能一切都会为您更快地工作。
最坏的
立即与局外人打交道。 为此,准备了40/50/60个元素的数组,这些数组包含从0到9的随机数。
| 类型=随机,唯一= False,最小值= 0,最大值= 9,计数= 1 |
---|
大小 |
---|
40 | 50 | 60 |
---|
巨蟒 | p | 巨蟒 | p | 巨蟒 | p |
---|
| 0.004 | 0.001 | 0.005 | 0.003 | 0.007 | 0.004 |
---|
| 0.007 | 0.009 | 0.018 | 0.009 | 0.018 | 0.023 |
---|
| 0.02 | 8.26647 | 0.053 | 20.8722 | 0.12901 | 45.9786 |
---|
愚蠢的排序比愚蠢的排序快一个数量级,而愚蠢的排序比笨拙的排序快一个数量级。 没有什么可看的了。
中农
为了检查平均值,生成了每100个元素的一百个数组的包(从100到999的唯一数),以及每个1000个元素的十个数组的包(从1000到9999的唯一数)。
准备随机数组,几乎排序的数组和反向排序的数组。
中量级:随机
| 类型=随机,唯一=真 |
---|
大小(最小到最大) ×计数 |
---|
100 (100至999) ×100 | 1000 (1000至9999) ×10 |
---|
巨蟒 | p | 巨蟒 | p |
---|
| 0.14101 | 0.18901 | 1.59109 | 1.7251 |
---|
| 0.20601 | 0.22301 | 2.33013 | 2.09712 |
---|
| 0.15301 | 0.22901 | 1.6711 | 2.23613 |
---|
| 0.21601 | 0.26402 | 2.55515 | 2.73116 |
---|
| 0.16701 | 0.33402 | 1.7251 | 3.13218 |
---|
所有人都得到相同的结果。 Python实现比PHP快一点。
中线:几乎排序
| 类型=几乎,唯一=真 |
---|
大小(最小到最大) ×计数 |
---|
100 (100至999) ×100 | 1000 (1000至9999) ×10 |
---|
巨蟒 | p | 巨蟒 | p |
---|
| 0.009 | 0.005 | 0.009 | 0.005 |
---|
| 0.009 | 0.014 | 0.01 | 0.014 |
---|
| 0.01 | 0.01 | 0.011 | 0.008 |
---|
| 0.011 | 0.008 | 0.013 | 0.008 |
---|
| 0.011 | 0.017 | 0.013 | 0.017 |
---|
都具有相同的结果,正负。 有趣的是:数十次部分数据排序提高了所有算法的性能。
中:反转
| 类型=反向,唯一=真 |
---|
大小(最小到最大) ×计数 |
---|
100 (100至999) ×100 | 1000 (1000至9999) ×10 |
---|
巨蟒 | p | 巨蟒 | p |
---|
| 0.26801 | 0.35902 | 3.10018 | 3.4292 |
---|
| 0.39602 | 0.45303 | 4.49726 | 4.19524 |
---|
| 0.22701 | 0.38402 | 2.48114 | 3.64421 |
---|
| 0.30202 | 0.42603 | 3.34419 | 4.17524 |
---|
| 0.30402 | 0.64404 | 3.36519 | 6.22036 |
---|
有一个有趣的结论-逆序对速度的影响不大,与随机数相比,速度仅下降2倍。
中:二进制
| 类型=随机,唯一= False,最小值= 0,最大值= 1 |
---|
尺寸×计数 |
---|
100×100 | 1000×10 |
---|
巨蟒 | p | 巨蟒 | p |
---|
| 0.073 | 0.094 | 0.81105 | 0.86905 |
---|
| 0.10401 | 0.11301 | 1.16307 | 1.06606 |
---|
| 0.08801 | 0.12901 | 0.86405 | 1.18207 |
---|
| 0.11501 | 0.15001 | 1.30107 | 1.41608 |
---|
| 0.11401 | 0.25801 | 1.31908 | 2.46314 |
---|
从某种程度上讲,有趣的是:如果您对零和一进行排序而不是从100到9999的数字,那么速度指示器的增长不会太大。
冠军
这里最吸引人的地方是用梳子和k-sort排序是否可以从基座上快速挤出?
冠军:随机
为了找出答案,让我们形成随机数组的包:10个1万个元素和10个10万个元素。 我想让百万富翁使用输入算法,但笔记本电脑没有拉动。 如果没有足够的RAM,则递归深度太大。
| 类型=随机,唯一= False,计数= 10 |
---|
大小(最小到最大) |
---|
10000 (从10000到99999) | 100000 (从100000到999999) |
---|
巨蟒 | p | 巨蟒 | p |
---|
| 0.80205 | 0.63104 | 10.4506 | 8.24647 |
---|
| 0.47703 | 1.64009 | 6.65138 | 26.5435 |
---|
| 0.90005 | 2.18613 | 15.8089 | 29.4867 |
---|
Python K排序较慢,而PHP则比快速排序快。
尽管与所有数据集相比,在所有测试中(以及在这些测试及后续测试中)它都不如快速梳子,但与快速梳子相比,梳理梳理看起来很可靠。
但是,有梳子和重要的无可争辩的优势。 它没有递归,因此与同事不同,它可以成功处理数百万个元素的数组。
特殊情况
尽管冠军比普通农民快数百倍,但在某些特定的数据集上,排序更简单地显示出他们不容易缝制。
特殊情况:几乎已分类
让我们尝试几乎排序的数组,其大小要比对普通农民测试的数组大。
一个由10个数组组成的包,每个数组1万个,由10个数组组成的包,每个数组10万个元素。
| 类型=几乎,唯一= False |
---|
大小(最小到最大) ×计数 |
---|
10000 (从10000到99999) ×10 | 100000 (从100000到999999) ×10 |
---|
巨蟒 | p | 巨蟒 | p |
---|
| 0.43202 | 0.058 | 0.81705 | 0.58003 |
---|
| 0.084 | 0.062 | 0.85805 | 0.54003 |
---|
| 0.11601 | 0.12401 | 1.41908 | 1.36008 |
---|
| 0.14001 | 0.11901 | 1.83411 | 1.41708 |
---|
| 0.13801 | 0.23101 | 1.6491 | 2.56915 |
---|
| ? | 122.088 | ? | ? |
---|
| 0.71504 | 1.58909 | 9.78356 | 19.4731 |
---|
这里根本不提供快速排序-没有足够的RAM。 同时,具有快速爆炸功能的quicksort会处理10/10万个元素的随机数组。 k-sort遇到了类似的问题,在PHP中只有千分之一。 大型的几乎已排序的数组是快速排序及其修改的简并案例。 由于元素的这种排列方式,递归将数组几乎对每对相邻元素划分为多个部分,这导致递归调用的最大数量。
顺便说一下,大型逆序数组的情况也是如此。 出现与几乎有序问题相同的问题-算法必须为每对相邻元素调用自身。
用梳子排序,虽然它的速度比快速或k慢一半到两倍到两倍(通常),但是它没有上述内存溢出。 没有递归-没问题。
好吧,我们注意到,所有中农以几乎几乎全部的排列超过了冠军。 然后,该原则起作用了:“安静地进行-您将继续。”
特殊情况:数百万小阵列的猩红色玫瑰
小数组-中农的元素。 如果需要处理大量的小数字集,则可以通过采用“原始”气泡或gnome排序来节省时间。 并对大型任务使用快速排序等。
| 类型=随机,唯一=真 |
---|
大小(最小到最大) ×计数 |
---|
5 (10至99) ×1,000,000 | 10 (10至99) ×1,000,000 |
---|
巨蟒 | p | 巨蟒 | p |
---|
| 11.77267 | 17.888 | 24.29039 | 33.6659 |
---|
| 12.51872 | 18.165 | 29.33268 | 35.202 |
---|
| 15.44188 | 17.861 | 30.06672 | 36.7911 |
---|
| 14.18681 | 19.7831 | 31.65981 | 39.3533 |
---|
| 13.63978 | 24.3374 | 28.41662 | 52.864 |
---|
| 14.21881 | 21.1452 | 25.80548 | 32.5419 |
---|
| 14.58683 | 28.5016 | 24.85942 | 50.3139 |
---|
| 18.53806 | 30.7238 | 29.6647 | 58.2493 |
---|
通过交换排序,一切都变得清晰了。 现在,对于真正有趣的部分-按插入排序。
参考文献
Excel应用程序AlgoLab ,您可以使用它逐步查看这些(不仅是这些)排序的可视化。
JSON形式的所有数组也都放置在
Google磁盘上 。
维基 -
傻 / 笨拙 , 慢 , 矮人 / 侏儒 , 泡泡 / 泡泡 , 摇床 / 摇床 , 奇数 / 偶数 , 梳子 / 梳子 , 快速 / 快速系列文章