Golang 设计实现排序算法工具包 go-sort 
冒泡排序选择排序快速排序堆排序

工具包的设计我们需要注重于开放API的设计上，API的灵活性能直接说明工具包设计的好坏。

Sortable
type Sortable interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
}
  • Len：返回slice长度
  • Less：判断第一个下标的值是否小于第二个下标的值
  • Swap：两个下标的值互相交换
Comparable
type Comparable interface {
	LessThan(other Comparable) bool
}
  • LessThan：比较两个Comparable元素，判断当前的元素是否小于给定的元素

这样我就可以定义新的一种类型：

type Slice []Comparable

gosort.SliceSortable
type Slice []Comparable

func (c Slice) Len() int {
	return len(c)
}

func (c Slice) Less(i, j int) bool {
	return c[i].LessThan(c[j])
}

func (c Slice) Swap(i, j int) {
	c[i], c[j] = c[j], c[i]
}

这下定义我们工具包内可排序的列表就非常简单了：

// 定义我们的自定义元素
type Person struct {
	Age int
}

// 实现Comparable接口
func (p Person) LessThan(other gosort.Comparable) bool {
  // 这里需要转换类型
	person, ok := other.(Person)
	if !ok {
		return false
	}
	return p.Age < person.Age
}

// 最后定义slice即可，可以使用go原生slice的所有方法
var people gosort.Slice
people = append(people, Person{Age: 10})

gosort.IntSlicegosort.Float64Slicegosort.IntSlice
type IntSlice []int

func (slice IntSlice) Len() int {
	return len(slice)
}

func (slice IntSlice) Less(i, j int) bool {
	return slice[i] < slice[j]
}

func (slice IntSlice) Swap(i, j int) {
	slice[i], slice[j] = slice[j], slice[i]
}

这时候我们工具包内的数据类型就基本统一了，Sortable和Slice都实现了Sortable接口，我们可以放心使用Sortable接口去实现我们的排序算法。

在实现排序算法之前，我们先定义排序算法的统一格式：

type SortFunc func(sortable Sortable)

再定义算法名类型：

type algorithm string

const (
	SortAlgorithmQuicksort     algorithm = "quicksort"
	SortAlgorithmSelectionSort algorithm = "selectionsort"
	SortAlgorithmBubbleSort    algorithm = "bubblesort"
	SortAlgorithmHeapSort      algorithm = "heapsort"
)

这里，SortFunc是出口类型而algorithm不是的原因是，我们可以让使用工具包的用户自定义排序函数但是不能自定义排序算法去重写工具包内的算法实现。

进而我们使用上述两种类型组成一个map结构：

// 这里充当value的SortFunc我们将会在文档后续实现
var sorts = map[algorithm]SortFunc{
	SortAlgorithmQuicksort:     QuickSort,
	SortAlgorithmSelectionSort: SelectionSort,
	SortAlgorithmBubbleSort:    BubbleSort,
	SortAlgorithmHeapSort:      HeapSort,
}

这样我们的第一个API就设计好了：

// 用户传入列表和算法类型，我们直接调用即可，算法类型只能使用我们定义的常量
func Sort(list Sortable, alg algorithm) {
	sorts[alg](list)
}

冒泡排序

// BubbleSort sorts the Sortable using bubble sort algorithm
func BubbleSort(list Sortable) {
	bubbleSort(list)
}

func bubbleSort(list Sortable) {
	for i := 0; i < list.Len()-1; i++ {
		for j := i + 1; j < list.Len(); j++ {
			if list.Less(j, i) {
				list.Swap(i, j)
			}
		}
	}
}

选择排序

// SelectionSort sorts the Sortable using selection sort algorithm
func SelectionSort(list Sortable) {
	selectionSort(list)
}

func selectionSort(list Sortable) {
	for i := 0; i < list.Len(); i++ {
		minIdx := i
		for j := i; j < list.Len(); j++ {
			if list.Less(j, minIdx) {
				minIdx = j
			}
		}
		list.Swap(i, minIdx)
	}
}

