Golang面试宝典——Go语言实现排序算法之冒泡排序

关于Golang面试宝典

最近几年，Go的热度持续飙升，国内外很多大公司都在大规模的使用Go。Google是Go语言诞生的地方，其他公司如Facebook、腾讯、阿里、字节跳动、百度、京东、小米等都在拥抱和转向Go。Go语言的开源项目也非常多，如kubernetes、docker、etcd。

随着市场对Go语言人才需求的增长，很多开发者都投入了Go语言的怀抱。本系列文章将以第一视角与大家一同开始Golang的面试之路，希望大家能够有所收获，拿下心仪的offer。

Go语言实现冒泡排序（BubbleSort）

思想

比较相邻的元素，如果后者比前者小，则交换位置，这样可以保证每轮交换结束后，最大的数都在最后位置。

复杂度分析

时间复杂度

平均：O(n^2)

最好：数组本身就是有序的情况下，仅需比较一轮即可，时间复杂度为O(n)

最坏：数组为倒序的情况下，需要比较n-1轮，时间复杂度为o(n^2)

空间复杂度

因为在原数组进行修改，所以空间复杂度为O(1)

稳定性

稳定，因为当arr[i] == arr[i + 1]时，数组元素不会进行交换

代码实现

func BubbleSort(arr []int) {
	for i := len(arr) - 1; i >= 0; i-- {
		hasChange := false
		for j := 0; j < i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				hasChange = true
			}
		}
		if !hasChange {
			break
		}
	}
}