快速排序

// 切分
func partition(data Interface, lo, hi int) int {
	i, j := lo+1, hi+1
	pivot := lo
	for {
		for ; data.Less(i, pivot); i++ {
			if i == hi {
				break
			}
		}
		j--
		for ; data.Less(pivot, j); j-- {
			if j == lo {
				break
			}
		}

		if i >= j {
			break
		}
		data.Swap(i, j)
	}
	data.Swap(lo, j)
	return j
}

// 递归子程序
func qsort(data Interface, lo, hi int) {
	if hi <= lo {
		return
	}
	j := partition(data, lo, hi)
	qsort(data, lo, j-1)
	qsort(data, j+1, hi)
}

//主程序
func qSort(data Interface) {
	qsort(data, 0, data.Len()-1)
}

优化

对于小数组，快速排序比插入排序慢，因此，可以在程序中定制。比如在qsort中将

	if hi <= lo {
		return
	}

替换成

    if hi <= lo + M {
        insertSort(data, lo, hi)
        return
    }