真空中的球形算法很棒。但是，让我们从天堂降落到罪恶的大地，看看所有这些理论上的美将如何在实践中证明自己。

对下一类排序的分析将以对类排序的测试结束。今天，我们将进行排序交换（不是从扔掉的意义上说，而是从测试的意义上说）。其他种类的类将稍后运行。

在今天的比赛中：

最弱的群体

由于降低了时间复杂度，这些算法没有任何要求。我们仅对其进行测试以供参考。

愚蠢的排序

排序缓慢

哑分类

更有趣的是，不仅它们有多出色，而且在业务上有多糟糕，其中哪一个最差。

主要组

在这里，交换交换排序为la O（ n ² ）。矮小排序（及其优化）+气泡排序的各种变体。

矮人排序

矮人分类（优化）

气泡排序

鸡尾酒分选

奇偶排序

这是当今测量中最有趣的部分。在主要团体的代表中，最顽固的斗争有望发生。

最强的群体

气泡的一种变化-通过梳子进行分类-克服了障碍O（ n ² ）并达到了历史悠久的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)) # minimum gap is 1 swaps = False for i in range(len(data) - gap): j = i + gap if data[i] > data[j]: data[i], data[j] = data[j], data[i] swaps = True return data def quick(data): less = [] pivotList = [] more = [] if len(data) <= 1: return data else: pivot = data[0] for i in data: if i < pivot: less.append(i) elif i > pivot: more.append(i) else: pivotList.append(i) less = quick(less) more = quick(more) return less + pivotList + more def k(data): return k_rec(data, 0, len(data) - 1) def k_rec(data, left, right): key = data[left] i = left j = right + 1 k = left + 1 p = left + 1 temp = False while j - i >= 2: if key <= data[p]: if p != j and j != right + 1: data[j] = data[p] elif j == right + 1: temp = data[p] j -= 1 p = j else: data[i] = data[p] i += 1 k += 1 p = k data[i] = key if temp: data[i + 1] = temp if left < i - 1: k_rec(data, left, i - 1) if right > i + 1: k_rec(data, i + 1, right) return data

PHP交换排序

  // function StoogeSort(&$arr, $i, $j) { if($arr[$j] < $arr[$i]) list($arr[$j], $arr[$i]) = array($arr[$i], $arr[$j]); if(($j - $i) > 1) { $t = ($j - $i + 1) / 3; StoogeSort($arr, $i, $j - $t); StoogeSort($arr, $i + $t, $j); StoogeSort($arr, $i, $j - $t); } return $arr; } // function SlowSort(&$arr, $i, $j) { if($i >= $j) return $arr; $m = ($i + $j) / 2; SlowSort($arr, $i, $m); SlowSort($arr, $m + 1, $j); if($arr[$m] > $arr[$j]) list($arr[$m], $arr[$j]) = array($arr[$j], $arr[$m]); SlowSort($arr, $i, $j - 1); return $arr; } // function StupidSort($arr) { $i = 1; $size = count($arr); while($i < $size) { if($arr[$i - 1] <= $arr[$i]){ ++$i; } else { list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]); $i = 1; } } return $arr; } // function GnomeSort($arr) { $i = 1; $size = count($arr); while($i < $size) { if($arr[$i - 1] <= $arr[$i]){ ++$i; } else { list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]); if($i > 1) --$i; } } return $arr; } // () function GnomeSort_opt($arr) { $i = 1; $j = 2; $size = count($arr); while($i < $size) { if($arr[$i - 1] <= $arr[$i]){ $i = $j; ++$j; } else { list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]); if(--$i == 0){ $i = $j; $j++; } } } return $arr; } // function BubbleSort($arr) { $c = count($arr) - 1; do { $swapped = false; for ($i = 0; $i < $c; ++$i) { if ($arr[$i] > $arr[$i + 1]) { list($arr[$i + 1], $arr[$i]) = array($arr[$i], $arr[$i + 1]); $swapped = true; } } } while($swapped); return $arr; } // function ShakerSort($arr){ do{ $swapped = false; for($i = 0; $i < count($arr); $i++){ if(isset($arr[$i + 1])) { if($arr[$i] > $arr[$i+1]) { list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]); $swapped = true; } } } if ($swapped == false) break; $swapped = false; for($i = count($arr) - 1; $i >= 0; $i--){ if(isset($arr[$i - 1])){ if($arr[$i] < $arr[$i - 1]) { list($arr[$i], $arr[$i - 1]) = array($arr[$i - 1], $arr[$i]); $swapped = true; } } } } while($swapped); return $arr; } //- function OddEvenSort($arr){ $n = count($arr); $sorted = false; while(!$sorted) { $sorted = true; for($i = 1; $i < $n - 2; $i += 2) { if($arr[$i] > $arr[$i + 1]) { list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]); $sorted = false; } } for($i = 0; $i < $n - 1; $i += 2) { if($arr[$i] > $arr[$i + 1]) { list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]); $sorted = false; } } } } // function CombSort($arr){ $gap = count($arr); $swap = true; while($gap > 1 || $swap){ if($gap > 1) $gap /= 1.25; $swap = false; $i = 0; while($i + $gap < count($arr)){ if($arr[$i] > $arr[$i + $gap]){ list($arr[$i], $arr[$i + $gap]) = array($arr[$i + $gap], $arr[$i]); $swap = true; } ++$i; } } return $arr; } // function QuickSort($arr) { $loe = $gt = array(); if(count($arr) < 2) { return $arr; } $pivot_key = key($arr); $pivot = array_shift($arr); foreach($arr as $val){ if($val <= $pivot){ $loe[] = $val; }elseif ($val > $pivot){ $gt[] = $val; } } return array_merge(QuickSort($loe), array($pivot_key => $pivot), QuickSort($gt)); } //k- function K_Sort($arr) { K_Sort_rec($arr, 0, count($arr) - 1); return $arr; } function K_Sort_rec(&$arr, $left, $right) { $key = $arr[$left]; $i = $left; $j = $right + 1; $k = $p = $left + 1; $temp = false; while($j - $i >= 2) { if($key <= $arr[$p]) { if(($p != $j) && ($j != ($right + 1))) { $arr[$j] = $arr[$p]; } elseif($j == ($right + 1)) { $temp = $arr[$p]; } --$j; $p = $j; } else { $arr[$i] = $arr[$p]; ++$i; ++$k; $p = $k; } } $arr[$i] = $key; if($temp) $arr[$i + 1] = $temp; if($left < ($i - 1)) K_Sort_rec($arr, $left, $i - 1); if($right > ($i + 1)) K_Sort_rec($arr, $i + 1, $right); }

时间

时间无处不在，以秒为单位，精确到微秒。

如果将一包数组（十个，一百个甚至一百万个数组中的一个）立即送入算法，则表明总时间。

铁是我忠实的旧笔记本电脑，它拥有更好的时代。因此，很可能一切都会为您更快地工作。

最坏的

立即与局外人打交道。为此，准备了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磁盘上。

维基 - 傻 / 笨拙，慢，矮人 / 侏儒，泡泡 / 泡泡，摇床 / 摇床，奇数 / 偶数，梳子 / 梳子，快速 / 快速

交换排序比较