Golang数据结构与算法学习笔记

1
2
3
4
5

1 0 0 0 0
0 0 0 0 0
0 0 2 0 0
0 0 0 0 0
0 0 0 0 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
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

var (
    originalArray [10][10]int // 定义一个二维数组
    sparseArr     []ValueNode // 定义一个切片来存放所有的值
    newArray      [10][10]int // 解压缩之后的数组
)

// ValueNode 定义一个结构体，表示存放值的结构
type ValueNode struct {
    row int
    col int
    val int
}

func main() {
    // 先给二维数组赋值
    originalArray[3][3] = 3
    originalArray[4][4] = 4
    originalArray[5][5] = 5

    // 输出查看原始数组的值
    for _, v1 := range originalArray {
       for _, v2 := range v1 {
          fmt.Printf("%d  ", v2)
       }
       fmt.Println()
    }

    compressArray(originalArray) // 转为稀疏数组
    // 遍历压缩后的值
    for _, vNode := range sparseArr {
       fmt.Println(vNode.row, vNode.col, vNode.val)
    }

    decompressArray(sparseArr) // 将压缩矩阵解压
    // 遍历解压后的数组
    for _, v1 := range newArray {
       for _, v2 := range v1 {
          fmt.Printf("%d  ", v2)
       }
       fmt.Println()
    }

}

// 将数组压缩
func compressArray(originalArray [10][10]int) {
    // 转为稀疏数组
    // 思路：
    // 遍历originalArray，如果我们发现有一个元素的值不为0，创建一个node结构体。如何设计结构体呢？
    // 将其放入到对应的切片中即可。

    valNode := ValueNode{ // 创建一个valNode 值结点，记录元素的二维数组的规模(行、列、默认值)
       row: 11,
       col: 11,
       val: 0,
    }
    sparseArr = append(sparseArr, valNode) // 将数组的结构信息也存入sparseArr中

    for i, v1 := range originalArray {
       for j, v2 := range v1 {
          if v2 != 0 {
             valNode = ValueNode{
                row: i,
                col: j,
                val: v2,
             }
             sparseArr = append(sparseArr, valNode)
          }
       }
    }
}

// 将数组还原
func decompressArray(sparseArr []ValueNode) {
    for i, v := range sparseArr {
       if i != 0 { // 第一行的值舍弃
          newArray[v.row][v.col] = v.val // 给新数组赋值
       }
    }
}

 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

type Queue struct {
    maxSize int
    array   [5]int // 数组 ==> 模拟队列
    front   int    // 队首（但不包含）
    rear    int    // 队尾（包含）
}

func (queue *Queue) AddQueue(val int) (err error) {

    if queue.rear == queue.maxSize-1 { // 先判断队列是否已满
       return errors.New("queue full")
    }
    queue.rear++ // rear后移
    queue.array[queue.rear] = val
    return nil
}

func (queue *Queue) GetQueue() (val int, err error) {

    if queue.rear == queue.front { // 先判断队列是否为空
       return -1, errors.New("queue empty")
    }
    queue.front++
    val = queue.array[queue.front]
    return val, err
}

func (queue *Queue) ShowQueue() {
    for i := queue.front + 1; i <= queue.rear; i++ {
       fmt.Printf("array[%d]=%d\t", i, queue.array[i])
    }
    fmt.Println()
}

