Go排序

Tags: Golang

选择排序

每次找未排序部分最小的，放到前面

go
func selectSort(arr []int) []int {
	for i := 0; i < len(arr); i++ {
		min := i
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < arr[min] {
				min = j
			}
		}
		arr[i], arr[min] = arr[min], arr[i]
	}
	return arr
}

冒泡排序

比较相邻元素，如果逆序则交换

go
func bubbleSort(arr []int) []int {
	swapped := true
	for swapped {
		swapped = false
		for i := 0; i < len(arr)-1; i++ {
			if arr[i] > arr[i+1] {
				arr[i], arr[i+1] = arr[i+1], arr[i]
				swapped = true
			}
		}
	}
	return arr
}

插入排序

将未排序的部分，逐个插入到已排序部分

go
func insertSort(arr []int) []int {
	for i := 1; i < len(arr); i++ {
		tmp := arr[i]
		j := i - 1
		for ; j >= 0 && arr[j] > tmp; j-- {
			arr[j+1] = arr[j]
		}
		arr[j+1] = tmp
	}
	return arr
}

希尔排序

把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

go
func shellSort(arr []int) []int {
	for d := len(arr) / 2; d > 0; d /= 2 {
		for i := d; i < len(arr); i++ {
			for j := i; j >= d && arr[j] < arr[j-d]; j -= d {
				arr[j], arr[j-d] = arr[j-d], arr[j]
			}
		}
	}
	return arr
}

归并排序

分治思想，不断将已排序的数组合并

go
func merge(left, right []int) []int {
	res := make([]int, 0, len(left)+len(right))
	i, j := 0, 0
	for i < len(left) && j < len(right) {
		if left[i] <= right[j] {
			res = append(res, left[i])
			i++
		} else {
			res = append(res, right[j])
			j++
		}
	}
	for i < len(left) {
		res = append(res, left[i])
		i++
	}
	for j < len(right) {
		res = append(res, right[j])
		j++
	}
	return res
}

func mergesort(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}
	mid := len(arr) / 2
	left := mergesort(arr[:mid])
	right := mergesort(arr[mid:])
	return merge(left, right)
}

快速排序

选出一个基准（pivot），将比它小的放在前面，大的放在后面。再递归的处理前后的数组

go
func partition(list []int, low, high int) int {
	pivot := list[low]
	for low < high {
		for low < high && list[high] >= pivot {
			high--
		}
		list[low] = list[high]
		for low < high && list[low] <= pivot {
			low++
		}
		list[high] = list[low]
	}
	list[low] = pivot
	return low
}

func quickSort(list []int, low, high int) {
	if high > low {
		pivot := partition(list, low, high)
		quickSort(list, low, pivot-1)
		quickSort(list, pivot+1, high)
	}
}