排序算法中比较函数的运用

 

 

 

假如我们有一个表格如下，

 

1,5

 

 

2,3

 

 

3,7

 

 

需要根据第二例排序。我们应该怎么办呢？这里使用python作为范例，其他语言提供类似的泛型编程方法。

 

 

对这个数据排序可以写出如下代码：

def customCmp(a,b):
	return	cmp(a[1],b[1]) 
mylist=[]
a=[1,5]
b=[2,3]
c=[3,7]
mylist.append(a);
mylist.append(b)
mylist.append(c)
mylist.sort(customCmp)
for t in mylist: 
	print t

 

 

 

对应python中List的排序算法，我们只要指定的比较函数，我们就可以得到正确的排序结果。

 

上面的程序得到的是升序排列的结果。如果我们要得到降序排列的结果，我们只需要在cmp函数前面添加一个负号，如下：

1. defcustomCmp(a,b):
2. return-cmp(a[1],b[1])

我们发现，这样cmp每次都要取负，效率有点问题。如果我们修改一下，变为：

 

 

 

修改比较函数我们可以的比较特殊的排列效果，例如我们先对第二个字段安装奇数降序，再

 

对偶数降序，所有的奇数都在偶数的前面，代码如下：

def mycmp(a,b):
 if a[1]%2==1andb[1]%2==0: 
  return -1; 
 elif a[1]%2==0andb[1]%2==1:
 return 1; 
return cmp(b[1],a[1])mylist=[] 

a=[1,5]
b=[2,3]
c=[3,7]
d=[4,2]
e=[5,4]
mylist.append(a);
mylist.append(b)
mylist.append(c)
mylist.append(d)
mylist.append(e)
mylist.sort(mycmp)
for t in mylist: 
 print t

 

 

 

 

 

 

[3, 7]

 

 

[1, 5]

 

 

[2, 3]

 

 

[5, 4]

 

 

[4, 2]