func main() {

    // 先创建一个队列
    queue := Queue{
       maxSize: 5,
       front:   -1,
       rear:    -1,
    }

    // 添加数据
    var key string
    var val int

    fmt.Println("1. 输入add 表示添加数据到队列")
    fmt.Println("2. 输入get 表示从队列中获取数据")
    fmt.Println("3. 输入show 表示显示队列")
    fmt.Println("4. 输入exit 表示退出")

    for {
       fmt.Printf("请输入指令：")

       if _, err := fmt.Scanln(&key); err != nil {
          panic(err)
       }

       keyMap := map[string]struct{}{"add": struct{}{}, "get": struct{}{}, "show": struct{}{}, "exit": struct{}{}}
       if _, exist := keyMap[key]; !exist { // 输入的指令不正确
          fmt.Println("请输入正确的指令（add/get/show/exit）！")
          continue
       }

       switch key {
       case "add":
          fmt.Printf("输入需要添加到队列的数据：")
          _, err := fmt.Scanln(&val)
          if err != nil {
             panic(err)
          }

          if err := queue.AddQueue(val); err != nil {
             fmt.Println(err.Error())
          } else {
             fmt.Println("加入队列成功！")
          }
       case "get":
          data, err := queue.GetQueue()
          if err != nil {
             fmt.Println(err.Error())
          } else {
             fmt.Printf("取出元素：%d\n", data)
          }
       case "show":
          fmt.Printf("当前队列为：")
          queue.ShowQueue()
       case "exit":
          os.Exit(0)
       }
    }
}

  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

type CircleQueue struct {
    maxSize int
    array   [5]int
    head    int // head指向下一个弹出元素的位置
    tail    int // tail指向下一个添加元素的位置
}

// Push 向队列中添加元素
func (queue *CircleQueue) Push(data int) (err error) {
    if (queue.tail+1)%queue.maxSize == queue.head { // 队列已满
       return errors.New("queue full")
    }
    queue.array[queue.tail] = data
    queue.tail = (queue.tail + 1) % queue.maxSize
    return
}

// Pop 从队列中弹出元素
func (queue *CircleQueue) Pop() (data int, err error) {
    if queue.head == queue.tail { // 队列为空
       return -1, errors.New("queue empty")
    }
    data = queue.array[queue.head]
    queue.head = (queue.head + 1) % queue.maxSize
    return data, nil
}

func (queue *CircleQueue) ShowCircleQueue() {
    queueLen := (queue.tail - queue.head + queue.maxSize) % queue.maxSize // 队列中元素个数
    if queueLen == 0 {
       fmt.Println("queue is empty")
       return
    }
    originalHead := queue.head
    for i := 1; i <= queueLen; i++ { // 遍历队列长度个元素
       fmt.Printf("array[%d]=%d\t", i, queue.array[originalHead])
       originalHead = (originalHead + 1) % queue.maxSize
    }
    fmt.Println()
}

func main() {

    // 先创建一个队列
    queue := CircleQueue{
       maxSize: 5,
       head:    0,
       tail:    0,
    }

    // 添加数据
    var key string
    var val int

    fmt.Println("1. 输入push 表示添加数据到队列")
    fmt.Println("2. 输入pop 表示从队列中获取数据")
    fmt.Println("3. 输入show 表示显示队列")
    fmt.Println("4. 输入exit 表示退出")

    for {
       fmt.Printf("请输入指令：")

       if _, err := fmt.Scanln(&key); err != nil {
          panic(err)
       }

       keyMap := map[string]struct{}{"pop": struct{}{}, "push": struct{}{}, "show": struct{}{}, "exit": struct{}{}}
       if _, exist := keyMap[key]; !exist { // 输入的指令不正确
          fmt.Println("请输入正确的指令（add/get/show/exit）！")
          continue
       }

       switch key {
       case "push":
          fmt.Printf("输入需要添加到队列的数据：")
          _, err := fmt.Scanln(&val)
          if err != nil {
             panic(err)
          }

          if err := queue.Push(val); err != nil {
             fmt.Println(err.Error())
          } else {
             fmt.Println("加入队列成功！")
          }
       case "pop":
          data, err := queue.Pop()
          if err != nil {
             fmt.Println(err.Error())
          } else {
             fmt.Printf("取出元素：%d\n", data)
          }
       case "show":
          fmt.Printf("当前队列为：")
          queue.ShowCircleQueue()
       case "exit":
          os.Exit(0)
       }
    }
}

1

arr = [1, 2, 3, 4, 5]

1

prefix_sum = [1, 3, 6, 10, 15]

1

