2017年Google I/O大会上,宣布在Android Studio IDE中支持Kotlin语言,开始成为Android开发的一级语言,但因为Java在Android开发领域做出的卓越贡献,业界并不看好这个新生儿,但是短短两年的时间,凭借比Java更安全,更简洁的多种优越性,Kotlin的受欢迎程度不断提升,在2019年Google I/O大会上宣布Kotlin将正式成为Android开发的首选语言,许多新的Jetpack API和功能都将首先在Kotlin上获得支持,Android开发将越来越多的以Kotlin为主。

今天(2020年3月31日)在Leet-code上的每日一题是一道排序数组的题目,想了半天感觉用Java写的话确实没有很大的挑战性,刚好今天尝试了在Android的一个App中使用了Kotlin作为开发语言打算写一个小型的App,所以就决定用Kotlin来写一写排序算法了。

本题你可以选择直接调用库函数来对序列进行排序,但意义不大。

——力扣官方题解

诚如官方所说,本次完全可以直接调用Java(Kotlin)提供的库函数对数组进行排序,但这并无丝毫的用处,其实这也像很多我们日常生活中所碰到的事情,不是说所有的事情我们都直接用别人做好的东西就可以了,因为这并没什么用,只有当我们自己亲自动手去做的时候,才知道事实的本质是怎样的,如此就不赘述了,开始使用Kotlin编写我们的排序算法吧。

经典中的经典:冒泡排序

相信很多人第一个接触的排序算法就是冒泡排序吧,也是很多程序员的启蒙,虽然说冒泡排序的时间和空间复杂度都不算是很优秀,但这确实一种传承,一种情怀。

  • 冒泡排序的基本思想是:外层循环每一次经过两两比较,把每一轮最大的元素放到了数组的末尾。

参考代码如下:

private fun bubbleSort(nums: IntArray): IntArray {
	//这里调用了IntArray.indices属性,其效果为返回一个IntRange类型的数据,用来进行遍历
	//reversed()方法可将其倒置,实现反向遍历
	for (i in nums.indices.reversed()) {
		//在每次遍历前,都假设数组已有序
		var sorted: Boolean = true
		//这里使用了until方法,创建了一个[0,i)的左闭右开的集合,可以遍历[0,i)之间的数
		for (j in0 until i) {
			if (nums[j] > nums[j + 1]) {
				val temp = nums[j]
	        	nums[j] = nums[j + 1]
	        	nums[j + 1] = temp
	        	sorted = false
        	}
        }
		//经过一次遍历后,如果sorted已然为true(即一次交换都未进行)
		//那么表示此数组已经有序,不需要再继续遍历
		if (sorted) {
            break
        }
    }
	return nums
}

让人思路最清晰的排序:选择排序

算法的世界里最多见的就是复杂多变、难以简单的用头脑想清楚的各种运算操作,但是选择排序却是让人思路最清晰的排序算法,或许只是我觉得。

它的主要思路就是,遍历数组,取出最小(大)的数和放到未排好序的地方去。

参考代码如下:

private fun selectSort(nums: IntArray): IntArray {
	//依旧使用indices属性来遍历数组
	for (i in nums.indices) {
        var minIndex: Int = i
        //创建一个[i+1,nums.size)的IntRange进行遍历,消除了越界异常
        for (j in i + 1 until nums.size) {
            //当前值比之前的最小值小时将当前的下标作为最小值的下标
            if (nums[j] < nums[minIndex]) {
                minIndex = j
            }
        }
        //遍历完成之后就取到了本轮遍历时的最小值,如果最小值已经不是当前的值时,就交换
        if (nums[minIndex] != nums[i]) {
            val temp = nums[i]
            nums[i] = nums[minIndex]
            nums[minIndex] = temp
        }
    }
    return nums
}

最“麻烦”的排序:插入排序

要说最“麻烦”的排序算法是什么,我想说估计是插入排序了,在最糟糕的情况下,每次排序甚至都要移动所有已经排序的数据。但是不得不说的是,在基本有序的数组中,插入排序的性能还算是可以。

插入排序的基本思想是将一个数组分为已排序和未排序两部分,并逐个从未排序的部分中取出数据,以正确的顺序插入到已排序的部分中。

参考代码:

