位置：首页-资讯-后端开发

go实现冒泡排序算法

2024-04-02 19:55

短信预约 -IT技能 免费直播动态提醒

1、基本思想

通过对待排序序列从后向前，依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素从后部移向前部，就像水底气泡一样逐渐向上冒。

通俗点说就是：数组中前一个元素和后一个元素进行比较如果大于或者小于前者就进行交换，最终返回最大或者最小都冒到数组的最后序列时间复杂度为O(n^2).

比较的次数为： $1+2+3+ ... + (N-1) = (\frac{N^{2}-N}{2})$

从比较次数上可以看出，是一个平方级别的时间复杂度；

冒泡排序算法是稳定的，如果两个相邻的元素相等，是不会交换的，可以保证了稳定性的要求。

2、算法步骤

例如数组

{23,45,13,67,35}

让前面的数和后面的数进行比较，如果前面的数大，则交换。

第一轮开始排序：

第一轮开始迭代，从第一个数开始，依次比较相邻的两个数，如果前一个数比后面一个数大，那么交换位置，直到处理最后一个数，最后一个数即为最大值。

第二轮开始排序：

第二轮开始迭代，重复上述步骤，得出倒数第二大的数；

第三轮开始排序：

第三轮开始迭代，重复上述操作，得到倒数第三大的值；

第四轮开始排序：

第四轮开始迭代，重复上述操作，得到倒数第四大的值；

3、算法实现

package  main
 
import "fmt"
 
func BubbleSort(arr []int)[]int{
	for i := 0; i<len(arr) - 1; i++{
		for j:= 0; j<len(arr)-1-i; j++{
			if arr[j] > arr[j+1]{
				arr[j],arr[j+1] = arr[j+1],arr[j]
			}
		}
	}
	return arr
}
 
func main(){
	arr := []int{23,45,13,67,35}
	fmt.Println(BubbleSort(arr))
}

结果展示：