我的名字叫浩仔/三向切分的快速排序

面试过程中，经常会遇到“快排”的这个题目，平时只是写出来了，但是一旦问到如何优化，就没有思路了。

今天看到《Algorithms Fourth Edition》中记录的“三向切分的快速排序”，所以用Go来实现下。

代码如此：

func quick3way(a []int, lo, hi int) {
	if lo >= hi {
		return
	}

	lt, i, gt := lo, lo+1, hi

	v := a[lo]

	for i <= gt {
		if a[i] < v {
			a[lt], a[i] = a[i], a[lt]
			lt++
			i++
		} else if a[i] > v {
			a[gt], a[i] = a[i], a[gt]
			gt--
		} else {
			i++
		}
	}

	quick3way(a, lo, lt-1)
	quick3way(a, gt+1, hi)
}