排序算法 - 冒泡排序
冒泡排序(Bubble Sort)
类型:交换排序时间复杂度(最坏):O(n^2)
时间复杂度(最好):O(n)
时间复杂度(平均):O(n^2)
空间复杂度:O(1)
稳定性:稳定
冒泡排序通过依次比较两个相邻元素的值,将数值较大的元素移动至数列尾部,每一轮的比较都能将无序数列中的最大值元素选出并移动到队尾,循环执行便可将数列按由大到小的顺序排列出来。因值大于才会发生交换,故为稳定排序。
package main import ( "fmt" ) func main() { var arr = []int{1, 6, 2, 4, 5, 3, 7, 9, 8} BubbleSort(arr) fmt.Print("sorted: ", arr) } // 冒泡排序 func BubbleSort(arr []int) { length := len(arr) alreadyOrdered := true // 记录某次排序是否发生元素交换 // 最多需要 length-1 次外循环 for i := 0; i < length-1; i++ { // length-i 为待排序数列的长度 i 为有序数列的长度 for j := 0; j < (length-i)-1; j++ { if arr[j] > arr[j+1] { alreadyOrdered = false temp := arr[j] arr[j] = arr[j+1] arr[j+1] = temp } } // 如果某次排序没有发生交换说明已有序 if alreadyOrdered { break } } }
相关推荐
hang0 2020-08-16
风吹夏天 2020-07-07
小海 2020-06-25
清溪算法君老号 2020-06-06
wonner 2020-06-03
清溪算法君老号 2020-06-01
rein0 2020-04-18
baike 2020-02-16
ustbfym 2019-12-17
wuxiaosi0 2019-12-10
Broadview 2019-11-19
ustbfym 2019-11-04
大数据分析BDA 2019-04-24
鱼天翱 2019-07-01
rein0 2020-04-21
rein0 2019-12-20
RememberMePlease 2020-05-01
清溪算法君老号 2020-04-25