subarray_sum = prefix_sum[3] - prefix_sum[0] = 10 - 1 = 9

 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

func main() {
    arr := []int{2, 3, 5, 1, 4} // 定义一个整数切片 arr
    help := make([]int, len(arr)) // 创建一个与 arr 长度相同的辅助切片 help
    smallSum := calcSmallSum(arr, help, 0, len(arr)-1) // 计算小和并存储在 smallSum 中
    fmt.Println(smallSum) // 打印小和
}

func calcSmallSum(arr, help []int, left, right int) int {
    if left >= right {
        return 0
    }
    middle := left + (right-left)>>1 // 计算中间位置的索引
    leftSmallSum := calcSmallSum(arr, help, left, middle) // 递归计算左半部分的小和
    rightSmallSum := calcSmallSum(arr, help, middle+1, right) // 递归计算右半部分的小和
    mergeSmallSum := merge(arr, help, left, middle, right) // 合并左右两部分并计算小和
    return leftSmallSum + rightSmallSum + mergeSmallSum // 返回总的小和
}

func merge(arr, help []int, left, middle, right int) int {
    ans := 0 // 初始化小和为0
    p1 := left // 左半部分起始索引
    p2 := middle + 1 // 右半部分起始索引
    i := left // 用于遍历 help 切片的索引

    for ; p1 <= middle && p2 <= right; i++ {
        if arr[p1] < arr[p2] { // 只有左组元素严格小于右组元素时，才执行以下操作
            ans += (right - p2 + 1) * arr[p1] // 计算小和并加到 ans 中
            help[i] = arr[p1] // 将较小的左组元素存储到 help 中
            p1++
        } else { // 当左组元素大于等于右组元素时，将右组元素存储到 help 中
            help[i] = arr[p2]
            p2++
        }
    }

    // 处理剩余的元素
    for ; p1 <= middle; i++ {
        help[i] = arr[p1]
        p1++
    }
    for ; p2 <= right; i++ {
        help[i] = arr[p2]
        p2++
    }

    // 将 help 中的元素复制回原数组 arr
    for i := left; i <= right; i++ {
        arr[i] = help[i]
    }

    return ans // 返回当前合并部分的小和
}

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

func main() {
    arr := []int{3, 1, 2, 8, 5, 2, 7, 1, 3, 6, 3}
    num := 3
    partition(arr, num)
    fmt.Println(arr)
}

func partition(arr []int, num int) {
    low, mid, high := 0, 0, len(arr)-1

    for mid <= high {
       if arr[mid] < num {
          arr[low], arr[mid] = arr[mid], arr[low]
          low++
          mid++
       } else if arr[mid] == num {
          mid++
       } else {
          arr[mid], arr[high] = arr[high], arr[mid]
          high--
       }
    }
}

 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

func main() {
	nums := []int{3, 2, 1, 5, 6, 4}
	k := 6
	result := findKthLargest(nums, k)
	fmt.Printf("第 %d 大的数是：%d\n", k, result)
}

func findKthLargest(nums []int, k int) int {
	return quickSelect(nums, 0, len(nums)-1, len(nums)-k)
}

func quickSelect(nums []int, left, right, index int) int {
	for {
		if left > right { // 遍历完了都没找到的情况
			return 0
		}
		pivotIndex := partition2(nums, left, right)
		if pivotIndex == index {
			return nums[pivotIndex]
		}
		if pivotIndex < index {
			left = pivotIndex + 1
		} else {
			right = pivotIndex - 1
		}
	}
}

func partition2(nums []int, left, right int) int {
	l := left
	r := right
	pivot := l + (r-l)>>1
	for {
		for nums[l] < nums[pivot] {
			l++
		}
		for nums[r] > nums[pivot] {
			r--
		}
		if l >= r {
			return r
		}
		nums[l], nums[r] = nums[r], nums[l]
		l++
		r--
	}
}

 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

type SingleLinkedList struct {
    id   int
    name string
    age  int
    next *SingleLinkedList // 指针，指向下一个元素
}

