如何在 5 次比较中对 4 个数字进行排序？
将数字 {a,b,c,d} 分成 2 个集合 {a,b} {c,d}。 对这 2 组中的每一组进行排序，这样您就得到 (e,f) (g,h)。这是每组一次比较。
现在从前面选择最低的（比较 e，g）。现在这是三个比较。 从 (e, h) 或 (f, g) 中选择下一个最低值。那是四个。 比较最后两个元素（如果这两个元素来自同一集合，因此已经排序，您甚至可能不需要此步骤）。所以这是五个。
伪代码：
function sortFour(a,b,c,d)
if a < b
low1 = a
high1 = b
else
low1 = b
high1 = a
if c < d
low2 = c
high2 = d
else
low2 = d
high2 = c
if low1 < low2
lowest = low1
middle1 = low2
else
lowest = low2
middle1 = low1
if high1 > high2
highest = high1
middle2 = high2
else
highest = high2
middle2 = high1
if middle1 < middle2
return (lowest,middle1,middle2,highest)
else
return (lowest,middle2,middle1,highest)
对于较少数量的输入，您可以生成最佳排序网络，以提供所需的最少比较次数。
您可以使用此页面
轻松生成它们按升序对四个数字进行排序：
if(num1>num2) swap(&num1,&num2);
if(num3>num4) swap(&num3,&num4);
if(num1>num3) swap(&num1,&num3);
if(num2>num4) swap(&num2,&num4);
if(num2>num3) swap(&num2,&num3);
哪里
void swap(int *a,int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
或者您可以实现自己的交换过程而无需额外变量
（对于降序，只需将符号更改为< )
这不需要额外的内存或交换操作，每次排序只需 5 次比较
def sort4_descending(a,b,c,d):
if a > b:
if b > c:
if d > b:
if d > a:
return [d, a, b, c]
else:
return [a, d, b, c]
else:
if d > c:
return [a, b, d, c]
else:
return [a, b, c, d]
else:
if a > c:
if d > c:
if d > a:
return [d, a, c, b]
else:
return [a, d, c, b]
else:
if d > b:
return [a, c, d, b]
else:
return [a, c, b, d]
else:
if d > a:
if d > c:
return [d, c, a, b]
else:
return [c, d, a, b]
else:
if d > b:
return [c, a, d, b]
else:
return [c, a, b, d]
else:
if a > c:
if d > a:
if d > b:
return [d, b, a, c]
else:
return [b, d, a, c]
else:
if d > c:
return [b, a, d, c]
else:
return [b, a, c, d]
else:
if b > c:
if d > c:
if d > b:
return [d, b, c, a]
else:
return [b, d, c, a]
else:
if d > a:
return [b, c, d, a]
else:
return [b, c, a, d]
else:
if d > b:
if d > c:
return [d, c, b, a]
else:
return [c, d, b, a]
else:
if d > a:
return [c, b, d, a]
else:
return [c, b, a, d]
目标是通过 5 次比较对 4 个元素进行排序。
Comp 1--> 取任意两个元素 a,b 并比较它们，其最大值为 Max1，最小值为 Min1。
Comp 2--> 取另外两个元素 c,d 并比较它们，其最大值为 Max2，最小值为 Min2。
Comp 3-->比较Max1和Max2以获得最终的Max元素。
Comp 4--> 比较 Min1 和 Min2 以获得最终的 Min 元素。
Comp 5-->比较Comp 4和Comp 5中的失败者以获得他们的顺序。
要在 5 次比较中对数字 ABCD 进行排序，请分别对 AB 和 CD 进行排序。这需要2次比较。现在像对字符串 AB 和 CD 进行合并排序一样调用合并。这需要 3，因为在第一次比较中，您将选择 A 或 C。您最终将合并 B 和 CD，或者 AB 和 D。这里您只需要 2 次比较，因为 AB 和 CD 都已排序。
刚刚实现了一个无分支函数，该函数使用五次比较对四个元素进行排序。可以将其制作成C++模板来对任何类型进行排序。数据不受影响，
r// This function actually returns a char[4], using type punning to bypass C restrictions
int order4(int* values) {
char r[4], h[2], m[2];
h[0]= values[1]<values[0];
h[1]=2|(char)(values[3]<values[2]); // 3210 -> {2<3}{0<1}
r[0]=values[h[1] ]<values[h[0] ];
r[3]=values[h[0]^1]<values[h[1]^1]; // {2<3}{0<1} -> 0<{21}<3
m[0]=h[r[0]^1];
m[1]=h[r[3]^1]^1;
r[2]=values[m[1]]<values[m[0]]; // 0<{21}<3 -> 0<1<2<3
r[0]=h[r[0]];
r[1]=m[r[2]];
r[2]=m[r[2]^1];
r[3]=h[r[3]]^1;
_ASSERT(((1<<r[0]) | (1<<r[1]) | (1<<r[2]) | (1<<r[3])) == 15); // Ensure that all elements present
_ASSERT(values[r[0]]<=values[r[1]] && values[r[1]]<=values[r[2]] && values[r[2]]<=values[r[3]]); // Ensure that elements are sorted
return *(int*)r;
}
Alg. 3: compare five, this average = 4.28 (#8 average = 5), Similar as #8<br>
compare 01, sort -> 0,1<br>
compare 23, sort -> 2,3<br>
compare 12 -> return or next compare<br>
compare 02, sort -> 0,2<br>
compare 13, sort -> 1,3<br>
compare 12, sort -> 1,2
<code>
function sort4CH(cmp,start,end,n)
{
var n = typeof(n) !=='undefined' ? n : 1;
var cmp = typeof(cmp) !=='undefined' ? cmp : sortCompare2;
var start = typeof(start)!=='undefined' ? start : 0;
var end = typeof(end) !=='undefined' ? end : arr[n].length;
var count = end - start;
var pos = -1;
var i = start;
var c = [];
c[0] = cmp(arr[n][i+0],arr[n][i+1]);
c[1] = cmp(arr[n][i+2],arr[n][i+3]);
if (c[0]>0) {swap(n,i+0,i+1);}
if (c[1]>0) {swap(n,i+2,i+3);}
c[2] = cmp(arr[n][i+1],arr[n][i+2]);
if (!(c[2]>0)) {return n;}
c[3] = c[0]==0 ? 1 : cmp(arr[n][i+0],arr[n][i+2]);// c[2]
c[4] = c[1]==0 ? 1 : cmp(arr[n][i+1],arr[n][i+3]);// c[2]
if (c[3]>0) {swap(n,i+0,i+2);}
if (c[4]>0) {swap(n,i+1,i+3);}
c[5] = !(c[3]>0 && c[4]>0) ? 1 : (c[0]==0 || c[1]==0 ? -1 : cmp(arr[n] [i+1],arr[n][i+2]));
if (c[5]>0) {swap(n,i+1,i+2);}
return n;
}
</code>
---------------------
Algoritmus: Insert sort sorted array 1-1, 2-2, 4-4, ... average = 3.96 = 1016/256 (average = 4.62 =1184/256 without previous cmp)
<code>
// javascript arr[1] = [0,1,2,3]
function sort4DN2(cmp,start,end,n) // sort 4
{
var n = typeof(n) !=='undefined' ? n : 1;
var cmp = typeof(cmp) !=='undefined' ? cmp : sortCompare2;
var start = typeof(start)!=='undefined' ? start : 0;
var end = typeof(end) !=='undefined' ? end : arr[n].length;
var count = end - start;
var pos = -1;
var i = start;
var c = [];
c[0] = cmp(arr[n][i+0],arr[n][i+1]);
c[1] = cmp(arr[n][i+2],arr[n][i+3]);
if (c[0]>0) {swap(n,i+0,i+1); c[0] = -1;}
if (c[1]>0) {swap(n,i+2,i+3); c[1] = -1;}
c[2] = cmp(arr[n][i+0],arr[n][i+2]);
//1234
if (c[2]>0)
{
//2013
c[3] = c[1]==0 ? c[2] : cmp(arr[n][i+0],arr[n][i+3]);
if (c[3]>0)
{
swap(n,i+0,i+2);
swap(n,i+1,i+3);
return n;
}
c[4] = c[0]==0 ? c[3] : (c[3]==0 ? 1 : cmp(arr[n][i+1],arr[n][i+3]));
if (c[4]>0)
{
//2013->2031
tmp = arr[n][i+0];
arr[n][i+0] = arr[n][i+2];
arr[n][i+2] = arr[n][i+3];
arr[n][i+3] = arr[n][i+1];
arr[n][i+1] = tmp;
return n;
}
// 2013
tmp = arr[n][i+2];
arr[n][i+2] = arr[n][i+1];
arr[n][i+1] = arr[n][i+0];
arr[n][i+0] = tmp;
return n;
}
if (c[2]==0) {
if (c[0]==0) {
return n;
}
if (c[1]==0) {
tmp = arr[n][i+1];
arr[n][i+1] = arr[n][i+2];
arr[n][i+2] = arr[n][i+3];
arr[n][i+3] = tmp;
return n;
}
}
c[3] = c[0]==0 ? c[2] : c[2]==0 ? -c[1] : cmp(arr[n][i+1],arr[n][i+2]);
if (c[3]>0)
{
c[4] = c[1]==0 ? c[3] : cmp(arr[n][i+1],arr[n][i+3]);
if (c[4]>0)
{
swap(n,i+1,i+2);
swap(n,i+2,i+3);
return n;
}
swap(n,i+1,i+2);
return n;
}
return n;
}
</code>
------------
Algoritmus: Insert sort into middle (av. 4.07 = 1044/256 | 4.53 = 1160/256)
0<br>
1 insert into middle 0 -> [0,1] 01, 10<br>
2 insert into middle 01 -> [1,2] 021, 012 -> [0,2] 021, 201 or [null] 012<br>
3 insert into middle 012 -> [1,3] -> [1,0] or [2,3]...
<code>
function sort4PA(cmp,start,end,n)
{
//arr[n] = [0,0,3,0];
var n = typeof(n) !=='undefined' ? n : 1;
var cmp = typeof(cmp) !=='undefined' ? cmp : sortCompare2;
var start = typeof(start)!=='undefined' ? start : 0;
var end = typeof(end) !=='undefined' ? end : arr[n].length;
var count = end - start;
var tmp = 0;
var i = start;
var c = [];
c[0] = cmp(arr[n][i+0],arr[n][i+1]);
if (c[0]>0) {swap(n,i+0,i+1); c[0] = -1;} //10->01
c[1] = cmp(arr[n][i+1],arr[n][i+2]);
if (c[1]>0) { //0-1 2
c[2] = c[0]==0 ? c[1] : cmp(arr[n][i+0],arr[n][i+2]);
if (c[2]>0) { //-01 2
c[3] = cmp(arr[n][i+0],arr[n][i+3]);
if (c[3]>0) {//2301
c[4] = cmp(arr[n][i+2],arr[n][i+3]);
if (c[4]>0) { //0123 -> 3201
tmp = arr[n][0];
arr[n][0]=arr[n][3];
arr[n][3]=arr[n][1];
arr[n][1]=arr[n][2];
arr[n][2]=tmp;
return n;
}
swap(n,i+0,i+2);
swap(n,i+1,i+3);
return n;
}
// 2031
c[4] = c[0]==0 ? c[3] : cmp(arr[n][i+1],arr[n][i+3]);
if (c[4]>0) { //2031
tmp = arr[n][0];
arr[n][0]=arr[n][2];
arr[n][2]=arr[n][3];
arr[n][3]=arr[n][1];
arr[n][1]=tmp;
return n;
}
tmp = arr[n][0];
arr[n][0]=arr[n][2];
arr[n][2]=arr[n][1];
arr[n][1]=tmp;
return n;
}
//0-1 2
c[3] = cmp(arr[n][i+2],arr[n][i+3]);
if (c[3]>0) {
c[4] = c[2]==0 ? c[3] : cmp(arr[n][i+0],arr[n][i+3]);
if (c[4]>0) {//3021
tmp = arr[n][0];
arr[n][0]=arr[n][3];
arr[n][3]=arr[n][1];
arr[n][1]=tmp;
return n;
}
//0321
swap(n,i+1,i+3);
return n;
}
// 0-1 23
c[4] = c[3]==0 ? c[1] : cmp(arr[n][i+1],arr[n][i+3]);
if (c[4]>0) { //0231
tmp = arr[n][1];
arr[n][1]=arr[n][2];
arr[n][2]=arr[n][3];
arr[n][3]=tmp;
return n;
}
//0213
swap(n,i+1,i+2);
return n;
}
c[2] = cmp(arr[n][i+1],arr[n][i+3]);
if (c[2]>0) {
c[3] = c[0]==0 ? c[2] : cmp(arr[n][i+0],arr[n][i+3]);
if (c[3]>0) {
// 3012
tmp = arr[n][0];
arr[n][0]=arr[n][3];
arr[n][3]=arr[n][2];
arr[n][2]=arr[n][1];
arr[n][1]=tmp;
return n;
}
// 0312
tmp = arr[n][1];
arr[n][1]=arr[n][3];
arr[n][3]=arr[n][2];
arr[n][2]=tmp;
return n;
}
c[3] = c[1]==0 ? c[2] : c[2]==0 ? -c[1] : cmp(arr[n][i+2],arr[n][i+3]);
if (c[3]>0) {
swap(n,i+2,i+3);
}
return n;
}
</code>
比较 Python 实现，Siddarth 和 Trott 的解决方案虽然排序顺序不同，但执行时间相似。 Daw 的建议（转换为 Python）在测试中稍微慢了 0.0000001 秒，尽管所有这些选项都执行得很快。我的替代解决方案使用 5 或 6 次比较，75% 的情况使用 5 次比较。虽然它通常比前三个慢，但它通常优于插入排序。:
permDict = {
'' : lambda a: a,
'12345': lambda a: [a[3],a[2], a[1], a[0]],
'5' : lambda a: [a[0],a[2], a[1], a[3]],
'1234' : lambda a: [a[3],a[1], a[2], a[0]],
'2' : lambda a: [a[0],a[1], a[3], a[2]],
'2345' : lambda a: [a[3],a[2], a[0], a[1]],
'45' : lambda a: [a[0],a[2], a[3], a[1]],
'124' : lambda a: [a[3],a[1], a[0], a[2]],
'245' : lambda a: [a[0],a[3], a[2], a[1]] if a[0] < a[3] else [a[3],a[0], a[2], a[1]],
'24' : lambda a: [a[3],a[0], a[1], a[2]] if a[3] < a[0] else [a[0],a[3], a[1], a[2]],
'1' : lambda a: [a[1],a[0], a[2], a[3]],
'1345' : lambda a: [a[2],a[3], a[1], a[0]],
'12' : lambda a: [a[1],a[0], a[3], a[2]] if a[0] < a[3] else [a[1],a[3], a[0], a[2]],
'345' : lambda a: [a[2],a[3], a[0], a[1]] if a[0] < a[3] else [a[2],a[0], a[3], a[1]],
'35' : lambda a: [a[2],a[0], a[1], a[3]],
'123' : lambda a: [a[1],a[3], a[2], a[0]],
'13' : lambda a: [a[1],a[2], a[0], a[3]] if a[0] < a[3] else [a[1],a[2], a[3], a[0]],
'135' : lambda a: [a[2],a[1], a[0], a[3]] if a[0] < a[3] else [a[2],a[1], a[3], a[0]],
}
def permSort(arr):
comp = ""
if arr[0] > arr[1]:
comp += "1"
if arr[2] > arr[3]:
comp += "2"
if arr[0] > arr[2]:
comp += "3"
if arr[1] > arr[3]:
comp += "4"
if arr[1] > arr[2]:
comp += "5"
return permDict[comp](arr)