一、 冒泡排序

• 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。
• 稳定性：冒泡排序是稳定的排序算法。
• 空间复杂度：冒泡排序是原地排序算法。
• 时间复杂度：
  (1) 最好情况（满有序度）：O(n)。
  (2) 最坏情况（满逆序度）：O(n^2)。

冒泡排序图解

冒泡排序降序golang语言实现图

 func bubbleSort(array []int) {
  for i := 0; i < len(array)-1; i++ {
    fmt.Printf("第%d次循环:\n", i)
    for j := i + 1; j < len(array); j++ {
      fmt.Printf("数组array第%d个元素与第%d个元素比较\n", i, j)
if array[i] > array[j] {
array[i], array[j] = array[j], array[i]
}
fmt.Printf("第%d次冒泡结果: %v \n\n", i, array)
}
}

输出:
/**
冒泡排序
old array= [4 5 6 1 3 2]
第0次循环:
数组 array 第0个元素与第1个元素比较
数组 array 第0个元素与第2个元素比较
数组 array 第0个元素与第3个元素比较
数组 array 第0个元素与第4个元素比较
数组 array 第0个元素与第5个元素比较
第0次冒泡结果: [1 5 6 4 3 2]

第1次循环:
数组 array 第1个元素与第2个元素比较
数组 array 第1个元素与第3个元素比较
数组 array 第1个元素与第4个元素比较
数组 array 第1个元素与第5个元素比较
第1次冒泡结果: [1 2 6 5 4 3]

第2次循环:
数组 array 第2个元素与第3个元素比较
数组 array 第2个元素与第4个元素比较
数组 array 第2个元素与第5个元素比较
第2次冒泡结果: [1 2 3 6 5 4]

第3次循环:
数组 array 第3个元素与第4个元素比较
数组 array 第3个元素与第5个元素比较
第3次冒泡结果: [1 2 3 4 6 5]

第4次循环:
数组 array 第4个元素与第5个元素比较
第4次冒泡结果: [1 2 3 4 5 6]

new array= [1 2 3 4 5 6]

*/  

二、插入排序

• 插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素，即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置，直到未排序区间为空。
• 空间复杂度：插入排序是原地排序算法。
• 时间复杂度：
  (1) 最好情况：O(n)。
  (2) 最坏情况：O(n^2)。
  (3) 平均情况：O(n^2)（往数组中插入一个数的平均时间复杂度是O(n)，一共重复n次）。
• 稳定性：插入排序是稳定的排序算法。

插入排序图解

插入排序降序golang语言实现

 func InsertSort(array []int) {
  length := len(array)
  if length <= 1 {
return
}
for i := 1; i < length; i++ {
    //从第二个数开始，从左向右依次取数
tmp := array[i] 
    //下标从0开始，依次从左向右
j := i - 1
fmt.Printf("第%d次循环: i=%d j=%d\n", i, i, j)
//每次取到的数都跟左侧的数做比较
    //如果左侧的数比取的数大，就将左侧的数右移一位
    //直至左侧没有数字比取的数大为止
for ; j >= 0; j-- {
fmt.Printf("temp:array[%d]=%d array[%d]=%d",i,tmp,j,array[j])
if tmp < array[j] {
array[j+1] = array[j]
} else {
fmt.Println("break")
break
}
fmt.Println("数据移动", array, "j=", j, "i=", i)
}
fmt.Println("当前数组 ", array, "j=", j, "i=", i)
//将取到的数插入到不小于左侧数的位置
//array[j+1] = tmp
//数据未移动，不替换
if j+1 != i {
array[j+1] = tmp
}
fmt.Printf("第%d次循环结果%v\n\n", i, array)
}
}

输出:
/**
old array= [4 5 6 1 3 2]
第1次循环: i=1 j=0
 temp:array[1]=5 array[0]=4 break
当前数组  [4 5 6 1 3 2] j= 0 i= 1
第1次循环结果[4 5 6 1 3 2]

第2次循环: i=2 j=1
 temp:array[2]=6 array[1]=5 break
当前数组  [4 5 6 1 3 2] j= 1 i= 2
第2次循环结果[4 5 6 1 3 2]

第3次循环: i=3 j=2
 temp:array[3]=1 array[2]=6 数据移动 [4 5 6 6 3 2] j= 2 i= 3
 temp:array[3]=1 array[1]=5 数据移动 [4 5 5 6 3 2] j= 1 i= 3
 temp:array[3]=1 array[0]=4 数据移动 [4 4 5 6 3 2] j= 0 i= 3
当前数组  [4 4 5 6 3 2] j= -1 i= 3
第3次循环结果[1 4 5 6 3 2]

第4次循环: i=4 j=3
 temp:array[4]=3 array[3]=6 数据移动 [1 4 5 6 6 2] j= 3 i= 4
 temp:array[4]=3 array[2]=5 数据移动 [1 4 5 5 6 2] j= 2 i= 4
 temp:array[4]=3 array[1]=4 数据移动 [1 4 4 5 6 2] j= 1 i= 4
 temp:array[4]=3 array[0]=1 break
当前数组  [1 4 4 5 6 2] j= 0 i= 4
第4次循环结果[1 3 4 5 6 2]

第5次循环: i=5 j=4
 temp:array[5]=2 array[4]=6 数据移动 [1 3 4 5 6 6] j= 4 i= 5
 temp:array[5]=2 array[3]=5 数据移动 [1 3 4 5 5 6] j= 3 i= 5
 temp:array[5]=2 array[2]=4 数据移动 [1 3 4 4 5 6] j= 2 i= 5
 temp:array[5]=2 array[1]=3 数据移动 [1 3 3 4 5 6] j= 1 i= 5
 temp:array[5]=2 array[0]=1 break
当前数组  [1 3 3 4 5 6] j= 0 i= 5
第5次循环结果[1 2 3 4 5 6]
new array= [1 2 3 4 5 6]
*/  

三、选择排序

• 选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾，直到未排序区间为空。
• 空间复杂度：选择排序是原地排序算法。】
• 时间复杂度：（都是O(n^2)）
  (1) 最好情况：O(n^2)。
  (2) 最坏情况：O(n^2)。
  (3) 平均情况：O(n^2)。
• 稳定性：选择排序不是稳定的排序算法。

选择排序图解

选择排序降序golang语言实现

 func SelectSort(values []int) {
length := len(values)
if length <= 1 {
return
}
for i := 0; i < length; i++ {
    //初始的最小值位置从0开始，依次向右
min := i 
//从i右侧的所有元素中找出当前最小值所在的下标
for j := length - 1; j > i; j-- {
if values[j] < values[min] {
min = j
}
}
fmt.Printf("i:%d minIndex:%d\n", i, min)
//把每次找出来的最小值与之前的最小值做交换
values[i], values[min] = values[min], values[i]
fmt.Println(values)
}
}

输出：
/**
old array= [4 5 6 1 3 2]
i:0 minIndex:3
[1 5 6 4 3 2]
i:1 minIndex:5
[1 2 6 4 3 5]
i:2 minIndex:4
[1 2 3 4 6 5]
i:3 minIndex:3
[1 2 3 4 6 5]
i:4 minIndex:5
[1 2 3 4 5 6]
i:5 minIndex:5
[1 2 3 4 5 6]
new array= [1 2 3 4 5 6]
*/  

四、思考

• 选择排序和插入排序的时间复杂度相同，都是O(n^2)，在实际的软件开发中，为什么我们更倾向于使用插入排序而不是冒泡排序算法呢？
• 答：从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个，所以在对相同数组进行排序时，冒泡排序的运行时间理论上要长于插入排序。

下一节：

上一节：