经典算法巡礼(六) -- 排序之快速排序

	// partition方法即为快速排序中重要的切分操作，以首元素做为基准，将剩余元素从两端寻找，分别找到大于（小于）基准的元素并交换，重复此过程直到剩余元素全部遍历为止
	func (this *QuickSort) partition(a []Comparable, compare Compare, lo int, hi int) int {
		i := lo + 1
		j := hi
		v := a[lo]
		for true {
			for this.less(a[i], v, compare) == true {
				if i == hi {
					break
				}
				i++
			}
			for this.less(a[j], v, compare) == false {
				if j == lo {
					break
				}
				j--
			}
			if i >= j {
				break
			}
			this.exch(a, i, j)
			i++
			j--
		}
		this.exch(a, lo, j)

		return j
	}

	// Sort中参数类型Comparable为统一的可比较接口，若为整数数组排序，则Comparable为int即可
	// Sort中参数类型Compare为配合Comparable接口的比较方法，若为整数数组排序，则Compare即满足a int < a int即可
	func (this *QuickSort) Sort(a []Comparable, compare Compare, lo int, hi int) {
		if hi <= lo {
			return
		}

		p := this.partition(a, compare, lo, hi)
		this.Sort(a, compare, lo, p-1)
		this.Sort(a, compare, p+1, hi)
	}

	// Sort方法采用”三向切分的快速排序“法进行排序
	func (this *QuickSort) Sort(a []Comparable, compare Compare, lo int, hi int) {
		if hi <= lo {
			return
		}

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

		v := a[lo]
		for i <= gt {
			cmp := compare(v, a[i])
			if cmp < 0 {
				this.exch(a, i, gt)
				gt--
			} else if cmp > 0 {
				this.exch(a, i, lt)
				i++
				lt++
			} else {
				i++
			}
		}
		this.Sort(a, compare, lo, lt-1)
		this.Sort(a, compare, gt+1, hi)
	}