冒泡排序

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

插入排序

func insertsort(nums []int) []int {
	for i := 1; i < len(nums); i++ {
		if nums[i] <= nums[i-1] {
			j := i
			for nums[j] < nums[j-1] {
				nums[j], nums[j-1] = nums[j-1], nums[j]
				j--
				if j == 0 {
					break
				}
				fmt.Println(nums)
			}
		}
	}
	return nums
}

选择排序

func selectsort(nums []int) []int {
	for i := 0; i < len(nums); i++ {
		temp := i
		for j := i; j < len(nums); j++ {
			if nums[j] < nums[temp] {
				temp = j
			}
		}
		nums[temp], nums[i] = nums[i], nums[temp]
	}
	return nums
}

归并排序

func mergeort(nums []int) []int {
	if len(nums) > 1 {
		mid := len(nums) / 2
		left := mergeort(nums[:mid])
		right := mergeort(nums[mid:])
		temp := []int{}
		for i, j := 0, 0; i < len(left) && j < len(right); {
			if left[i] < right[j] {
				temp = append(temp, left[i])
				i++
				if i == len(left) {
					temp = append(temp, right[j:]...)
					break
				}
			} else {
				temp = append(temp, right[j])
				j++
				if j == len(right) {
					temp = append(temp, left[i:]...)
					break
				}
			}
		}
		return temp
	}
	return nums
}

显然，这个归并排序每次递归都会创建新的切片，空间占用直接爆炸

为了解决这个问题，下面的快速排序是在原有的切片上操作，使得空间占用大大降低

快速排序

func quicksort(nums []int, left, right int) []int {
	if left >= right {
		return nums
	}
	i, j := left, right
	privot := nums[i]
	for i < j {
		for i < j && nums[j] >= privot {
			j--
		}
		nums[i] = nums[j]
		for i < j && nums[i] <= privot {
			i++
		}
		nums[j] = nums[i]
	}
	nums[i] = privot
	quicksort(nums, left, i-1)
	quicksort(nums, i+1, right)
	return nums
}