基本排序算法总结

 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
36
37
38

// BubbleSort 冒泡排序
func BubbleSort(s []int) {
	l := len(s)
	for i := 0; i < l; i++ {
		for j := 0; j < l-1-i; j++ {
			if s[j] > s[j+1] {
				s[j], s[j+1] = s[j+1], s[j]
			}
		}
	}
	fmt.Println("冒泡排序后：", s)
}

// OpBubbleSort 优化后的冒泡排序
// 在一趟排序中如果没有发生交换说明已经是有序的
// 可以直接停止排序
// 这个优化对性能提升没有太大帮助
func OpBubbleSort(s []int) {
	l := len(s)
	var flag bool
	for i := 0; i < l; i++ {
		flag = false
		for j := i + 1; j < l-i; j++ {
			for j := 0; j < l-1-i; j++ {
				if s[j] > s[j+1] {
					s[j], s[j+1] = s[j+1], s[j]
					flag = true
				}
			}
		}
		// 如果没有发生交换说民已经有序，直接返回
		if !flag {
			break
		}
	}
	fmt.Println("冒泡排序后：", s)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// SelectSort 选择排序算法
// 升序排序
// 遍历 每次选择最小的数放在排序位置
func SelectSort(s []int) {
	l := len(s)
	fmt.Println(l, cap(s))
	for i := 0; i <= l; i++ {
		// 寻找[i,l)区间里的最小值,并交换
		for j := i + 1; j < l; j++ {
			if s[j] < s[i] {
				// 交换
				s[i], s[j] = s[j], s[i]
			}
		}
	}
	fmt.Println("选择排序后：", s)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// InsertionSort 插入排序
func InsertionSort(s []int) {
	for i := range s {
		// 已排序末位元素索引
		pk := i - 1
		// 待插入的元素
		cu := s[i]
		// 第一趟排序不会执行这个循环
		// 第二趟开始，从后往前遍历已排序数列与待插入元素比较
		// 如果已排序数列中的数大于待插入数则将其后移一个元素
		// 以为插入数腾出空间
		for pk >= 0 && s[pk] > cu {
			s[pk+1] = s[pk]
			pk--
		}
		// 第一趟循环，将第一个元素当作已排序
        // 第二趟开始，如果没有进入子循环（待插入数大于等于已排序末端元素）
        // 待插入数无需移动
		// 如果进入了子循环则相当于将待插入元素插入到比它大的元素前
		s[pk+1] = cu
	}
	fmt.Println("插入排序后：", s)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func ShellSort(s []int) {
	l := len(s)
	gap := 1
	for gap < gap/3 {
		gap = gap*3 + 1
	}
	for gap > 0 {
		for i := gap; i < l; i++ {
			tmp := s[i]
			j := i - gap
			for j >= 0 && s[j] > tmp {
				s[j+gap] = s[j]
				j = j - gap
			}
			s[j+gap] = tmp
		}
		gap = gap / 3
	}
	fmt.Println("希尔排序后：", s)
}

 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
36
37
38
39
40
41

// MergeSort 归并排序
func MergeSort(s []int) {
	s = mergeSort(s)
	fmt.Println("归并排序后：", s)
}

// 递归
func mergeSort(s []int) []int {
	l := len(s)
	if l < 2 {
		return s
	}
	mid := l / 2
	left := s[0:mid]
	right := s[mid:]
	return merge(mergeSort(left), mergeSort(right))
}

// 分治与合并
func merge(l []int, r []int) []int {
	var rs []int
	for len(l) != 0 && len(r) != 0 {
		if l[0] <= r[0] {
			rs = append(rs, l[0])
			l = l[1:]
		} else {
			rs = append(rs, r[0])
			r = r[1:]
		}
	}
	for len(l) != 0 {
		rs = append(rs, l[0])
		l = l[1:]
	}
	for len(r) != 0 {
		rs = append(rs, r[0])
		r = r[1:]
	}
	return rs
}

 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

// QuickSort 快速排序
func QuickSort(s []int) {
	s = quickSort(s, 0, len(s)-1)
	fmt.Println("快速排序后：", s)
}

// 递归分治
func quickSort(s []int, l, r int) []int {
	if l < r {
		pi := partition(s, l, r)
		quickSort(s, l, pi-1)
		quickSort(s, pi+1, r)
	}
	return s
}

// 分区
func partition(s []int, l, r int) int {
	pivot := l
	index := pivot + 1
	for i := index; i <= r; i++ {
		if s[i] < s[pivot] {
			s[i], s[index] = s[index], s[i]
			index++
		}
	}
	s[pivot], s[index-1] = s[index-1], s[pivot]
	return index - 1
}

 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

// HeapSort 堆排序
func HeapSort(s []int) {
	l := len(s)
	buildMaxHeap(s, l)
	for i := l - 1; i >= 0; i-- {
		s[0], s[i] = s[i], s[0]
		l--
		heapify(s, 0, l)
	}
	fmt.Println("堆排序后：  ", s)
}
func buildMaxHeap(s []int, sl int) {
	for i := sl / 2; i >= 0; i-- {
		heapify(s, i, sl)
	}
}
func heapify(s []int, i, sl int) {
	l := 2*i + 1
	r := 2*i + 2
	largest := i
	if l < sl && s[l] > s[largest] {
		largest = l
	}
	if r < sl && s[r] > s[largest] {
		largest = r
	}
	if largest != i {
		s[i], s[largest] = s[largest], s[i]
		heapify(s, largest, sl)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// CountingSort 计数排序
func CountingSort(s []int, maxValue int) {
	bucketLen := maxValue + 1
	bucket := make([]int, bucketLen) // 初始为0的数组

	sortedIndex := 0
	length := len(s)

	for i := 0; i < length; i++ {
		bucket[s[i]]++
	}

	for j := 0; j < bucketLen; j++ {
		for bucket[j] > 0 {
			s[sortedIndex] = j
			sortedIndex++
			bucket[j]--
		}
	}
	fmt.Println("计数排序后：", s)
}