func (head *SingleLinkedList) InsertNode(newNode *SingleLinkedList) {
    tempNode := head
    for {
       if tempNode.next == nil { // 找到最后一个Node
          tempNode.next = newNode
          return
       }
       tempNode = tempNode.next
    }
}
func (head *SingleLinkedList) DeleteNode(id int) {
    exist := false
    tempNode := head
    if tempNode.next == nil { // 先判断链表是否为空，防止空指针异常
       fmt.Println("LinkedList is empty")
       return
    }

    for {
       if tempNode.next.id == id {
          exist = true
          break
       }
       tempNode = tempNode.next
       if tempNode.next == nil {
          break
       }
    }
    if exist {
       tempNode.next = tempNode.next.next
    } else {
       fmt.Printf("\nid=%d的元素不存在！\n", id)
    }
}

func (head *SingleLinkedList) GetAllNodes() {
    tempNode := head
    if tempNode.next == nil { // 先判断链表是否为空，防止空指针异常
       fmt.Println("\nLinkedList is empty")
       return
    }
    fmt.Println()
    for {
       tempNode = tempNode.next
       fmt.Printf("[%d %s %d] ---> ", tempNode.id, tempNode.name, tempNode.age)
       if tempNode.next == nil {
          return
       }
    }
}

func main() {

    head := &SingleLinkedList{} // 定义一个头结点

    elem01 := &SingleLinkedList{ // 创建一个结点
       id:   1,
       name: "Tom",
       age:  23,
    }

    elem02 := &SingleLinkedList{
       id:   2,
       name: "Jerry",
       age:  25,
    }
    elem03 := &SingleLinkedList{
       id:   3,
       name: "Tomas",
       age:  28,
    }

    head.InsertNode(elem01) // 插入结点
    head.InsertNode(elem02)
    head.InsertNode(elem03)

    head.GetAllNodes() // 获取所有结点信息
    head.DeleteNode(2) // 删除结点
    head.GetAllNodes()

}

  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
110
111
112
113
114
115
116

type DoubleLinkedList struct {
    id       int
    name     string
    age      int
    previous *DoubleLinkedList // 指向前一个元素
    next     *DoubleLinkedList // 指针，指向下一个元素
}

func (head *DoubleLinkedList) InsertNode(newNode *DoubleLinkedList) {
    tempNode := head
    for {
       if tempNode.next == nil { // 找到最后一个Node
          tempNode.next = newNode
          newNode.previous = tempNode
          return
       }
       tempNode = tempNode.next
    }
}
func (head *DoubleLinkedList) DeleteNode(id int) {
    exist := false
    tempNode := head
    if tempNode.next == nil { // 先判断链表是否为空，防止空指针异常
       fmt.Println("DoubleLinkedList is empty")
       return
    }

    for {
       tempNode = tempNode.next
       if tempNode.id == id {
          exist = true
          break
       }
       if tempNode.next == nil {
          break
       }
    }
    if exist {
       tempNode.previous.next = tempNode.next
       tempNode.next.previous = tempNode.previous
       //tempNode.next = nil  // 2023.10.11 这里到底需不需要写呢？
       //tempNode.previous = nil
    } else {
       fmt.Printf("\nid=%d的元素不存在！\n", id)
    }
}

func (head *DoubleLinkedList) GetAllNodes() {
    tempNode := head
    if tempNode.next == nil { // 先判断链表是否为空，防止空指针异常
       fmt.Println("\nDoubleLinkedList is empty")
       return
    }
    fmt.Println()
    for {
       tempNode = tempNode.next
       fmt.Printf("[%d %s %d] <---> ", tempNode.id, tempNode.name, tempNode.age)
       if tempNode.next == nil {
          return
       }
    }
}

