golang 冒泡、选择、插入、快速排序法
个人学习笔记～
1. 冒泡排序
// @Author sunwenbo
// 2024/4/6 22:37
/*
1. 一共会经过arr.length -1 次的轮数比较，每一轮将会确认一个数的位置
2. 每一轮的比较次数逐渐的减少 [4,3,2,1]
3. 当发现前面的一个数比后面的一个数大的时候，就进行了交换
*/package mainimport "fmt"func bubbleSort(arr1 *[11]int) {fmt.Println("排序前arr=", (*arr1))//完成第一轮排序temp := 0 //临时变量 用作于交换for i := 0; i < len(arr1); i++ {for j := 0; j < len(arr1)-1; j++ {if (*arr1)[j] > (*arr1)[j+1] {temp = (*arr1)[j](*arr1)[j] = (*arr1)[j+1](*arr1)[j+1] = temp}}}}func main() {arr := [...]int{1, 4, 3, 11, 6, 8, 2, 9, 0, 5, 7}//外层控制行for i := 0; i < len(arr)-1; i++ {//内层控制列for j := 0; j < len(arr)-1; j++ {//比较两个相邻的元素 满足条件交换数据//升序使用大于号， 降序使用小于号if arr[j] > arr[j+1] {arr[j], arr[j+1] = arr[j+1], arr[j]}}}fmt.Println(arr)arr1 := [11]int{1, 4, 3, 11, 6, 8, 2, 9, 0, 5, 7}bubbleSort(&arr1)fmt.Println("排序后的arr1=", arr1)
}
2. 选择排序
// @Author sunwenbo
// 2024/4/6 21:49
package mainimport "fmt"/*
选择排序基本介绍选择式排序也属于内部排序法，是从预排序的数据中按指定的规则选出某一元素，经过和其他元素重整，再依原则交换位置后达到排序的目的
*/func selectSort(arr *[6]int) {for j := 0; j < len(arr)-1; j++ {min := arr[j]minIndex := jfor i := j + 1; i < len(arr); i++ {if min > arr[i] {min = arr[i]minIndex = i}}if minIndex != j {arr[minIndex], arr[j] = arr[j], arr[minIndex]}}
}func main() {// 定义数组,从小到大排arr := [6]int{10, 34, 19, 100, 80, 99}selectSort(&arr)fmt.Println("main函数")fmt.Println(arr)
}
3. 插入排序
// @Author sunwenbo
// 2024/4/7 18:37
package mainimport "fmt"/*
插入排序法介绍：插入式排序属于内部排序法，是对预排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的插入排序（insertion Sorting）的基本思想是：把N个待排序的元素堪称一个有序表和一个无序表，开始时有序表中包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中第一个元素，把它的排序码
依次与有序表元素的排序码进行比较，将它插入到有序表中的适当为止，使之成为新的有序表
*/func InsertSort(arr *[7]int) {for i := 1; i < len(arr); i++ {// 完成第一次，给第二个元素找到合适的位置并插入insertVal := arr[i]insertIndex := i - 1 //下标// 从大到小for insertIndex >= 0 && arr[insertIndex] < insertVal {arr[insertIndex+1] = arr[insertIndex] // 数据后移insertIndex--}// 插入if insertIndex+1 != i {arr[insertIndex+1] = insertVal}fmt.Printf("第%d次插入后 %v \n", i, *arr)}
}func main() {arr := [7]int{23, 0, 12, 56, 34, -1, 55}fmt.Println("原始数组=", arr)InsertSort(&arr)fmt.Println("main函数")fmt.Println(arr)
}
4. 快速排序
// @Author sunwenbo
// 2024/4/8 11:26
package mainimport "fmt"/*
快速排序法介绍：
快速排序(Quicksort)是对冒泡排序的一种改进。基本思想是：通过排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都要比另外一部分的数据都要小，
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据编程有序序列
*/
// 快速排序
// 1. left表示数组左边的下标
// 2. right 表示数组右边的下标
// 3. array 表示要排序的数组func QuickSort(left int, right int, array *[6]int) {l := leftr := right// pivot是中轴，支点pivot := array[(left+right)/2]temp := 0// for 循环的目标是将比pivot小的数放到左边，大的数放到右边for l < r {// 先从pivot 的左边找到大于等于pivot的值for array[l] < pivot {l++}// 从pivot的右边找到小于等于pivot的值for array[r] > pivot {r--}// l >= r 表明本次分解任务完成if l >= r {break}// 交换temp = array[l]array[l] = array[r]array[r] = temp// 优化if array[l] == pivot {r--}if array[r] == pivot {l++}}// 如果l==r,再移动一位就不要比较了if l == r {l++r--}// 向左递归if left < r {QuickSort(left, r, array)}// 向右递归if right > l {QuickSort(l, right, array)}
}func main() {arr := [6]int{-9, 78, 0, 23, -567, 70}// 调用快速排序QuickSort(0, len(arr)-1, &arr)fmt.Println("第一种方法排序后的数组:", arr)fmt.Println("###################")arr2 := []int{10, 7, 8, 9, 1, 5}n := len(arr2)quickSort(arr2, 0, n-1)fmt.Println("第二种方法排序后的数组:", arr2)
}// 快速排序函数
func quickSort(arr []int, low, high int) {if low < high {// 划分pivot := partition(arr, low, high)// 递归排序左右子数组quickSort(arr, low, pivot-1)quickSort(arr, pivot+1, high)}
}// 划分函数
func partition(arr []int, low, high int) int {pivot := arr[high] // 选择最后一个元素作为基准值i := low - 1 // i 为小于基准值的最后一个元素的索引for j := low; j < high; j++ {if arr[j] < pivot {i++// 将小于基准值的元素放到左边arr[i], arr[j] = arr[j], arr[i]}}// 将基准值放到正确的位置上arr[i+1], arr[high] = arr[high], arr[i+1]return i + 1
}