Golang(二十一)[排序算法

1.简介

冒泡排序（Bubble Sort）是一种较为简单的排序算法，重复的走访要排序的数列，一次比较两个元素，如果顺序错误就交换，走访舒蕾的工作是重复的进行指导没有需要再交换的位置，如同水中的气泡最终上浮到顶端一样。
冒泡排序（Bubble Sort）还有一种优化算法，就是立一个flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。

2.原理

以升序排序为例

1. 比较相邻的元素，如果第一个比第二个大，就交换彼此；
2. 对每一对相邻元素做同样的工作，从开始第一对结尾的最后一对，此时，最后打的元素应该是最大的数； 针对所有元素重复以上步骤，除了最后一个；
3. 持续每次对越来越少的元素重复上面的步骤，知道没有任何一对数字需要比较。

3.操作规则

1. 外层控制行【控制比较次数】
2. 内层控制列【控制交换次数】
3. 相邻比大小
4. 规则交换值

4.Golang代码

1.升序

// 冒泡排序--升序
func BubbleSortAsc(array []int) {
	// 1.外层控制行[控制比较的次数]：减1的操作，因为是两两相比，所以比较的次数是len-1
	for i := 0; i < len(array)-1; i++ {
		// 2.内层控制列[控制交换的次数]:减i的操作，因为随着i的增加，j的上限在减少
		for j := 0; j < len(array)-1-i; j++ {
			// 3.相邻比大小
			if array[j] > array[j+1] {
				// 4.规则交换值
				array[j], array[j+1] = array[j+1], array[j]
			}
		}
	}
}

2.降序

// 冒泡排序--降序
func BubbleSortDesc(array []int) {
	// 1.外层控制行[控制比较的次数]：减1的操作，因为是两两相比，所以比较的次数是len-1
	for i := 0; i < len(array)-1; i++ {
		// 2.内层控制列[控制交换的次数]:减i的操作，因为随着i的增加，j的上限在减少
		for j := 0; j < len(array)-1-i; j++ {
			// 3.相邻比大小
			if array[j] < array[j+1] {
				// 4.规则交换值
				array[j], array[j+1] = array[j+1], array[j]
			}
		}
	}
}

3.测试

func main() {
	array := []int{1, 3, 5, 9, 10, 2, 0, 7, 8, 4}
	fmt.Println("原数据：", array)
	BubbleSortAsc(array)
	fmt.Println("冒泡升序：", array)
	BubbleSortDesc(array)
	fmt.Println("冒泡降序：", array)
}

4.完整代码

package main

import (
	"fmt"
)

// 冒泡排序--升序
func BubbleSortAsc(array []int) {
	// 1.外层控制行[控制比较的次数]：减1的操作，因为是两两相比，所以比较的次数是len-1
	for i := 0; i < len(array)-1; i++ {
		// 2.内层控制列[控制交换的次数]:减i的操作，因为随着i的增加，j的上限在减少
		for j := 0; j < len(array)-1-i; j++ {
			// 3.相邻比大小
			if array[j] > array[j+1] {
				// 4.规则交换值
				array[j], array[j+1] = array[j+1], array[j]
			}
		}
	}
}

// 冒泡排序--降序
func BubbleSortDesc(array []int) {
	// 1.外层控制行[控制比较的次数]：减1的操作，因为是两两相比，所以比较的次数是len-1
	for i := 0; i < len(array)-1; i++ {
		// 2.内层控制列[控制交换的次数]:减i的操作，因为随着i的增加，j的上限在减少
		for j := 0; j < len(array)-1-i; j++ {
			// 3.相邻比大小
			if array[j] < array[j+1] {
				// 4.规则交换值
				array[j], array[j+1] = array[j+1], array[j]
			}
		}
	}
}

func main() {
	array := []int{1, 3, 5, 9, 10, 2, 0, 7, 8, 4}
	fmt.Println("原数据：", array)
	BubbleSortAsc(array)
	fmt.Println("冒泡升序：", array)
	BubbleSortDesc(array)
	fmt.Println("冒泡降序：", array)
}

5.优化

优化：

1. 在 某些 数据元素已经有序的情况下，没必要进行操作，提高效率

1.原冒泡排序

操作次数统计count

package main

import (
	"fmt"
)

// 冒泡排序--升序
func BubbleSortAsc(array []int) {
	count := 0
	// 1.外层控制行[控制比较的次数]：减1的操作，因为是两两相比，所以比较的次数是len-1
	for i := 0; i < len(array)-1; i++ {
		// 2.内层控制列[控制交换的次数]:减i的操作，因为随着i的增加，j的上限在减少
		for j := 0; j < len(array)-1-i; j++ {
			count++
			// 3.相邻比大小
			if array[j] > array[j+1] {
				// 4.规则交换值
				array[j], array[j+1] = array[j+1], array[j]
			}
		}
	}
	fmt.Println("冒泡排序升序执行次数：", count)
}

// 冒泡排序--降序
func BubbleSortDesc(array []int) {
	count := 0
	// 1.外层控制行[控制比较的次数]：减1的操作，因为是两两相比，所以比较的次数是len-1
	for i := 0; i < len(array)-1; i++ {
		// 2.内层控制列[控制交换的次数]:减i的操作，因为随着i的增加，j的上限在减少
		for j := 0; j < len(array)-1-i; j++ {
			count++
			// 3.相邻比大小
			if array[j] < array[j+1] {
				// 4.规则交换值
				array[j], array[j+1] = array[j+1], array[j]
			}
		}
	}
	fmt.Println("冒泡排序降序执行次数：", count)
}

func main() {
	array := []int{1, 3, 5, 9, 10, 2, 0, 7, 8, 4}
	fmt.Println("原数据：", array)
	BubbleSortAsc(array)
	fmt.Println("冒泡升序：", array)
	BubbleSortDesc(array)
	fmt.Println("冒泡降序：", array)
}

原数据： [1 3 5 9 10 2 0 7 8 4]
冒泡排序升序执行次数： 45
冒泡升序： [0 1 2 3 4 5 7 8 9 10]
冒泡排序降序执行次数： 45
冒泡降序： [10 9 8 7 5 4 3 2 1 0]

2.优化后

package main

import (
	"fmt"
)

// 冒泡排序--升序
func BubbleSortAsc(array []int) {
	// 定义标记，如果已经连续，则不再执行
	doExec := false
	count := 0
	// 1.外层控制行[控制比较的次数]：减1的操作，因为是两两相比，所以比较的次数是len-1
	for i := 0; i < len(array)-1; i++ {
		// 2.内层控制列[控制交换的次数]:减i的操作，因为随着i的增加，j的上限在减少
		for j := 0; j < len(array)-1-i; j++ {
			count++
			// 3.相邻比大小
			if array[j] > array[j+1] {
				// 4.规则交换值
				array[j], array[j+1] = array[j+1], array[j]
				// 执行操作，置true
				doExec = true
			}
		}
		// 如果没有进行比较交换，则直接退出，不再执行
		if !doExec {
			break
		} else {
			//如果已经进行比较交换了，那么恢复默认标记，方便后续比较
			doExec = false
		}
	}
	fmt.Println("冒泡排序升序执行次数：", count)
}

// 冒泡排序--降序
func BubbleSortDesc(array []int) {
	// 定义标记，如果已经连续，则不再执行
	doExec := false
	count := 0
	// 1.外层控制行[控制比较的次数]：减1的操作，因为是两两相比，所以比较的次数是len-1
	for i := 0; i < len(array)-1; i++ {
		// 2.内层控制列[控制交换的次数]:减i的操作，因为随着i的增加，j的上限在减少
		for j := 0; j < len(array)-1-i; j++ {
			count++
			// 3.相邻比大小
			if array[j] < array[j+1] {
				// 4.规则交换值
				array[j], array[j+1] = array[j+1], array[j]
				// 执行操作，置true
				doExec = true
			}
		}
		// 如果没有进行比较交换，则直接退出，不再执行
		if !doExec {
			break
		} else {
			//如果已经进行比较交换了，那么恢复默认标记，方便后续比较
			doExec = false
		}
	}
	fmt.Println("冒泡排序降序执行次数：", count)
}

func main() {
	array := []int{1, 3, 5, 9, 10, 2, 0, 7, 8, 4}
	fmt.Println("原数据：", array)
	BubbleSortAsc(array)
	fmt.Println("冒泡升序：", array)
	BubbleSortDesc(array)
	fmt.Println("冒泡降序：", array)
}

原数据： [1 3 5 9 10 2 0 7 8 4]
冒泡排序升序执行次数： 42
冒泡升序： [0 1 2 3 4 5 7 8 9 10]
冒泡排序降序执行次数： 45
冒泡降序： [10 9 8 7 5 4 3 2 1 0]
同样的数据进行排序，执行的次数已经有了明显的优化