0%

排序算法

发表于 更新于 分类于

常见的排序算法有八种：冒泡排序、选择排序、插入排序、归并排序、快速排序; 本文中主要介绍这些排序算法，及Golang实现。

1.冒泡排序

  依次比较相邻两元素，若前一元素大于后一元素则交换，直至最后一个元素即为最大；然后重新从首元素开始重复同样的操作，直至倒数第二个元素即为次大元素；依次类推。如同水中的气泡，依次将最大或最小元素气泡浮出水面。

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

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

func main() {
	ns := []int{5, 2, 4, 6, 1, 3}
	ns = SortBubble(ns)
	fmt.Println(ns)
}

冒泡排序时间复杂副O(N2)， 空间复杂度O(1)，稳定性：稳定

2.选择排序

  首先初始化最小元素索引值为首元素，依次遍历待排序数列，若遇到小于该最小索引位置处的元素则刷新最小索引为该较小元素的位置，直至遇到尾元素，结束一次遍历，并将最小索引处元素与首元素交换；然后，初始化最小索引值为第二个待排序数列元素位置，同样的操作，可得到数列第二个元素即为次小元素；以此类推。

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

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

func main() {
	ns := []int{5, 2, 4, 6, 1, 3}
	ns = SortSelect(ns)
	fmt.Println(ns)
}

选择排序时间复杂副O(N2)， 空间复杂度O(1) ，稳定性：不稳定

3.插入排序

  数列前面部分看为有序，依次将后面的无序数列元素插入到前面的有序数列中，初始状态有序数列仅有一个元素，即首元素。在将无序数列元素插入有序数列的过程中，采用了逆序遍历有序数列，相较于顺序遍历会稍显繁琐，但当数列本身已近排序状态效率会更高。

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
 package main

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

func main() {
	for i := 1; i < len(ns); i++ {
		for j := i; j > 0; j-- {
			if ns[j] >= ns[j-1] {
				break
			}
			ns[j], ns[j-1] = ns[j-1], ns[j]
		}
	}
	return ns
}

插入排序时间复杂副O(N2)，空间复杂度O(1) ，稳定性：稳定

4.归并排序

  采用了分治和递归的思想，递归&分治-排序整个数列如同排序两个有序数列，依次执行这个过程直至排序末端的两个元素，再依次向上层输送排序好的两个子列进行排序直至整个数列有序
排序过程如下图

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 package main

func SortMerge(ns []int) []int {
	return sort(ns, 0, len(ns)-1)
}

func sort(ns []int, left, right int) []int {
	if left == right {
		return ns
	}

	mid := left + ((right - left) >> 1)
	ns = sort(ns, left, mid)
	ns = sort(ns, mid+1, right)
	return merge(ns, left, mid, right)
}

func merge(ns []int, left, mid, right int) []int {
	i, i1, i2 := 0, left, mid+1
	tmp := make([]int, right-left+1)
	for {
		if i1 > mid || i2 > right {
			break
		}

		if ns[i1] < ns[i2] {
			tmp[i] = ns[i1]
			i1++
		} else {
			tmp[i] = ns[i2]
			i2++
		}
		i++
	}

	for j := i1; j <= mid; j++ {
		tmp[i] = ns[j]
		i++
	}

	for j := i2; j <= right; j++ {
		tmp[i] = ns[j]
		i++
	}

	for i := 0; i < right-left+1; i++ {
		ns[i+left] = tmp[i]
	}

	return ns
}

func main() {
	ns := []int{5, 2, 4, 6, 1, 3}
	ns = SortMerge(ns)
	fmt.Println(ns)
}

归并排序时间复杂副O(NLgN)，空间复杂度O(N) ，稳定性：稳定

6.快速排序

  选一基准元素，依次将剩余元素中小于该基准元素的值放置其左侧，大于等于该基准元素的值放置其右侧；然后，取基准元素的前半部分和后半部分分别进行同样的处理；以此类推，直至各子序列剩余一个元素时，即排序完成

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
42
43
44
45
46
47
48
49
50
 package main

func SortFast(ns []int) []int {
	return sort1(ns, 0, len(ns)-1)
}

func sort(ns []int, left, right int) []int {
	if left >= right {
		return ns
	}

	ns, index := adjust(ns, left, right)
	ns = sort(ns, left, index-1)
	ns = sort(ns, index+1, right)
	return ns
}

func adjust(ns []int, left, right int) ([]int, int) {
	//保存基准key, 左边留出一个空位
	key := ns[left]
	for left < right {
		//从右边开始找第一个小于key的,放左边空位, 右边留出一个空位
		for left < right && ns[right] >= key {
			right--
		}
		if left < right {
			ns[left] = ns[right]
			left++
		}

		//从左边开始找第一个大于key的,放右边空位, 左边留出一个空位
		for left < right && ns[left] <= key {
			left++
		}
		if left < right {
			ns[right] = ns[left]
			right--
		}
	}

	//此时left=right
	ns[left] = key
	return ns, left
}

func main() {
	ns := []int{5, 2, 4, 6, 1, 3}
	ns = SortFast(ns)
	fmt.Println(ns)
}

快速排序时间复杂副O(NLgN)，空间复杂度O(1) ，稳定性：不稳定