SortAlgosKt(1) - 开个新坑吧，吧卟吧卟之冒泡排序

前言

作为一个天天摸鱼的打工人，最近接触到一些新的知识后，愈发认识到自己的菜了。前几天听别人讲到归并排序算法，一时没想起来是咋个思路来着（此处脸上泛红），跑去查了下才想起来。于是乎想开个新坑，介绍下各排序算法的思路并用 kotlin 一一实现这些排序算法，也借此机会巩固(学习)以前学的各种排序算法。(害，其实除了常用的排序算法，其它的在下都忘得差不多了……)

为啥第一篇选择冒泡排序呢，当然是因为冒泡最出名也最简单啦。

还是讲正题吧

本来想抄下百度百科介绍的冒泡排序的原理，但是感觉blahblah一长串讲得好复杂。我觉得简单来讲，冒泡排序就是每一趟排序把剩余数组里最大的那个数给找出来并放到相应位置。这个排序的过程很像气泡在水里的运动规律，一些大小不同的气泡并排躺在水底，最鼓（数值最大）的那个气泡肯定最先浮出水面。

光讲排序思想还是有些抽象，举个例子吧。

对array:[2,4,1,3]进行冒泡排序,如果当前元素比它后面那一个元素小，就执行交换。

第一趟排序:

①index=0，array[0]<array[1]，不执行任何操作，index++

②index=1，array[1]>array[2]，执行swap(1,2)，数组变成[2,1,4,3]，index++

③index=2，array[2]>array[3]，执行swap(2,3)，数组变成[2,1,3,4]，此时index+1==lastIndex，排序结束

第二趟排序：

①index=0，array[0]>array[1]，执行swap(0,1)，数组变成[1,2,3,4]，index++

②index=1，array[1]<array[2]，不执行任何操作，index++，此时index+1==上一趟排出的最大值的index，排序结束

第三趟排序：

①index=0，array[0]<array[1]，不执行任何操作，index++，此时index+1==上一趟排出的最大值的index，排序结束

一共要执行 n-1 趟排序( n 为数组长度)。都执行完毕后，当前数组即为有序的数组(虽然在本例中，第二趟排序结束后就已经是有序数组了，但算法还是要执行完第三趟)。

还不明白的童鞋(假装除了自己还会有别人看其实并没有)，可以试试看一下visualgo上面的图，应该也可以帮助理解。

算法实现

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

fun bubbleSort(nums: IntArray) {
    if (nums.size < 2) return
    //i表示第几趟排序
    for (i in 0 until nums.lastIndex - 1) {
        //j表示这趟排序遍历的索引位置
        for (j in 0 until nums.lastIndex - i) {
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1)
            }
        }
    }
}

/**
 * 之后其它的排序算法还会多次用到这个函数，所以直接抽出来变成一个单独的方法
 */
fun swap(nums: IntArray, i: Int, j: Int) {
    val temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
}

冒泡排序的实现使用了两层循环，所以时间复杂度为O(n^2)。

冒泡排序并未使用额外变量，所以空间复杂度为O(1)。

最后

这个系列应该不会咕咕咕(大概)，下一篇不出意外的话应该是选择排序。