排序算法（上）

发表于 更新于

本文讨论关于数组排序算法的实现， 给定一个整形数组，按从小到大排列

常见的排序算法有：插入排序， 选择排序，冒泡排序，快速排序，归并排序等

插入排序

两种实现方案，第一种方法是新建一个数组并按序排列，遍历原始数组复制元素到新的数组， 时间复杂度为 O(n * n), 空间复杂度为O(n)， 同时为不稳定的排序; 另一种方式是在原地选择和排序，数组分为两部分，左边是已排序的部分，右边是带排序的部分，初始状态左侧为数组第一个元素，右侧为第二个元素之后的元素，从数组中第二个元素开始遍历， 依次插入左侧并排序， 时间复杂度为 O(n * n), 稳定排序

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package sort

// 插入排序
// v1: time O(n * n) space O(n)
func InsertSortArray1 (array []int, length int) []int {
	// 1. 创建一个新的数组
	// 2. 循环旧的数组数据并复制到插入到新数组的指定位置
	if length <= 1 {
		return array
	}

	times := 0

	newArray := make([]int, length, length)

	newArray[0] = array[0]

	for i := 1; i < length; i++ {
		index := 0

		for j := i-1; j >=0 ; j-- {

			times++

			if array[i] >= newArray[j] {
				index = j + 1

				break
			}

		}

		if index < i {
			for k:=i-1; k>=index; k-- {
				times++

				newArray[k + 1] = newArray[k]
			}
		}

		newArray[index] = array[i]
	}

	println("time O(", times, ")")

	return newArray
}

// v2 time o(n * n) space O(0)
func InsertSortArray2 ( array []int, len int) []int {
	// 原地交换数据
	if len <= 1 {
		return array
	}

	times := 0

	for i := 1; i< len; i++ {
		curr := array[i]
		j := i-1

		for ; j>=0; j-- {
			times++

			if array[j] > curr {
				array[j+1] = array[j]
			} else {
				break
			}
		}

		array[j+1] = curr
	}

	println("time O(", times, ")")

	return array
}

选择排序

遍历数组， 每次取剩下的元素中的最小的元素的下标， 如果找到了就和已排序的元素进行交换， 时间复杂度 O(n * n)

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

func SelectionSort1(arr []int, len int) {
	if len <=1 {
		return
	}

	times := 0

	for i:=0; i< len; i++ {
		minIndex := i

		for j:= i+1; j < len; j++ {

			times++

			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}

		arr[i], arr[minIndex] = arr[minIndex], arr[i]
	}

	println(times)
}

冒泡排序

比较相邻的数字，将大数字后移， 遍历完一轮右侧是最大的数字，然后在比较第0个元素到第n-1个元素，直到n=1, 时间复杂度： O(n * n)

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
package sort

func BubleSort(arr []int, len int) {
	if len <=1 {
		return
	}

	flag := false

	times := 0

	for i :=0; i< len; i++ {
		for j :=0; j< len-i-1; j++ {

			times++

			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]

				flag = true
			}
		}

		if !flag {
			break
		}
	}

	println("time:", times)
}```


### 快速排序
> 首先选择一个pivot, 一般选最后一个元素， 然后便利数据从start和end， 如果小于pivot， 那么交换正在比较的两个数据， 第一次对比完成后，pivot所在的索引左边都是小于pivot的数据，右侧都是大于pivot的数据， 然后分别对左侧和右侧数据进行排序， 直到start>=end. 时间复杂度O(logN)


```go
package sort

/*
排序过程：

j=0, 1, i=0 1
1      111 23 31 43  54 45
> i=1

j=1 111, i=1 1111
1      111    23 31 43  54 45

j=2 23, i=1 111
1      23    111 31 43  54 45
> i=2 111

j = 3   31
1      23   31 111 43  54 45
> i = 3 111

j = 4, 43
1      23   31 43 111  54 45
> i = 4 111

j = 5, 54
1      23   31 43 111  54 45
> i=4 111

1      23   31 43 45  54 111
> i =4, j =5

*/
func QuickSort(arr []int, len int) {
	separate(arr, 0, len-1)

	println("time O(", times, ")")
}

func separate(arr []int, start,end int) {
	if start >= end {
		return
	}

	i := partition(start, end, arr)

	separate(arr, start, i-1)
	separate(arr, i+1, end)
}

var times int = 0

func partition(start int, end int, arr []int) int {
	pivot := arr[end]

	i := start

	for j :=start; j< end; j++ {
		times++

		if arr[j] < pivot {
			if i != j {
				arr[i], arr[j] = arr[j], arr[i]
			}

			i++
		}
	}

	arr[i], arr[end] = arr[end], arr[i]

	return i
}

归并排序

将数据分成相等两部分（length / 2 = mid）， 分别对start到mid和mid到end进行排序， 然后在进行合并， 知道start>=end结束遍历， 时间复杂度O(logN), 空间复杂度O(N)

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
58
59
60
61
package sort

var exetimes int = 0

func MergeSort(arr []int, len int) {
	if len <=1 {
		return
	}

	sort(arr, 0, len-1)

	println("tims O(", exetimes, ")")
}

func sort(arr []int, start, end int) {
	if start >=end {
		return
	}

	mid := (start + end) /2

	sort(arr, start, mid)
	sort(arr, mid+1, end)
	merge(arr, start, mid, end)
}

func merge(arr []int, start, mid, end int) {
	temp := make([]int, end - start + 1)

	i := start
	j :=mid+1
	k := 0

	for ; i<=mid && j<= end; k++ {
		exetimes++

		if arr[i] > arr[j] {
			temp[k] = arr[j]
			j++
		} else {
			temp[k] = arr[i]
			i++
		}
	}

	for ;i<=mid;i++ {
		exetimes++

		temp[k] = arr[i]
		k++
	}

	for ;j<=end;j++ {
		exetimes++
		temp[k] = arr[j]
		k++
	}

	copy(arr[start:end+1], temp)
}