排序算法(上)

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

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

插入排序

两种实现方案,第一种方法是新建一个数组并按序排列,遍历原始数组复制元素到新的数组, 时间复杂度为 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
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
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)

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
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
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)
}