记得上大学刚学编程时，书本上就教了最简单的2种排序算法：选择排序和冒泡排序。原理也很简单，但是后来毕业后，有一次面试要手写一下选择、冒泡排序算法，突然之间卡壳了，心里知道是 2 层 for 循环嵌套，但是提笔写确怎么也写不好，弄得十分尴尬。
后来仔细想想，还是没有彻底搞懂算法的核心思想，上学时都是死记硬背 2 层 for 循环：第 1 层 for 循环 i 从多少开始到多少停止，第 2 层 for 循环 j 从多少开始到多少停止。但是时间一长，压根就忘记了 i、j 分别表示什么，所以在此记录一下这些算法的核心思想，只要了解了核心思想，后面不管过多长时间，不管用什么语言，手写这些算法基本不会有什么障碍了，无非是调调边界的问题。
1. 冒泡排序（kotlin编写）
假设待排序数组为 [a₁, a₂, a₃, ..., aₙ] 共 n 个元素，从数组第 1 个元素 a₁ 开始，依次与其后面的元素进行比较，如果该元素比其后面的元素大，则交换数组里这 2 个位置的元素。这样第一轮比较完之后，数组里的 aₙ 肯定是数组里最大的元素。
第二轮比较时，我们继续从头开始比较，一直到 aₙ₋₁ 为止，这样2轮比较之后，我们已经把最大的前2个数据排到数组的最后2个位置了。再继续进行，总共要进行 n - 1 轮比较之后，整个数组就是一个有序数组了。
原理清楚之后，就是代码层面的问题了，我们只需要记住2点：
- 第一层 for 循环
i表示当前正处于第几轮比较冒泡之中，i是从 0 开始还是 1 开始都无所谓，但要记住总共有n - 1轮比较冒泡，也就是说i要循环n - 1次，记住这个就好了。还有人说为什么是n - 1次比较，举几个简单的例子一看就知道了。 - 第二层 for 循环表示比较冒泡的过程，比较冒泡都是从头开始，也就是说
j肯定是从 0 开始，那么循环到什么时候结束呢？这个就与第 1 层 for 循环的i有关了，第 1 轮我们需要将前 n - 1 个元素依次与其后面的比较，第 2 轮需要将前 n - 2 个元素依次与其后面的比较，理解这个就不难写了。
//冒泡排序
fun bubbleSort(array: IntArray?) {
array ?: return
if (array.isEmpty())
return
var n = array.size
// i 表示第几轮冒泡
for (i in 1 until n) {
//j 从0开始，依次与其后面的元素进行比较交换
for (j in 0 until n - i) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1)
}
}
}
}
private fun swap(array: IntArray, i: Int, j: Int) {
var tmp = array[i]
array[i] = array[j]
array[j] = tmp
}
在此基础上，我们还可以做一点优化。在第 2 层 for 循环里，如果前一轮比较冒泡结束之后，整个数组已经是有序的了，则在当前这轮比较冒泡时，肯定不会出现比较交换的情况。也就是说如果某轮比较冒泡结束后，发现在该轮中没有出现一次比较交换，我们就可以断定整个数组就已经是有序的了，可以直接跳出所有的循环了，只需要加一点判断即可：
fun bubbleSort(array: IntArray?) {
array ?: return
if (array.isEmpty())
return
var n = array.size
for (i in 1 until n) {
var flag = true
for (j in 0 until n - i) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1)
//发生了比较交换
flag = false
}
}
//说明这一轮冒泡没有发生过比较交换
if (flag)
break
}
}
空间复杂度：O(1)
最好情况时间复杂度：O(n)，如果数组直接是有序的，则比较完一轮之后就可结束循环了
最坏情况时间复杂度：O(n²)
平均情况时间复杂度：O(n²)
冒泡排序是稳定的，能够保持相等的元素在数组里的初始相对顺序。
2. 选择排序
将待排序数组分成 2 部分，第一部分是排好序的，第二部分是未排序的。初始时，排好序的元素个数为 0 ，每次从未排序的数组中选择出最小(或最大)的一个元素，放入到排好序的部分里，经过 n - 1 次选择，我们就能得到排好序的数组了，这就是选择排序名称的由来。
以数组 [a₁, a₂, a₃, ..., aₙ] 为例，第1次选择，从 [a₁...aₙ] 中选择最小的数放到 a₁ 处，第2次选择，从 [a₂...aₙ] 中选择最小的放到 a₂ 处，重复执行直到结束就排序完成。同样我们这样理解 2 层 for 循环的含义：
- 第一层 for 循环，表示当前进行第几轮选择，总共需要 n - 1 次。这与冒泡排序是不是很相似，本质上都是同一个意思，一个表示需要冒泡的轮数，一个表示需要选择的轮数，那么 for 循环中的
i从 0 开始还是从 1 开始，根本无所谓，只要记住循环次数是 n - 1 就行。 - 第
i轮选择时，数组的前 i - 1 个元素是有序的，所以我们需要从数组的第i个元素开始到结尾的所有数据中选择出最小的一个。那么第二层 for 循环j的起始值，就表示当前数组的第几个元素开始是未排好序的，循环到数组最后一个元素结束。
fun selectionSort(array: IntArray?) {
array ?: return
if (array.isEmpty())
return
//i表示在进行第几次选择，选择的最小数据放在未排序数组的头部
for (i in 0 until array.size - 1) {
//a[i]是第一个未排序元素，将其后面的所有元素与之比较，如果有比a[i]小的，则交换到 a[i] 的位置上
for (j in i + 1 until array.size) {
if (array[i] > array[j]) {
swap(array, i, j)
}
}
}
}
再重复一遍，不要纠结 i 是从 0 开始还是从 1 开始，其影响的无非就是 j 的起始值是要 +1 还是 -1 问题，举个简单例子看一下就清楚了，不要死记。
算法很简单，但是我们还能做优化。我们看到第二层 for 循环里，比较之后都有交换操作，但我们只需要找到最小的一个数做一次交换就可以了，根本没必要那么多的交换。所以，我们每次比较之后，只需要记录最小元素的索引即可，在这轮比较结束之后，做一次交换就 OK 了。
fun selectionSort(array: IntArray?) {
array ?: return
if (array.isEmpty())
return
for (i in 0 until array.size - 1) {
var min = i
for (j in i + 1 until array.size) {
if (array[min] > array[j]) {
min = j
}
}
swap(array, i, min)
}
}
空间复杂度：O(1)
时间复杂度：O(n²)
选择排序是不稳定的，例如数组：[5、2、5、1、4、8] 经过选择排序后，两个相同元素 5 的前后顺序会发生变化。
冒泡排序可以优化，而选择排序不管怎样，其时间复杂度总是为 O(n²)，并且不稳定，所以总体来说冒泡是比选择排序优秀的。
3. 插入排序
插入排序与选择排序类似，也是将待排序数组分成两组，一组是已排好的数据，一组是未排好的数据。一开始选择数组的第一个元素作为已排好序的数据，剩下的就是未排好序的数据了。接下来在未排好序的数据里选择一个元素，将其插入到已排好序的数据里，并且保证已排好序的数据一直都是有序的。重复这个过程，直到未排序的数据为空，排序就完成了。为什么叫插入排序，其实就是将未排好序的数据插入到已排好序的数据之中，这也是其名称的由来。
举个例子来看一下插入排序的过程，假设待排序数组为：[6, 5, 3, 4, 0]
插入排序.png
同样我们记住2点：
- 第一层 for 循环
i表示插入的次数，总共要进行 n - 1 次，同样i从0还是1开始都没关系。 - 第
i次选择时，我们需要将第i个元素插入到前面 i - 1 个有序数组中。第i个元素是待插入的元素，由于前 i - 1 个元素是相对有序的，我们从第 i - 1 个元素开始逆序从后往前，依次与待插入元素比较，如果待插入元素小则交换位置。相当于我们排队时，有一组队伍按身高已经排好队了，接着我们要新加入一个人时，我们从队伍的最后面开始依次比较，找到自己的位置后，自己后面的所有人都往后挪移了一个位置。
fun insertionSort(array: IntArray?) {
array ?: return
if (array.isEmpty())
return
//表示当前进行第几轮插入，共 n - 1 次插入，初始时 array[0] 是已排好序的数，因为单条数据肯定是排好序的嘛
for (i in 1 until array.size) {
//这是待插入的数据，array[0]...array[i - 1] 是排好序的
var target = array[i]
//插入比较的核心在此，将要插入的数据从已排序数据的逆序开始逐一比较，如果要插入的数据比之小则插入
for (j in i - 1 downTo 0) {
//从后往前，遇到比待插入数据大的数据，将其往后移动一位
//可对比选择冒泡，这里只是数据往后挪移，并没有直接交换，只是在循环结束的时候将待插入数据放在目标位置即可
if (array[j] > target) {
array[j + 1] = array[j]
if (j == 0) {
//处理好边界条件，发现自己是最小的数据
array[j] = target
}
} else {
//找到自己的位置了
array[j + 1] = target
break
}
}
}
}
空间复杂度：O(1)
时间复杂度：O(n²)
4. 三种排序方式比较
| 排序方式 | 是否稳定 | 空间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 |
|---|---|---|---|---|---|
| 冒泡排序 | 是 | O(1) | O(n) | O(n²) | O(n²) |
| 选择排序 | 否 | O(1) | O(n²) | O(n²) | O(n²) |
| 插入排序 | 是 | O(1) | O(n) | O(n²) | O(n²) |
这三种排序方式中，最差的是选择排序，最好的通常是插入排序。
此外，看起来冒泡排序与插入排序都差不多，但是实际上插入排序性能更好。冒泡排序的比较交换次数通常会比插入排序多，我们看第二层 for 循环就可知道，插入排序在找到待插入的位置之后，就立即结束了当前循环，并且比较交换的次数也会少，而冒泡排序通常需要循环完。除此之外，插入排序还有更加优化的算法希尔排序。希尔排序算法简单介绍：https://www.jianshu.com/p/a031e6c78cdb
网友评论