关于数据结构和算法:你以为只是简单的排序一

始终在犹豫要不要写排序的文章，因为真的烂大巷了。可是一旦细看，还真是很多值的思考的中央，所以还是抉择记录一下

以下残缺代码，均可从这里获取

https://github.com/Rain-Life/data-struct-by-go/tree/master/sort

排序算法效率剖析

理解如何剖析一个排序算法，能够帮忙咱们在理论工作场景中抉择适合的排序算法，比方，如果排序的数据比拟少，能够抉择冒泡或插入排序，如果排序的数据量较大，抉择归并或疾速排序，尽管它们两两的工夫复杂度是雷同的，然而还是有很大的区别的，下边会对它们做比照

排序算法执行效率

个别剖析一个排序算法的复杂度，咱们都是去剖析它的工夫复杂度，工夫复杂度反馈的是数据规模 n 很大的时候的一个增长趋势。所以，通常在剖析工夫复杂度的时候会疏忽到 系数、常数、低阶。然而，在理论开发场景中，可能咱们排序的数据并不多，因而，在对排序算法进行剖析的时候，还是须要将系数、常数、低阶也思考进来

剖析一个排序算法的工夫复杂度的时候，通常会剖析它的 最好状况、最坏状况以及均匀状况下的工夫复杂度。因为对于要排序的数据，它的有序度，对排序算法的执行工夫是有影响的，所以，要想抉择最合适的排序算法，这些状况的工夫复杂度都应该思考到（其实不光是排序，在实现任何一个算法的时候，当有多种形式可供选择的时候，都应该剖析多重状况下的工夫复杂度）

下边要分享的三个排序算法都是基于比拟的排序算法，基于比拟的排序算法的在执行过程中，个别波及两种操作，一个是比拟大小，一个是数据交换。因而，在比照这几种排序算法的时候，比拟次数和挪动次数 也应该思考进去。这也是为什么基于比拟排序的算法，咱们通常不会抉择冒泡排序，而抉择插入排序

排序算法内存耗费

算法的内存耗费能够通过空间复杂度来掂量 。针对排序算法的空间复杂度，有一个新的概念是 原地排序 。原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。下边要分享的三种排序算法，都是原地排序算法

排序算法稳定性

只靠执行效率和内存耗费来掂量排序算法的好坏是不够的。针对排序算法，还有一个重要的度量指标，稳定性 。意思是， 如果待排序的序列中存在值相等的元素，通过排序之后，相等元素之间原有的先后顺序不变

如：1、8、6、5、5、7、2、3，依照大小排序之后是：1、2、3、5、5、6、7、8

这组数据里有两个 5。通过某种排序算法排序之后，如果两个 5 的前后程序没有扭转，那咱们就把这种排序算法叫作 稳固的排序算法 ；如果前后程序发生变化，那对应的排序算法就叫作 不稳固的排序算法

冒泡排序

冒泡排序优化

冒泡排序的实现思维，置信大家都十分的相熟了

每次冒泡操作都会对相邻的两个元素进行比拟，看是否满足大小关系要求。如果不满足就让它俩调换。一次冒泡会让至多一个元素挪动到它应该在的地位，反复 n 次，就实现了 n 个数据的排序工作

实际上，冒泡过程还能够优化。当某次冒泡操作曾经没有数据交换时，阐明曾经达到齐全有序，不必再继续执行后续的冒泡操作。如图

下边是优化后的代码：

func BubbleSort(arr []int) {
    flag := false
    n := len(arr)
    for i := 0; i < n; i++ {
        flag = false// 如果某一次冒泡，没有呈现数据交换，阐明曾经有序，不必再持续冒泡了
        for j := 0; j < n-i-1; j++ {if arr[j] > arr[j+1] {tmp := arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = tmp
                flag = true
            }
        }
        if !flag {break}
    }

    for _, v := range arr {fmt.Printf("%v\t", v)
    }
}

冒泡排序算法剖析

首先 冒泡排序是一个原地排序算法，因为冒泡排序只波及相邻数据的替换，须要常量级的长期空间，所以空间复杂度是 O(1)

在冒泡排序中，只有替换才能够扭转两个元素的前后程序。为了保障冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，咱们不做替换，雷同大小的数据在排序前后不会扭转程序，所以 冒泡排序是稳固的排序算法

在最好的状况下，也就是待排数据是齐全有序的，那只须要进行一次冒泡操作即可，所以 最好状况下的工夫复杂度是 O(n)

最坏状况下是待排数据是齐全无序的，这个时候就须要 n 次冒泡，所以 最坏状况下的工夫复杂度是 O(n^2)

均匀状况下的工夫复杂度的剖析波及比较复杂的推导，不是这里的重点（我也不会，手动狗头。如果你想理解，能够看这里），冒泡排序算法的均匀工夫复杂度是 O(n^2)

插入排序

