三个时间复杂度为 O(n^2)的排序算法
排序有很多种，有些算法连名字都没听过，经过这段时间的刷题，我在这里总结一下几个常见的排序。我们都知道，算法是要考虑时间复杂度和空间复杂度的，所以我把算法分了三类，分别是时间复杂度是 O(n^2)、O(nlogn)、O(n)。注意这里的时间复杂度是指平均时间复杂度，关于最坏情况下的时间复杂度和最好情况下的时间复杂度在下面讨论。
对于排序算法，我们需要了解几个问题，算法的时间复杂度是多少？是否是原地排序算法？算法是否稳定？
时间复杂度我个人感觉可以理解为代码需要执行的次数，次数越多，所花费的时间就越长，当然是要在同等的数据量下比较。而原地排序的概念，可以扯到空间复杂度上面，原地排序，顾名思义就是直接在原数组进行排序操作，不需要申请额外的内存空间，空间复杂度为 O(1)。最后是算法是否稳定，何为稳定，当一个数组中有两个相等的数的时候，若排序之后，两个相等的数的顺序不会发生改变，这就是一个稳定的算法，反之就是不稳当的算法。
冒泡排序
顾名思义，就是要把待排序的元素一点点的往上替换，就好像气泡从水里浮起来一样。那它的具体实现过程呢？我们想象一组等待排序的元素，比如 2、5、1、7、0 这五个数字，如果我们要把它从小到大排序怎么办。
按照冒泡的算法，我们先把第一个和第二个两个相邻的数字，比较它们的大小，如果 2 比 5 大，就把 2 和 5 的位置互换，当然 2 肯定是比 5 小的，所以第一步不交换，第二步比较 5 和 1，这时 5 比 1 要大，所以把 5 和 1 的位置互换，重复这个操作，当第一次冒泡完成的时候，7 就已经排到了最后面。每次冒泡可以使得一个数字移动到它应该处于的位置上，重复 n 次就可以对 n 个数据完成排序，因此冒泡的时间复杂度是 O(n^2)。下面是演示
来看一下代码实现,我这里使用的是 go 语言，但是原理都是一样的,是不是很简单。
package main
import "fmt"
func main(){
a :=[]int{1,2,5,8,3,}
bubbleSort(a)
fmt.Println(a)
}
func bubbleSort(array []int) {//这里是实现冒泡排序的函数
n := len(array)
for i := 0; i < n; i++{
for j := 1; j < n; j++{
if array[j] < array[j-1] {
temp := array[j]
array[j] = array[j-1]
array[j-1] = temp
}
}
}
}当然，我们可以对冒泡排序做出一些优化，比如说当某一冒泡的时候没有元素移动，这时候就可以停止了，因为没有元素移动，说明已经是有序了。
可以看到，在代码中只申请了一个临时变量，交换过程都是直接在原数组操作，所以冒泡排序是一个原地排序算法，同时如果两个数相等的时候，是可以不交换位置的，因此是一个稳定的算法。
插入排序
上面的冒泡排序是对一个静态的数组排序，如果我们对一个已经有序的数组插入一个值，怎么能保持它还是有序的呢？这就要用到插入排序了。
插入排序的思想就是把待排序的元素分为已排序部分和未排序部分，每一次从未排序部分中取出一个值，插入到已排序部分中，最后未排序部分为空时，就完成了对元素的排序。看动图就容易理解了
代码实现
package main
import "fmt"
func main(){
a :=[]int{7,2,9,0,3,}
insertionSort(a)
fmt.Println(a)
}
func insertionSort(arr []int) []int {
for i := range arr {
preIndex := i - 1
current := arr[i]
for preIndex >= 0 && arr[preIndex] > current {
arr[preIndex+1] = arr[preIndex]
preIndex--
}
arr[preIndex+1] = current
}
return arr
}关于插入排序的时间复杂度，在最好情况下，向一个有序的数组中插入一个值，只需要遍历一次，所以时间复杂度是 O(n)，在最坏情况下，数组是倒序的，每次插入都相当于在数组的第一个位置插入，所以时间复杂度是 O(n^2)。那么平均时间复杂度呢？我们知道在一个数组中插入一个值的时间复杂度是 O(n)，那么插入 n 个数据就是 O(n^2)。
插入排序如同冒牌排序，也是一个原地排序算法，同样的可以不交换相等的数，因此也是一个稳定的算法。
选择排序
选择排序和插入排序类似，也是需要先划分出已排序部分和未排序部分，不过选择排序是每次从未排序部分中选择出最大或者最小的元素，然后插入到前面的已排序部分中。
在最好情况下，从第一个数据开始，每个都需要对数组进行遍历，即使我们知道这个数组已经是有序的，但是按照算法还是要逐个扫描，每向已排序部分插入一个值都要遍历一次，因此时间复杂度是 O(n^2)。同样的，不管是最坏情况，还是平均时间复杂度，都是 o(n^2)。
代码
package main
import "fmt"
func main(){
a :=[]int{7,2,9,0,3,}
selectionSort(a)
fmt.Println(a)
}
func selectionSort(array []int)[]int {
length := len(array)
if length < 2 {return array}
for i := 0; i < length; i++ {
for j := i; j < length; j++ {
if array[j] < array[i] {
temp := array[j]
array[j] = array[i]
array[i] = temp
}
}
}
return array
}选择排序是原地排序算法吗？当然是，和上面一样，同样是 o(1) 的空间复杂度，那选择排序是一个稳定的算法吗？这就不是了，它每次把最小的交换到前面去，那么被交换到后面的数字可能和中间有的数字是相等的，这时候它们的顺序就发生了改变。比如 3,4,6,3,2 这五个数字，第一轮会把第一个 3 和最后的 2 交换位置，这时两个 3 的顺序就发生改变了，所以是不稳定的算法。
插入排序和冒泡排序相比较呢？插入排序又要比冒泡排序更好一点，同样都是 O(n^2) 的时间复杂度和 O(1) 的空间复杂度，插入排序中赋值操作比冒泡中要少。数据少的时候差距不大，当数据量大的时候，多出来的这两步赋值操作消耗的时间就很明显了。
公众号：没有梦想的阿巧 后台回复 "群聊"，一起学习，一起进步
有疑问加站长微信联系（非本文作者）
