关于golang:冒泡选择插入排序

4次阅读

共计 2598 个字符，预计需要花费 7 分钟才能阅读完成。

三个工夫复杂度为 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)。上面是演示

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) 的空间复杂度，插入排序中赋值操作比冒泡中要少。数据少的时候差距不大，当数据量大的时候，多进去的这两步赋值操作耗费的工夫就很显著了。