插入排序思维

插入排序是如何来的？假如当初有一个有序的数组，让你往里边插入一个数据之后，放弃数组是有序的。咱们都会想到通过遍从来找到待插入数据的地位，而后进行数据的挪动。通过这种形式就能够保障这个数组有序。借鉴上边这种插入方法，于是就有了插入排序

插入排序的思维是：将待排序的数组分成两个区间，有序区和无序区。刚开始的时候，有序区只有第一个元素。插入排序的过程就是每次从无序区中取出一个元素，放入到有序区中对应的地位，保障插入到有序区中之后，有序区仍然是有序的。一直的反复这个过程，直到无序区为空

文字描述比拟形象，见下图（从小到大排序）

插入排序也是蕴含两种操作，一种是比拟，一种是挪动。下边是代码实现

func InsertSort(arr []int)  {if len(arr) <= 0 {fmt.Println("待排数据不非法")
    }
    n := len(arr)

    for i := 1; i < n; i++ {// i 是待排区的元素
        value := arr[i]
        j := i-1
        for ; j >= 0; j-- { // j 遍历的是已排区的每一个元素
            if arr[j] > value {arr[j+1] = arr[j] // 如果满足条件，将前一个值赋给后边这个
            } else {break}
        }
        arr[j+1] = value
    }

    for _, v := range arr {fmt.Printf("%v\t", v)
    }
}

插入排序算法剖析

插入排序也不须要额定的存储空间，空间复杂度是 O(1)，所以它是 原地排序算法

在插入排序中，对于值雷同的元素，咱们能够抉择将前面呈现的元素，插入到后面呈现元素的前面，这样就能够放弃原有的前后程序不变，所以插入排序是 稳固的排序算法

如果待排序的数据是齐全有序的，并不需要搬移任何数据。如果从尾到头在有序数据组外面查找插入地位，每次只须要比拟一个数据就能确定插入的地位。所以这种状况下，最好是工夫复杂度为 O(n)。留神，这里是从尾到头遍历曾经有序的数据

如果数组是倒序的，每次插入都相当于在数组的第一个地位插入新的数据，所以须要挪动大量的数据，所以 最坏状况工夫复杂度为 O(n^2)。均匀工夫复杂度也是 O(n^2)

抉择排序

抉择排序思维

抉择排序的思维和插入排序的思维有些相似，抉择排序是每次从无序区中抉择一个最小的元素放入到有序区中，具体如图：

代码实现如下

func SelectionSort(arr []int) {n := len(arr)
    if n <= 0 {fmt.Println("待排数据不非法")
    }

    for i := 0; i < n - 1; i++ {
        for j := i+1; j < n ; j++ {if arr[i] > arr[j] {arr[i],arr[j] = arr[j], arr[i]
            }
        }
    }

    for _, v := range arr {fmt.Printf("%v\t", v)
    }
}

抉择排序算法剖析

抉择排序的空间复杂度也是 O(1)，是原地排序算法。抉择排序的最好状况和最坏状况的工夫复杂度都是 O(n^2)，这个很简略，看一下它的执行过程就晓得了

抉择排序不是一个稳固排序，抉择排序每次都要找残余未排序元素中的最小值，并和后面的元素替换地位，这样毁坏了稳定性

比方 7，3，5，7，1，9 这样一组数据，应用抉择排序算法来排序的话，第一次找到最小元素 1，与第一个 7 替换地位，那第一个 7 和两头的 7 程序就变了，所以就不稳固了

这样一看，抉择排序和前边两个排序算法相比就差一些了

三种排序算法比照

这里就先不提抉择排序了，因为和前两种相比，它显著逊色一些

冒泡排序不管怎么优化，元素替换的次数是一个固定值。插入排序是同样的，不管怎么优化，元素挪动的次数也是一个固定值。然而，从冒泡和插入排序的代码上看，冒泡排序的数据交换次数比插入排序要简单，冒泡排序须要 3 个赋值操作，而插入排序只须要 1 个

冒泡排序的替换操作
if arr[j] > arr[j+1] {tmp := arr[j]
    arr[j] = arr[j+1]
    arr[j+1] = tmp
    flag = true
}

抉择排序的替换操作
if arr[j] > value {arr[j+1] = arr[j]
}

假如把一次赋值操作的工夫算作一个单位工夫，那冒泡排序的替换操作须要 3 个单位工夫，而插入排序只须要 1 个单位工夫

如果须要排序的数据比拟少，可能这样的差异能够忽略不计，然而数据多起来之后，插入排序节俭的工夫还是比拟显著的

这三种工夫复杂度为 O(n2) 的排序算法中，冒泡排序、抉择排序，可能就纯正停留在实践的层面了，学习的目标也只是为了开辟思维，理论开发中利用并不多，然而插入排序还是挺有用的。有些编程语言中的排序函数的实现原理会用到插入排序算法