# Follow the bubble sorting of animation go data structure ＃ practical operation sharing of private items ＃

A drop in the universe 2022-01-26 15:00:03 阅读数:432

### Bubble sort

Bubble sort is the simplest exchange sort algorithm .

What exchange is ？ Exchange is to compare two by two , If the order is not satisfied, you can exchange positions . such as , We want to sort from small to large , Compare the values in two positions , If it's in reverse order, it's swapped , Make records with large keywords pop up like bubbles and put them at the end .

Repeat bubble sort several times , Finally, we get an ordered sequence .

The name of bubble sort comes from ： Elements with smaller values are like ” Bubble “ Gradually float to the top of the sequence .

#### thought

1. Given a N Array of elements , Bubble sort will ：

If the element size relationship is incorrect , Exchange these two numbers （ In this case a> b）,

1. Compare a pair of adjacent elements （a,b）,
2. Repeat step 1 and 2, Until we reach the end of the array （ The last pair is the （N-2） and （N-1） term , Because our array starts from zero ）
3. up to now , The largest element will be in the last position . Then we will N Reduce 1, And repeat the steps 1, until N = 1.

### The demo

Given an array ​​29, 10, 14, 37, 14, 48, 17​​ , The bubble sorted animation is shown below ：

### Code implementation


package
main

import
"fmt"

func
main() {

// index starts from 0

var
nums
= []
int{
29,
10,
14,
37,
14,
48,
17}

var
length
=
len(
nums)

fmt
.
Println(
" Original array ：",
nums)

bubbleSort(
nums,
length)

fmt
.
Print(
" After array sorting :")

for
i :
=
0;
i
<
length;
i
++ {

fmt
.
Printf(
"%d\t",
nums[
i])
}
}

func
bubbleSort(
nums []
int,
length
int) {

for
i :
=
0;
i
<
length
-
1;
i
++ {

for
j :
=
0;
j
<
length
-
i
-
1;
j
++ {

if
nums[
j]
>
nums[
j
+
1] {
// If big , In exchange for

var
temp
=
nums[
j]
// Temporary variables save the previous value

nums[
j]
=
nums[
j
+
1]

nums[
j
+
1]
=
temp
}
}
}
}

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.


Run the above code , You can see the result of sorting ：


[
Running]
go
run
"e:\Coding Workspaces\LearningGoTheEasiestWay\Go data structure \ Bubble sort \main.go"

Original array ： [
29
10
14
37
14
48
17]

After array sorting :
10
14
14
17
29
37
48

1.
2.
3.


### Optimization of bubble sort

A flag can be attached to improve the algorithm , During sorting , If there is no swap operation, it means that the sorting is completed . If the sequence is already ordered , You can end the algorithm by judging the flag .


func
bubbleSortImproved(
nums []
int,
length
int) {

swapped :
=
true

for
i :
=
0;
i
<
length
-
1
&&
swapped;
i
++ {

swapped
=
false

for
j :
=
0;
j
<
length
-
i
-
1;
j
++ {

if
nums[
j]
>
nums[
j
+
1] {
// If big , In exchange for

var
temp
=
nums[
j]
// Temporary variables save the previous value

nums[
j]
=
nums[
j
+
1]

nums[
j
+
1]
=
temp

swapped
=
true
}
}
}
}

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.


In the best case , The time complexity of the improved bubbling algorithm is .

### summary

The advantage of comparing other sorting algorithms is , It can detect whether the input sequence is already sorted .

The time complexity of bubble sort is （ Even in the best of circumstances ）, The space complexity is  .

Bubble sorting is also a stable algorithm .