排序算法

冒泡排序

双层循环,每次循环将最大的值放到数组的最后面,外层循环n次,内层循环n-i次完成排序,时间复杂度为O(n²)

1
2
3
4
5
6
7
8
9
func bubbleSort(arr []int) {
	for i := 0; i < len(arr)-1; i++ {
		for j := 0; j < len(arr)-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}

选择排序

双层循环,每次循环找出arr[n-i]中最小的数与当前数进行交换,时间复杂度为O(n²)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func selectSort(arr []int) {
	for i := 0; i < len(arr)-1; i++ {
		var min = i
		for j := i + 1; j < len(arr); j++ {
			if arr[min] > arr[j] {
				min = j
			}
		}
		arr[i], arr[min] = arr[min], arr[i]
	}
}

插入排序

双层循环,类似打扑克牌调整牌的顺序,每次循环对当前数字顺序进行插入调整,时间复杂度为O(n²)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func insertionSort(arr []int) {
	for i := range arr {
		preIndex := i - 1
		current := arr[i]
		for preIndex >= 0 && arr[preIndex] > current {
			arr[preIndex+1] = arr[preIndex]
			preIndex -= 1
		}
		arr[preIndex+1] = current
	}
}

归并排序

分治的思想,时间复杂度O(N*logN)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func mergeSort(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}
	i := len(arr) / 2
	left := mergeSort(arr[:i])
	right := mergeSort(arr[i:])
	result := merge(left, right)
	return result
}

func merge(left, right []int) []int {
	result := make([]int, 0)
	m, n := 0, 0
	l, r := len(left), len(right)
	for m < l && n < r {
		if left[m] > right[n] {
			result = append(result, right[n])
			n++
		} else {
			result = append(result, left[m])
			m++
		}
	}
	result = append(result, right[n:]...)
	result = append(result, left[m:]...)
	return result
}

堆排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package heap

func sink(array []int, parentIndex int, length int) {
	//保存父节点，用于最后的赋值
	temp := array[parentIndex]
	//左子节点
	childIndex := 2*parentIndex + 1
	//是否有左子节点
	for childIndex < length {
		//判断是否有右子节点，并且右子节点大于左子节点的值
		if childIndex+1 < length && array[childIndex+1] > array[childIndex] {
			childIndex++
		}
		//如果父节点大于任何一个子节点的值直接跳出
		if temp >= array[childIndex] {
			break
		}
		array[parentIndex] = array[childIndex]
		parentIndex = childIndex
		childIndex = 2*childIndex + 1
	}
	array[parentIndex] = temp
}

func heapSort(array []int) {
	//构建大顶堆
	for i := (len(array) - 2) / 2; i >= 0; i-- {
		sink(array, i, len(array))
	}
	//将堆顶元素和最后一个元素交换，数组长度i--(相当于循环删除根顶部元素，然后sink 调整最大堆)
	for i := len(array) - 1; i > 0; i-- {
		array[i], array[0] = array[0], array[i]
		sink(array, 0, i)
	}
}