O(n^2)

排序系列文章链接：

O(n^2) (Jul 16, 2021)
O(nlogn) (Jul 16, 2021)
O(n) (Jul 16, 2021)
二分查找 (Jul 16, 2021)

排序算法的分类:

排序算法	时间复杂度	是否基于比较	是否是原地排序	是否稳定
冒泡、插入、选择	O(n^2)	√	√	插入排序不稳定
快排、归并	O(nlogn)	√	归并排序不是	快排不稳定
桶、计数、基数	O(n)	×	×	√

原地排序 算法，就是特指空间复杂度是 O(1) 的排序算法。

如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变，就把这种排序算法叫作 稳定的排序算法，否则叫做 不稳定的排序算法。

冒泡排序(Bubble Sort)

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。
一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

func BubbleSort(a []int, n int) {
    if n <= 1 {
        return
    }
    for i := 0; i < n; i++ {
        // 提前退出标志
        flag := false
        for j := 0; j < n-i-1; j++ {
            if a[j] > a[j+1] {
                a[j], a[j+1] = a[j+1], a[j]
                //此次冒泡有数据交换
                flag = true
            }
        }
        // 如果没有交换数据，提前退出
        if !flag {
            break
        }
    }
}

冒泡排序是稳定的排序算法吗？

在冒泡排序中，只有交换才可以改变两个元素的前后顺序。
为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

冒泡排序的时间复杂度是多少？

最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)
而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n^2)。
平均时间复杂度：
- 对于包含 n 个数据的数组，这 n 个数据就有 n! 种排列方式。如果用概率论方法定量分析平均时间复杂度，涉及的数学推理和计算就会很复杂。
- 有序度是数组中具有有序关系的元素对的个数。逆序度是数组中具有无序关系的元素对的个数。
  - 对于一个倒序排列的数组，比如 6，5，4，3，2，1，有序度是 0；
  - 对于一个完全有序的数组，比如 1，2，3，4，5，6，有序度就是 n*(n-1)/2，也就是 15。我们把这种完全有序的数组的有序度叫作 满有序度。
- 公式：逆序度 = 满有序度 - 有序度
- 排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度
- 冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度就加 1。不管算法怎么改进，交换次数总是确定的，即为逆序度，也就是n*(n-1)/2–初始有序度。
- 对于包含 n 个数据的数组进行冒泡排序，平均交换次数是多少呢？
  - 最坏情况下，初始状态的有序度是 0，所以要进行 n*(n-1)/2 次交换。
  - 最好情况下，初始状态的有序度是 n*(n-1)/2，就不需要进行交换。
  - 我们可以取个中间值 n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。
- 平均交换次数是n*(n-1)/4，比较操作肯定要比交换操作多，而最坏情况时间复杂度为 O(n^2)，所以平均情况下的时间复杂度就是 O(n^2)。

插入排序

将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。
插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。
重复这个过程，直到未排序区间中元素为空，算法结束。

func InsertionSort(a []int, n int) {
    if n <= 1 {
        return
    }
    for i := 1; i < n; i++ {
        value := a[i]
        j := i - 1
        //查找要插入的位置并移动数据，
        //从尾到头遍历已经有序的数据，保证数组a是有序的时候，只需要做一次比较操作就知道要插入的位置了
        for ; j >= 0; j-- {
            if a[j] > value {
                a[j+1] = a[j]
            } else {
                break
            }
        }
        a[j+1] = value
    }
}

插入排序是稳定的排序算法吗？

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

插入排序的时间复杂度是多少？

最好情况下，要排序的数据已经是有序的了，而且是从尾到头遍历已经有序的数据，所以最好情况时间复杂度是 O(n)
而最坏的情况是，要排序的数据刚好是倒序排列的，每次插入都相当于在数组的第一个位置插入新的数据，所以最坏情况时间复杂度为 O(n^2)。
平均时间复杂度：在数组中插入一个数据的平均时间复杂度是O(n)，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度为 O(n^2)。

选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

func SelectionSort(a []int, n int) {
    if n <= 1 {
        return
    }
    for i := 0; i < n; i++ {
        // 查找最小值
        minIndex := i
        // 从头到尾遍历还未排序的元素，保证数组a是有序的时候，只需要做一次比较操作就知道最小的元素了。
        for j := i + 1; j < n; j++ {
            if a[j] < a[minIndex] {
                minIndex = j
            }
        }
        // 交换
        a[i], a[minIndex] = a[minIndex],a[i]

    }
}

选择排序是稳定的排序算法吗？

选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。所以选择排序是一种不稳定的排序算法。

选择排序的时间复杂度是多少？

最好情况下，要排序的数据已经是有序的了，而且是从头到尾遍历还未排序的元素，所以最好情况时间复杂度是 O(n)
而最坏的情况是，要排序的数据刚好是倒序排列的，每次插入都相当于将未排序区间的最后一个元素插入到已排好序区间的末尾，所以最坏情况时间复杂度为 O(n^2)。
平均时间复杂度：在数组中插入一个数据的平均时间复杂度是O(n)，对于选择排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度为 O(n^2)。

为什么插入排序要比冒泡排序更受欢迎呢？

从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂：

//冒泡排序中数据的交换操作：
if a[j] > a[j+1] {
    a[j], a[j+1] = a[j+1], a[j]
    //此次冒泡有数据交换
    flag = true
}

//插入排序中数据的移动操作：
if a[j] > value {
    a[j+1] = a[j]
} else {
    break
}