/三向切分的快速排序

Created Sun, 23 Dec 2018 23:02:56 +0800 Modified Mon, 13 Dec 2021 10:41:45 +0800
170 Words

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

今天看到《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)
}