快速排序

// QuickSort sorts the Sortable using quicksort algorithm
func QuickSort(list Sortable) {
	quicksort(0, list.Len(), list)
}

func quicksort(low, high int, list Sortable) {
	if low >= high {
		return
	}
	var (
		i, j, p = low, high - 1, low
	)
	for {
		for i < list.Len() && !list.Less(p, i) {
			i++
		}
		for j >= 0 && list.Less(p, j) {
			j--
		}
		if i >= j {
			break
		}
		list.Swap(i, j)
	}
	list.Swap(p, j)
	quicksort(low, j, list)
	quicksort(j+1, high, list)
}

堆排序

// HeapSort sorts the Sortable using heapsort algorithm
func HeapSort(list Sortable) {
	heapsort(list)
}

func heapsort(list Sortable) {
	for i := list.Len()/2 - 1; i >= 0; i-- {
		heapify(list, list.Len(), i)
	}
	for i := list.Len() - 1; i >= 0; i-- {
		list.Swap(0, i)
		heapify(list, i, 0)
	}
}

func heapify(list Sortable, length int, rootIdx int) {
	var (
		largest = rootIdx
		left    = 2*rootIdx + 1
		right   = 2*rootIdx + 2
	)
	if left < length && list.Less(largest, left) {
		largest = left
	}
	if right < length && list.Less(largest, right) {
		largest = right
	}
	if largest != rootIdx {
		list.Swap(rootIdx, largest)
		heapify(list, length, largest)
	}
}

实现好所有算法之后，我们接下来就测试使用一下我们的工具包：

type Person struct {
	Age int
}

type Item struct {
	Price int
}

func (p Person) LessThan(other gosort.Comparable) bool {
	person, ok := other.(Person)
	if !ok {
		return false
	}
	return p.Age < person.Age
}

func (i Item) LessThan(other gosort.Comparable) bool {
	item, ok := other.(Item)
	if !ok {
		return false
	}
	return i.Price < item.Price
}

func main() {

	var intSl gosort.IntSlice
	intSl = append(intSl, []int{2, 4, 3, 7, 10, 3, 0, 3, 6}...)
	fmt.Printf("intSlice before sort: %v\n", intSl)
	gosort.Sort(intSl, gosort.SortAlgorithmBubbleSort)
	fmt.Printf("intSlice after bubble sort: %v\n", intSl)

	var floatSlice gosort.Float64Slice
	floatSlice = append(floatSlice, []float64{1.9, 7.2, 3.4, 0.5, 5.7}...)
	fmt.Printf("floatSlice before sort: %v\n", floatSlice)
	gosort.Sort(floatSlice, gosort.SortAlgorithmSelectionSort)
	fmt.Printf("floatSlice after selection sort: %v\n", floatSlice)

	var people gosort.Slice
	people = append(people, Person{10})
	people = append(people, Person{3})
	people = append(people, Person{7})
	fmt.Printf("people before sort: %v\n", people)
	gosort.Sort(people, gosort.SortAlgorithmQuicksort)
	fmt.Printf("intSlice after selection sort: %v\n", people)

	var items gosort.Slice
	items = append(items, Item{15})
	items = append(items, Item{8})
	items = append(items, Item{20})
	fmt.Printf("items before sort: %v\n", items)
	gosort.Sort(items, gosort.SortAlgorithmHeapSort)
	fmt.Printf("intSlice after heap sort: %v\n", items)
}

➜  go-sorts go run main.go
intSlice before sort: [2 4 3 7 10 3 0 3 6]
intSlice after bubble sort: [0 2 3 3 3 4 6 7 10]
floatSlice before sort: [1.9 7.2 3.4 0.5 5.7]
floatSlice after selection sort: [0.5 1.9 3.4 5.7 7.2]
people before sort: [{10} {3} {7}]
intSlice after selection sort: [{3} {7} {10}]
items before sort: [{15} {8} {20}]
intSlice after heap sort: [{8} {15} {20}]