冒泡排序

思路:从左向右每次两两比较相邻元素,如果前一个元素大于后一个元素,那么就交换这两个元素,一趟下来肯定有一个元素放到了最后的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func BubbleSort(nums []int) []int {
bubbleSort(nums)
return nums
}

func bubbleSort(nums []int) {
//从前往后进行交换,每次都会固定好后面的元素
for i := 0; i < len(nums)-1; i++ {
for j := 0; j < len(nums)-1-i; j++ {
//两两比较并交换
if nums[j] > nums[j+1] {
nums[j], nums[j+1] = nums[j+1], nums[j]
}
}
}
}

优化版本的冒泡排序

思路:前面的冒泡排序在数组已经有序的时候还仍然会比较,因此我们可以通过设置一个flag,如果某一轮没有交换操作,说明当前已经有序,后面的不需要继续比较和判断了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//改进版的冒泡排序:一旦某一趟不交换后面就直接退出
func BubbleSortV2(nums []int) []int {
bubbleSortV2(nums)
return nums
}

func bubbleSortV2(nums []int) {
flag := true
//从前往后进行交换,每次都会固定好后面的元素
for i := 0; i < len(nums)-1 && flag; i++ {
flag = false
for j := 0; j < len(nums)-1-i; j++ {
//两两比较并交换
if nums[j] > nums[j+1] {
nums[j], nums[j+1] = nums[j+1], nums[j]
flag = true
}
}
}
}

评论