一、分类与性能

1.1、稳定排序和非稳定排序

简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。

1.2、内排序和外排序

在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；

在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。

1.3、算法的时间复杂度和空间复杂度

所谓算法的时间复杂度，是指执行算法所需要的计算工作量。

一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。

1.4、比较排序与非比较排序

比较排序：冒泡（交换）排序、插入排序、希尔排序、选择排序、归并排序

非比较排序：计数排序、桶排序、基数排序

二、八大排序算法实现

2.1、冒泡排序

算法思想简单描述：以升序为例说明，在要排序的一组数中，对当前还未排好序的范围内的全部数，从左到右对相邻的两个数依次进行比较和调整，让较大的数往右冒。

第1遍完：最后一个数就是最大的了。第2遍完：倒数第二个就是最大的了，

golang实现

2.2、选择法排序

算法思想简单描述：以升序为例说明，在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

选择排序是不稳定的。算法复杂度O(n2)------[n的平方]

每找一遍，就把最小的数放到了最前面。

第一遍：把第一个数当最小用下标min记录，后面每个数与第min号元素比较

第二遍：把第二个数当最小用下标min记录，后面每个数与第min号元素比较

golang实现

2.3、插入排序

算法思想简单描述：在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

插入排序是稳定排序。算法时间复杂度O(n2)-- [n的平方]

golang实现

2.4、快速排序

快速排序是已知的平均时间复杂度均为O(n*logn）的几种排序算法中效率最高的一个，它在最坏时间复杂度退化到O(n*n）。

golang递归实现

golang非递归实现

2.5、归并排序

算法思想简单描述：2-路归并的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。

归并排序的最好最坏和平均时间复杂度都是O(n*logn)，但是需要额外的长度为n的辅助数组（每次递归调用前都会释放上次递归中传入到Merge函数的temp数组），因此空间复杂度为O(n),而不会因为栈的最大深度为O（logn）而积累至O（n*logn）。占用额外空间是归并排序不足的地方，但是它是几个高效排序算法（快速排序、堆排序、希尔排序）中唯一稳定的排序方法。