[TOC]

table.sort

简单来说就是table.sort的第二个参数支持自定义比较函数，这类似于c++的容器支持自定义比较函数一样，代码如下：

local tbTest = {
	{1, 3},
	{3, 5},
	{5, 4},
	{2, 3},
}

-- 比较函数
function cmp(a, b)
	return a[2] < b[2]
end

-- 通常用法
table.sort(tbTest, cmp)

深入学习

在自己工作过程中，遇到过下面两个问题

1.自定义排序算法的问题

第一个问题是：当自定义比较函数出现比较两个参数时，无法严格给出一个结果，就会出现错误。用官方的说法是比较函数需要满足非对称和传递性质。对于这两个性质，可以回忆一下中学时候学的不等式相关性质，也可以看看《c++标准程序库》中介绍的比较函数排序准则[1]。官网文档说明如下：

Note that the comp function must define a strict partial order over the elements in the list; that is, it must be asymmetric and transitive. Otherwise, no valid sort may be possible.

拿上面的代码举例，当把比较函数改为：

-- 比较函数
function cmp(a, b)
	return a[2] <= b[2]
end

这个时候就会出现下面的错误：

 attempt to index local 'b' (a nil value)

因为，这个时候元素a={1, 3}和b={2, 3}的a[2] == b[2]，a[2] <= b[2]和b[2] <= a[2]都成立。所以这个是比较函数是symmetric的。

2.面向对象方式的问题

在工作中，写比较大的功能的时候，会经常用到lua的面向对象的方式编码。一开始无知的时候，会写下面的代码，结果后面的苦头自己吃了。

local tbSort = {25, 18, 15}
--面向对象隐藏self
function tbSort:fCompWrap(a, b)
	print("fCompWrap(self, a, b)", self, a, b)
	return a < b;
end
-- 比较
table.sort(tbSort, tbSort.fCompWrap)

结果，往往是比较函数报错，第二个参数为nil

attempt to compare number with nil

只要理解’.’和’:’的区别就可以了，后面的’:’会使得函数的第一个参数为self。所以下面的一种写法可以解决问题：

--面向对象
function tbSort.fComp(a, b)
	return a < b;
end

当然，最好可以用闭包的比较函数，就省掉了这许多麻烦。一点点的总结：

table.sort的比较函数在面向对象编程时候要注意了
lua面向对象中的self要理解：table:func(param) 等价于table.func(self, param)
table:func定义式在作为参数(table.func)传递之后使用，默认就是table:func的调用形式，也就是第一个参数为self
应该理解function table:func(param)的定义形式等价于function table.func(self, param)，这样更容易分的清楚

源码的简单分学习

关于问题1中的报错，可以看一下源码

for (;;) {  /* invariant: a[l..i] <= P <= a[j..u] */
  /* repeat ++i until a[i] >= P */
  while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {
    if (i>u) luaL_error(L, "invalid order function for sorting");
    lua_pop(L, 1);  /* remove a[i] */
  }
  /* repeat --j until a[j] <= P */
  while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {
    if (j<l) luaL_error(L, "invalid order function for sorting");
    lua_pop(L, 1);  /* remove a[j] */
  }
  if (j<i) {
    lua_pop(L, 3);  /* pop pivot, a[i], a[j] */
    break;
  }
  set2(L, i, j);
}

有几点不一样的地方

lua源码中的快速排序，是用大循环代替了pivot的另外一部分排序。一般我们自己写快排的时候，会递归调两次，小于pivot的一部分和大于pivot的一部分
递归++i和++j的while，一般自己在写的时候会同时检查比较函数的结果和i、j的大小，防止越界

参考补充

[1]《c++标准程序库》

所谓的“排序准则”，必须定义strict weak ordering，其意义如下：

必须是“反对称的(antisymmetric)” 对operator<而言，如果x<y为真，则y<x为假。
必须是“可传递的（transitive）” 对operator<而言，如果x<y为真且y<z为真，则x<z为真。
必须是“非自反的（irreflexive）” 对operator<而言，x<x永远为假。

Lua学习笔记(6)table.sort