private fun insertSort(nums: IntArray): IntArray {
    //当数据只有一个时,则可直接将其视为排好序,所以可以直接从数组第二位(即下标1)开始遍历
    //所以此处使用了1 until nums.size
    for (i in1 until nums.size) {
        //设定最小值为nums[i]
        val temp: Int = nums[i]
        var suitableLocation: Int = i
        //循环遍历i之前的数据
        for (j in IntRange(0, i - 1).reversed()) {
            //如果遍历到的值小于或等于当前temp的值,说明i位置上的数据已经到达了合适的地方
            //反之如果遍历到的某个值大于当前temp的值,说明i位置上的数据还需要往前移动,则将当前遍历到的值向后移动
            if (nums[j] <= temp) {
                break
            } else {
                nums[j + 1] = nums[j]
                suitableLocation = j
            }
        }
        //当本次循环结束时,判断下标是否还等于i,如果不等于,则代表需要交换位置
        if (suitableLocation != i) {
            nums[suitableLocation] = temp
        }
    }
    return nums
}

分而治之:归并排序

主要是借助额外空间,合并两个有序数组,得到更长的有序数组。

归并排序是基于递归的算法,也是分治思想在排序算法中的一种体现。

/**
 * 归并排序
 * @param nums 原数组
 * @param left 区间左值
 * @param right 区间右值
 * @param temp 用作合并两个数组时的缓存数据的数组,避免重复创建temp数组
 */
private fun mergeSort(nums: IntArray, left: Int, right: Int) {
    if (right <= left) {
        return
    }
    val mid = left + (right - left) / 2
    mergeSort(nums, left, mid)
    mergeSort(nums, mid + 1, right)
    if (nums[mid] > nums[mid + 1]) {
        mergeTwoUnorderedArrays(nums, left, mid, right)
    }
}

/**
 * 合并两段区间,这里使用了类似插入排序的方式,当然也有别的方法
 */
private fun mergeTwoUnorderedArrays(nums: IntArray, left: Int, mid: Int, right: Int) {
    for (i in (mid + 1)..right) {
        val temp = nums[i]
        var index = i
        for (j in (i - 1) downTo left) {
            if (nums[j] > temp) {
                nums[j + 1] = nums[j]
                index = j
            } else {
                break
            }
        }
        if (index != i) {
            start = index
            nums[index] = temp
        }
    }
}

左右群臣:快速排序

快速排序算法不得不说是一个重中之重,很多面试都会提到,而快速排序的主要思想就是,选定一个值,然后将数组中所有比该值小(大)的数放在一边,而大(小)的放在另一边,然后再分别说两边做同样的操作,直到数组有序,就好像是古代群臣围绕帝王左右排座次一样。

private val insertionSortDecision = 7
private fun quickSort(nums: IntArray, left: Int, right: Int) {
    //当区间长度小于insertionSortDecision时使用插入排序
    //已经排好序则直接返回,归并排序中也可以使用
    if (right - left <= insertionSortDecision) {
        insertSort(nums, left, right)
        return
    }
    //也可以选择区间中只含有一个元素时返回
    /*if (right - left < 1) {
    	return
    }*/
    //将数组分成两个区域并按大小分区,返回基准点所在位置
    val pIndex: Int = splitArray(nums, left, right)
    quickSort(nums, left, pIndex - 1)
    quickSort(nums, pIndex + 1, right)
}

private fun splitArray(nums: IntArray, left: Int, right: Int): Int {
    //首先在[left,right]随机一个index
    val randomIndex: Int = Random.nextInt(left..right)
    //将randomIndex位置上的数据和left位置上的数据调换位置
    swap(nums, left, randomIndex)
    var pIndex: Int = left
    for (i in (left + 1)..right) {
        if (nums[i] < nums[pIndex]) {
            swap(nums, pIndex, pIndex + 1)
            swap(nums, pIndex, i)
            pIndex++
        }
    }
    return pIndex
}

private fun insertSort(nums: IntArray, left: Int, right: Int) {
    for (i in (left + 1)..right) {
        var index = i
        val temp = nums[i]
        for (j in (i - 1) downTo left) {
            if (nums[j] > temp) {
                nums[j + 1] = nums[j]
                index = j
            }
        }
        if (index != i) {
            nums[index] = temp
        }
    }
}

private fun swap(nums: IntArray, i: Int, j: Int) {
    val temp: Int = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
}

今天的分享先到此结束,本文的篇幅也是比较长了,其他的排序算法就等以后有机会再慢慢分享了。