func bubbleSort(list []int) []int {
	done := false
	for i := len(list) - 1; i >= 0; i-- {
		done = true
		for j := 0; j < i; i++ {
			if list[j] > list[j+1] {
				list[j], list[j+1] = list[j], list[j+1]
				done = false
			}
		}
		
		if done {
			break
		}
	}
	return list
}

func selectSort(list []int) []int {
	for i := len(list) - 1; i >= 0; i-- {
		maxIdx := 0
		for j := 1; j <= i; i++ {
			if list[j] > list[maxIdx] {
				maxIdx = j
			}
		}
		list[maxIdx], list[i] = list[i], list[maxIdx]
	}
	return list
}

func insertSort(list []int) []int {
	for i := 0; i < len(list); i++ {
		for j := i; j > 0; j-- {
			if list[j] < list[j-1] {
				list[j], list[j-1] = list[j-1], list[j]
			}
		}
	}
	return list
}

func mergeSort(list []int) []int {
	merge := func(l, r []int) []int {
		ret := make([]int, 0)
		i, j := 0, 0
		for i < len(l) && j < len(r) {
			if l[i] < r[j] {
				ret = append(ret, l[i])
				i++
			} else {
				ret = append(ret, r[j])
				j++
			}
		}
		
		if i < len(l) {
			ret = append(ret, l[i:]...)
		}
		
		if j < len(r) {
			ret = append(ret, r[j:]...)
		}
		
		return ret
	}

	var dm func([]int) []int
	dm = func(ls []int) []int {
		if len(ls) == 1 {
			return ls
		}

		ll := dm(ls[:len(ls)/2])
		lr := dm(ls[len(ls)/2:])
		return merge(ll, lr)
	}

	return dm(list)
}

func quickSort(list []int) []int {
	part := func(l, r int) int {
		pv := list[r]
		i := l
		for j := l; j < r; j++ {
			if list[j] < pv {
				list[i], list[j] = list[j], list[i]
				i++
			}
		}

		list[i], list[r] = list[r], list[i]
		return i
	}

	var df func(int, int)
	df = func(l, r int) {
		if l >= r {
			return
		}

		p := part(l, r)
		df(l, p-1)
		df(p+1, r)
	}

	df(0, len(list)-1)
	return list
}

func heapSort(list []int) []int {
	minHeap := make([]int, 0)

	// 建堆，上浮
	for _, v := range list {
		minHeap = append(minHeap, v)
		j := len(minHeap) - 1
		for j > 0 {
			parent := (j - 1) / 2
			if v >= minHeap[parent] {
				break
			}
			minHeap[j] = minHeap[parent]
			j = parent
		}
	}

	// 取值，下沉
	ret := make([]int, 0)
	for range minHeap {
		// 取堆顶
		ret = append(ret, minHeap[0])

		// 获取最后一个元素，并且挪到堆顶
		x := minHeap[len(minHeap)-1]
		minHeap = minHeap[:len(minHeap)-1]

		// 没有元素了
		if len(minHeap) == 0 {
			break
		}

		// 对堆顶元素做下沉操作
		i := 0
		for {
			l := 2*i + 1 // 左孩子
			r := 2*i + 2 // 右孩子

			// 如果没有左孩子，则停止下沉
			if l >= len(minHeap) {
				break
			}

			// 如果有右孩子，则比较左右孩子得到比较小的孩子下标赋值给l
			if r < len(minHeap) && minHeap[l] > minHeap[r] {
				l = r
			}

			// 如果比最小的孩子还要小，则停止下沉
			if x <= minHeap[l] {
				break
			}

			// 将较小的孩子提升上来
			minHeap[i] = minHeap[l]
			i = l
		}

		minHeap[i] = x
	}

	return ret
}

func countSort(list []int) []int {
	maxNum := list[0]
	for i := 1; i < len(list)-1; i++ {
		if list[i] > maxNum {
			maxNum = list[i]
		}
	}

	// 记录每个数的数量
	count := make([]int, maxNum+1)
	for _, v := range list {
		count[v]++
	}

	// 记录每个数的位置
	for i := 1; i < len(count); i++ {
		count[i] += count[i-1]
	}

	// 从后往前遍历，保证稳定性
	ret := make([]int, len(list))
	for i := len(list) - 1; i >= 0; i-- {
		idx := count[list[i]] - 1
		ret[idx] = list[i]
		count[list[i]]--
	}

	return ret
}