func (head *DoubleLinkedList) GetReverseNodes() {
    tempNode := head
    if tempNode.next == nil { // 先判断链表是否为空，防止空指针异常
       fmt.Println("\nDoubleLinkedList is empty")
       return
    }
    fmt.Println()
    for { // 找到最后一个Node
       if tempNode.next == nil {
          break
       }
       tempNode = tempNode.next
    }
    for { // 向前遍历
       if tempNode.previous == nil {
          break
       }
       fmt.Printf("[%d %s %d] <---> ", tempNode.id, tempNode.name, tempNode.age)
       tempNode = tempNode.previous
    }
}
func main() {

    head := &DoubleLinkedList{} // 定义一个头结点

    elem01 := &DoubleLinkedList{ // 创建一个结点
       id:   1,
       name: "Tom",
       age:  23,
    }

    elem02 := &DoubleLinkedList{
       id:   2,
       name: "Jerry",
       age:  25,
    }
    elem03 := &DoubleLinkedList{
       id:   3,
       name: "Tomas",
       age:  28,
    }

    head.InsertNode(elem01) // 插入结点
    head.InsertNode(elem02)
    head.InsertNode(elem03)

    head.GetAllNodes()     // 获取所有结点信息
    head.GetReverseNodes() // 向前遍历结点

    head.DeleteNode(2) // 删除结点
    head.GetAllNodes()
    head.GetReverseNodes() // 向前遍历结点
}

 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

type JosephusRing struct {
	id   int
	next *JosephusRing
}

func InitRing(num int) *JosephusRing { // 指定成员的个数进行初始化环
	first := &JosephusRing{}
	last := &JosephusRing{}
	if num < 1 {
		fmt.Println("成员数量至少为1！")
		return nil
	}
	for i := 1; i <= num; i++ {
		rData := &JosephusRing{
			id: i,
		}
		if i == 1 { // 第一个成员
			first = rData     // first指向链表的第一个元素，此后就不再改变
			last = rData      // 通过移动last来实现链表元素的增长，初始值为第一个元素
			last.next = first // 将新加入的元素指向first
		} else {
			last.next = rData // 将新的元素加入链表，并将last指向新的元素
			rData.next = first
			last = rData
		}
	}
	return first
}

func GetRingElems(first *JosephusRing) {
	if first.next == nil {
		fmt.Println("链表为空，没有任何成员！")
		return
	}
	last := first
	fmt.Println()
	for {
		fmt.Printf("[id=%d]--->", last.id)
		if last.next == first { // 遍历到最后一个元素了
			break
		}
		last = last.next
	}
}

func PlayGame(first *JosephusRing, startNo int, countNo int) {
	if first.next == nil {
		fmt.Println("链表为空！")
		return
	}
	last := first // 需要一个last指针指向最后(也就是first之前的那个元素)，因为要删除first结点，必须要找打它的前一个结点
	for {         // 将last指向最后的元素
		if last.next == first {
			break
		}
		last = last.next
	}
	// 让first和last都移动startNo-1次（移动到起始位置）（因为startNo表示的是开始的编号，但first已经指向第1个元素了，所以只需要移动startNo-1次）
	for i := 1; i <= startNo-1; i++ {
		first = first.next
		last = last.next
	}
	// 游戏开始，开始数数（countNo）
	// first始终指向的是要删除的成员
	for {
		// 移动countNo-1次（因为成员自身也算一次）
		for i := 1; i <= countNo-1; i++ {
			first = first.next
			last = last.next
		}

		// 删除first指向的结点
		fmt.Printf("\nid=%d的元素被删除！", first.id)
		first = first.next
		last.next = first

		// 循环的终止条件：链表中只有一个元素（first=last）
		if last == first {
			break
		}
	}
	fmt.Printf("\nid=%d的元素被删除！", first.id)
}

