Go 实现常用的五种算法排序

In |

WechatIMG57.jpeg

冒泡排序

  • 介绍

从第一个数据开始，依次比较相邻元素的大小。如果前者大于后者，则进行交换操作，把大的元素往后交换。通过多轮迭代，直到没有交换操作为止。

  • 图解

冒泡排序.gif

  • 创建 bubble.go 内容如下：
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
package main

import (
	"fmt"
	"encoding/json"
)

func main() {
	arr := [5]int{ 29,10,14,37,15 }
	str,err := json.Marshal(arr)
    if err != nil {
        panic(err)
    }
	fmt.Printf("原始数据：%s\n",string(str))
	for i := 0 ;i < len(arr); i++ {
		for j := i+1 ;j < len(arr); j++ {
			if arr[i] > arr[j] {
				var temp = arr[j]
				arr[j] = arr[i]
				arr[i] = temp
			} 
		}
	}
	bubbleStr,err := json.Marshal(arr)
    if err != nil {
        panic(err)
    }
	fmt.Printf("冒泡排序：%s",string(bubbleStr))
}
  • 执行
1
2
3
$ go run bubble.go
原始数据：[29,10,14,37,15]
冒泡排序：[10,14,15,29,37]

插入排序

  • 介绍

选取未排序的元素，插入到已排序区间的合适位置，直到未排序区间为空。

  • 图解

插入排序.gif

  • 创建 insert.go 内容如下：
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 main

import (
    "fmt"
    "encoding/json"
)

func main() {
    arr := [5]int{ 29,10,14,37,15 }
    str,err := json.Marshal(arr)
    if err != nil {
        panic(err)
    }
    fmt.Printf("原始数据：%s\n",string(str))
    
    var i = 1
    for ;i < len(arr); i++ {
        var temp = arr[i]
        var j = i - 1
        for ; j >= 0; j-- {
            if arr[j] > temp {
                arr[j + 1] = arr[j]
            } else {
                break
            }
        }
        arr[j + 1] = temp
    }

    bubbleStr,err := json.Marshal(arr)
    if err != nil {
        panic(err)
    }
    fmt.Printf("插入排序：%s",string(bubbleStr))
}
  • 执行
1
2
3
$ go run insert.go
原始数据：[29,10,14,37,15]
插入排序：[10,14,15,29,37]

归并排序

  • 介绍

归并排序的原理其实就是分治法（二分法）。它采用了二分的迭代方式，首先将数组不断地二分，直到最后每个部分只包含 1 个数据。然后再对每个部分分别进行排序，最后将排序好的相邻的两部分合并在一起，这样整个数组就有序了。

  • 图解

归并排序.gif

  • 创建 merge.go 内容如下：
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
package main

import (
	"fmt"
	"encoding/json"
)

func customMergeSort(a []int, start int, end int) {
	if start < end {
		var mid = (start + end) / 2;
		// 对左侧子序列进行递归排序
		customMergeSort(a, start, mid);
		// // 对右侧子序列进行递归排序
		customMergeSort(a, mid+1, end);
		// // 合并
		customDoubleMerge(a, start, mid, end);
	}
}

func customDoubleMerge(arr []int, start int, mid int, end int){
    leftLen:=mid-start+1
    rightLen:=end-mid
 
    arrLeft:=make([]int,leftLen)
    for i:=0;i<leftLen;i++{
        arrLeft[i]=arr[start+i]
    }
 
    arrRight:=make([]int,rightLen)
    for j:=0;j<rightLen;j++{
        arrRight[j]=arr[mid+j+1]
    }
 
    i,j,k:=0,0,start
    for ;k<=end&&i<leftLen&&j<rightLen;k++{
        if arrLeft[i]<=arrRight[j]{
            arr[k]=arrLeft[i]
            i++
        }else{
            arr[k]=arrRight[j]
            j++
        }
    }
 
    for ;i<leftLen&&k<=end;k++{
        arr[k]=arrLeft[i]
        i++
    }
 
    for ;j<rightLen&&k<=end;k++{
        arr[k]=arrRight[j]
        j++
    }
}

func main() {
	arr := [5]int{ 29,10,14,37,15 }
	str,err := json.Marshal(arr)
	if err != nil {
		panic(err)
	}
	fmt.Printf("原始数据：%s\n",string(str))
	customMergeSort(arr, 0, len(arr)-1)
	mergeStr,err := json.Marshal(arr)
	if err != nil {
		panic(err)
	}
	fmt.Printf("归并排序：%s\n",string(mergeStr))
}
  • 执行
1
2
3
$ go run merge.go
原始数据：[29,10,14,37,15]
归并排序：[10,14,15,29,37]

快速排序

  • 介绍

快速排序法的原理也是分治法。它的每轮迭代，会选取数组中任意一个数据作为分区点，将小于它的元素放在它的左侧，大于它的放在它的右侧。再利用分治思想，继续分别对左右两侧进行同样的操作，直至每个区间缩小为 1，则完成排序。

  • 图解

快速排序.gif

  • 创建 quick.go 内容如下：
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
package main

import (
	"fmt"
	"encoding/json"
)

func customQuickSort(arr []int, start, end int) {
    if start < end {
        i, j := start, end
        key := arr[(start+end)/2]

        for i <= j {
            for arr[i] < key {
                i++
            }
            for arr[j] > key {
                j--
            }
            if i <= j {
                arr[i], arr[j] = arr[j], arr[i]
                i++
                j--
            }
        }

        if start < j {
            customQuickSort(arr, start, j)
        }
        if end > i {
            customQuickSort(arr, i, end)
        }
    }
}

func main() {
	arr := []int{ 29,10,14,37,15 }
	str,err := json.Marshal(arr)
	if err != nil {
		panic(err)
	}
	fmt.Printf("原始数据：%s\n",string(str))
	customQuickSort(arr, 0, len(arr)-1)
	quickStr,err := json.Marshal(arr)
	if err != nil {
		panic(err)
	}
	fmt.Printf("快速排序：%s\n",string(quickStr))
}
  • 执行
1
2
3
$ go run quick.go
原始数据：[29,10,14,37,15]
快速排序：[10,14,15,29,37]

选择排序

  • 介绍

每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

  • 图解

2022-11-03 10.19.45.gif

  • 创建 select.go 内容如下：
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
package main

import (
	"fmt"
	"encoding/json"
)

func main() {
	arr := [5]int{ 29,10,14,37,15 }
	str,err := json.Marshal(arr)
    if err != nil {
        panic(err)
    }
	fmt.Printf("原始数据：%s\n",string(str))
	for i := 0 ;i < len(arr); i++ {
		var minKey = i
		for j := i+1 ;j < len(arr); j++ {
			if arr[j]<=arr[minKey] {
				minKey = j 
			}
		}
		if minKey != i {
			var temp = arr[i]
			arr[i] = arr[minKey]
			arr[minKey] = temp
		} 
	}
	bubbleStr,err := json.Marshal(arr)
    if err != nil {
        panic(err)
    }
	fmt.Printf("选择排序：%s",string(bubbleStr))
}
  • 执行
1
2
3
$ go run select.go
原始数据：[29,10,14,37,15]
选择排序：[10,14,15,29,37]

关联

[[PHP 实现常用的五种算法排序]]

-------------本文结束感谢您的阅读-------------
0%