什么是冒泡排序
冒泡排序是一种稳定的简单的排序算法。
它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
如果上面说的不太明白的话,那请移步一篇老文章:http://www.haodaquan.com/44 相信聪明的你肯定能看明白,这里不做赘述了。
时间复杂度
O(n²)
golang实现冒泡排序
先来一个简单直观的写法:
/************************************************************
** @Description: bubble_sort
** @Author: haodaquan
** @Date: 2018-08-29 22:01
** @Last Modified by: haodaquan
** @Last Modified time: 2018-08-29 22:01
*************************************************************/
package bubble
func Sort(arr []int) []int {
len := len(arr)
if len < 2 {
return arr
}
for i := 1; i < len; i++ {
//内层循环相邻进行比较
for j := 0; j < len-1; j++ {
if arr[j] > arr[j+1] {
arr[j+1], arr[j] = arr[j], arr[j+1]
}
//fmt.Println(arr)
}
}
return arr
}
测试代码和性能测试代码已经放到了github上,地址:
https://github.com/george518/PPGo_algorithm/tree/master/sort/bubble
不妨一试。