func main() {
	first := InitRing(5)
	GetRingElems(first)
	PlayGame(first, 2, 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

import "fmt"

func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        // 对未排序部分的元素进行多次遍历
        for j := 0; j < n-i-1; j++ {
            // 如果当前元素大于下一个元素，交换它们的位置
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

func main() {
    // 待排序的切片
    arr := []int{64, 34, 25, 12, 22, 11, 90}

    fmt.Println("未排序的数组：", arr)
    bubbleSort(arr)
    fmt.Println("排序后的数组：", arr)
}

 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 main

import "fmt"

func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        // 假设当前元素是最小的
        minIndex := i

        // 在未排序部分中查找最小元素的索引
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }

        // 将找到的最小元素与当前元素交换位置
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}

func main() {
    // 待排序的切片
    arr := []int{64, 25, 12, 22, 11}

    fmt.Println("未排序的数组：", arr)
    selectionSort(arr)
    fmt.Println("排序后的数组：", arr)
}

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

func main() {
    arr := []int{3, 8, 1, 5, 4, 7, 6, 9, 2}
    result := SelectionSort(arr)
    fmt.Println(result)
}

func SelectionSort(arr []int) []int {
    newArr := arr
    for j := 0; j < len(arr)-1; j++ {
       //minArr := newArr[j] // 之前用了一个变量来存最小值，后面发现可以优化一下，只需要记录下标minIndex就可以了，所以将这里注释掉
       minIndex := j
       for i := j + 1; i < len(arr); i++ { // 找出最小值的下标
          if newArr[i] < newArr[minIndex] {
             minIndex = i // 更新minIndex
          }
       }
       newArr[minIndex], newArr[j] = newArr[j], newArr[minIndex]
    }
    return newArr
}

 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 main

import "fmt"

func insertionSort(arr []int) {
    n := len(arr)
    for i := 1; i < n; i++ {
        // 从第二个元素开始，将当前元素插入到已排序部分的合适位置
        current := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > current {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = current
    }
}

func main() {
    // 待排序的切片
    arr := []int{64, 34, 25, 12, 22, 11, 90}

    fmt.Println("未排序的数组：", arr)
    insertionSort(arr)
    fmt.Println("排序后的数组：", arr)
}

 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

package main

import "fmt"

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

    pivot := arr[0] // 选择第一个元素作为基准
    var left, right []int

    for i := 1; i < len(arr); i++ {
        if arr[i] < pivot {
            left = append(left, arr[i])
        } else {
            right = append(right, arr[i])
        }
    }

    left = quickSort(left)
    right = quickSort(right)

    return append(append(left, pivot), right...)
}

func main() {
    // 待排序的切片
    arr := []int{64, 34, 25, 12, 22, 11, 90}

    fmt.Println("未排序的数组：", arr)
    arr = quickSort(arr)
    fmt.Println("排序后的数组：", arr)
}

 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

func QuickSort2(low, high int, arr []int) {
    if low < high {
        pivotIndex := partition(low, high, arr) // 选择分区点并获取分区点的索引
		QuickSort2(low, pivotIndex, arr)        // 递归排序分区点左侧的子数组
		QuickSort2(pivotIndex+1, high, arr)     // 递归排序分区点右侧的子数组
    }
}

// partition 将数组分成两部分，左侧的元素都小于或等于基准元素，右侧的元素都大于基准元素。
// 这是快速排序算法中的关键步骤，它在原地（in-place）完成，不需要额外的内存空间。
func partition(low, high int, arr []int) int {
    pivot := arr[(low+high)/2] // 选择最中间的元素作为基准
    i, j := low, high

    for {
       for arr[i] < pivot {
          i++
       }
       for arr[j] > pivot {
          j--
       }
       if i >= j {
          return j  // 返回 j 的索引，它表示分区点的位置。分区点是基准元素在排序后应该处于的位置。
       }
       arr[i], arr[j] = arr[j], arr[i]
       i++
       j--
    }
}

 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

var numCount = 80000

func main() {
    var arr []int
    for i := 0; i < numCount; i++ {
       arr = append(arr, rand.Intn(numCount)) // 随机生成numCount个数字
    }

    start := time.Now().UnixMilli()
    BubbleSort(arr)
    end := time.Now().UnixMilli()
    fmt.Printf("冒泡排序耗时(ms)：%d\n", end-start)

    start = time.Now().UnixMilli()
    SelectionSort(arr)
    end = time.Now().UnixMilli()
    fmt.Printf("选择排序耗时(ms)：%d\n", end-start)

    start = time.Now().UnixMilli()
    InsertSort(arr)
    end = time.Now().UnixMilli()
    fmt.Printf("插入排序耗时(ms)：%d\n", end-start)

    start = time.Now().UnixMilli()
    QuickSort(arr)
    end = time.Now().UnixMilli()
    fmt.Printf("快速排序耗时(ms)：%d\n", end-start)
    
    start = time.Now().UnixMilli()
	QuickSort2(0, len(arr)-1, arr)
	end = time.Now().UnixMilli()
	fmt.Printf("改进快速排序耗时(ms)：%d\n", end-start)
}

1
2
3
4
5

冒泡排序耗时(ms)：9575
选择排序耗时(ms)：3458
插入排序耗时(ms)：0
快速排序耗时(ms)：56649
改进快速排序耗时(ms)：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

func main() {
    arr := []int{3, 8, 1, 5, 4, 7, 6, 9, 2}
    help := make([]int, len(arr))
    MergeSort(arr, help, 0, len(arr)-1)
    fmt.Println(arr)
}

func MergeSort(arr, help []int, left, right int) {
    if left >= right {
       return
    }

    middle := left + (right-left)>>1      // 求中点
    MergeSort(arr, help, left, middle)    // 左部分有序
    MergeSort(arr, help, middle+1, right) // 右部分有序

    Merge(arr, help, left, middle, right) // 将左右数组合并到help数组中（middle参数用来分割左右数组）
}

func Merge(arr, help []int, left, middle, right int) { // 左：left...middle，右：middle+1...right。help为辅助辅助，存放合并后的值。
    p1 := left
    p2 := middle + 1
    i := left // 两个数组中比较出来的数字，应该放在help数组中的位置
    for ; p1 <= middle && p2 <= right; i++ {
       if arr[p1] <= arr[p2] {
          help[i] = arr[p1]
          p1++
       } else {
          help[i] = arr[p2]
          p2++
       }
    }
    for ; p1 <= middle; i++ {  // 将p1或p2中剩下的元素添加到help数组中
       help[i] = arr[p1]
       p1++
    }
    for ; p2 <= right; i++ {
       help[i] = arr[p2]
       p2++
    }
    for i := left; i <= right; i++ {
       arr[i] = help[i]
    }
}

 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

func main() {
    arr := []int{3, 8, 1, 5, 4, 7, 6, 9, 2}
    sortedArr := mergeSort(arr)
    fmt.Println(sortedArr)
}

// mergeSort 使用非递归方式实现归并排序
func mergeSort(arr []int) []int {
    if len(arr) < 2 {
       return arr
    }

    n := len(arr)
    help := make([]int, n) // 辅助数组用于合并
    mergeSize := 1         // 初始化合并步长

    for mergeSize < n { // 当合并步长小于数组长度时，继续迭代
       for left := 0; left < n; left += 2 * mergeSize {
          middle := left + mergeSize - 1
          right := min(left+2*mergeSize-1, n-1) // 控制右边界不越界

          if middle < right { // 只有左侧和右侧都有元素时才进行合并
             merge(arr, help, left, middle, right)
          }
       }

       mergeSize *= 2        // 增加合并步长
       arr, help = help, arr // 交换arr和help以备下一轮合并
    }

    return arr
}

// merge 用于合并两个已排序的子数组
func merge(arr, help []int, left, middle, right int) {
    i, j, k := left, middle+1, left

    for i <= middle && j <= right {
       if arr[i] <= arr[j] {
          help[k] = arr[i]
          i++
       } else {
          help[k] = arr[j]
          j++
       }
       k++
    }

    for i <= middle {
       help[k] = arr[i]
       i++
       k++
    }

    for j <= right {
       help[k] = arr[j]
       j++
       k++
    }
}