数组有N个元素，每个元素可能是红色、白色或蓝色。现在要把它们按照颜色排序（左红中白右蓝）。写出代码。

sort-by-color.lua

function printa(arr)
	for _, v in ipairs(arr) do
		io.write(v .. " ")
	end
	io.write("\n")
end

-- use consecutive number to represent the colors, like:
-- red: 1
-- blue: 2
-- green: 3
-- ...: 4

-- The algorithm runs in linear time with an extra space of 2 * color-numbers
function sort_by_color(arr)
	-- count number of each color
	local counter = {}
	for i, v in ipairs(arr) do
		if not counter[v] then counter[v] = 0 end
		counter[v] = counter[v] + 1
	end
	
	-- caculate a color's targeted start index
	counter[0] = 1
	for i = 1, #counter-1 do
		counter[i] = counter[i-1] + counter[i]
	end
	for i = #counter+1, 0, -1 do
		counter[i] = counter[i-1]
	end
	counter[#counter] = #arr + 1 -- set to maximum
	-- printa(counter)
	
	
	-- check if a color is already in the scope
	local origcount = {}
	for i = 0, #counter do
		origcount[i] = counter[i]
	end
	local function inscope(i, v)
		return i >= origcount[v] and i < origcount[v+1]
	end
	
	
	-- Iterate the array, if a color is not in scope, swap it to the target scope
	for i = 1, #arr do
		local v = arr[i]
		while not inscope(i, v) do
			-- loop until find an element that is not in scope
			while inscope(counter[v], arr[counter[v]]) do
				counter[v] = counter[v] + 1
			end
			arr[counter[v]], arr[i] = arr[i], arr[counter[v]]
			counter[v] = counter[v] + 1 -- increase the start index
			v = arr[i]
		end
	end
	printa(arr)
end


sort_by_color{1}
sort_by_color{1, 2}
sort_by_color{1, 2, 3, 4, 5}
sort_by_color{4, 3, 2, 1, 5}
sort_by_color{1, 1, 1, 1, 1, 1}
sort_by_color{1, 1, 2, 2, 3, 3, 4, 4}
sort_by_color{1, 2, 3, 1, 2, 3, 4}
sort_by_color{3,3,4,1,2,3,3,3,2,1,1,3}

$ lua sortbycolor.lua
1
1 2
1 2 3 4 5
1 2 3 4 5
1 1 1 1 1 1
1 1 2 2 3 3 4 4
1 1 2 2 3 3 4
1 1 1 2 2 3 3 3 3 3 3 4