今天总结一下我们常用到的排序算法（指内存排序），按照算法思想 + 代码实现 + 时间复杂度 + 空间复杂度 + 是否稳定 + 是否为比较排序的格式描述一种排序算法
下面的例子皆以升序排序为例
冒泡排序
冒泡排序属于交换排序的一种，是一种简单的排序算法。核心思想是重复的遍历数列（遍历次数 = 数列长度n），比较相邻的两个数，如果前面的数比后面的数大，则交换顺序，每一次遍历之后当前数列中最大的数将“沉底”，较小的数会慢慢“浮”到数列顶端，这就是“冒泡”名字由来。
过程：
- 遍历数组n(n = 数组长度)次
- 从下标为0开始比较相邻两个数大小，直到下标到达
n-1-已遍历次数（减少比较次数，优化排序） - 遍历完成，排序完成
代码：
时间复杂度：最坏情况O(n^2) 最好情况O(n) 平均O(n^2)
空间复杂度：O(1)
稳定排序，属于比较排序
快速排序
快排和冒泡一样属于简单的交换排序。快速排序通过分治的思想把数列二分，降低问题规模，以降低复杂度。核心思想是每一次排序能确定一个元素在数列中的准确位置。
过程：
- 数列中选择一个元素作为“基准“，一般选择第一个元素
- 重新排列数列，将所有比基准值小的数放在基准值的左边，所有比基准值大的数放在基准值右边，分区操作之后，基准值就处于数列中间位置
- 递归的将两边子序列以相同方法重新排列
代码：
时间复杂度：最坏情况O(n^2) 最好情况O(nlogn) 平均O(nlogn)
空间复杂度：O(logn)
不稳定排序，属于比较排序
插入排序
插入排序的原理是通过构建有序序列，将数列中未排序数据插入到有序序列中。在有序序列中逐个往前比较插入数据，确定插入位置。
过程：
- 选择第一个元素看作有序序列
- 取出下一个元素a，从后往前比较有序序列中元素与a的大小，比a大的元素与a交换位置，直至元素i < a, 那么i+1就是元素a在序列中的位置
- 重复步骤2直到整个序列有序
代码：
时间复杂度：最坏情况O(n^2)，最好情况O(n)， 平均O(n^2)
空间复杂度：O(1)
稳定排序，属于比较排序
希尔排序
希尔排序是希尔于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序的改良升级版，也称为缩小增量排序，同时该算法是第一批冲破O(n^2)的算法之一。
希尔排序的原理也是基于分治思想，基本思想是：假设数列长度len，选取一个间隔increment(增量)，将数列分为increment份，对每一份使用直接插入排序，减小increment，重复操作，直至increment=1，排序完成
过程：
- 选取希尔排序增量arrlen/2向下取整
- 划分子序列，并对子序列插入排序
- 减小增量，重复步骤2，直至增量为1，排序完成
代码：
时间复杂度：O(nlog2n)
空间复杂度：O(1)
不稳定排序，属于比较排序，其中希尔排序缩小增量的选择对算法性能影响很大，最初shell提出取increment=len/2向下取整，后来Knuth提出取increment=n/3向下取整+1
选择排序
选择排序是最稳定的排序算法之一，无论什么情况时间复杂度都是O(n^2)，所以使用选择排序数据规模越小越好
选择排序基本工作原理：在无序序列中选择最小的数放置到无序序列最前端，重复n次即可排序完成
过程：
- 从当前无序数列中选择出最小的数
- 交换无序序列最前端数与选出最小数的位置
- 重复1，2直到无序序列消失，排序完成
代码：
时间复杂度：O(n^2)
空间复杂度：O(1)
不稳定排序，属于比较排序
堆排序
堆排序是利用堆这种数据结构设计的一种算法，属于选择排序。
堆结构：堆是一种近似完全二叉树结构，每个节点的值都大于等于（小于等于）其左右子节点的值，称为大顶堆（小顶堆）
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序的基本思想是将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾元素就是最大值，调整结构将剩余的n-1个元素从新构造成一个堆。如此反复执行，便能得到一个有序序列了
过程;
- 将待排序序列构造成一个大顶堆（调整数列排序结构，使其满足堆定义）
- 交换根节点和末尾元素
- 反复执行1，2调整+交换，最终得到一个有序序列
代码：
时间复杂度：O(nlogn)
空间复杂度：O(1)
不稳定排序，属于交换排序
归并排序
归并排序(merge排序)与选择排序一样，无论待排序列什么样，时间复杂度均为O(nlogn)，表现比选择排序好得多，但是需要额外的内存空间
归并排序算法采用经典的分治策略，利用归并的思想实现，基本思想是先将子序列排序，再将已有序的子序列合并。
过程：
- 分：通过递归或迭代将序列拆分为两部分
- 治：将两部分通过归并排序合并
代码：
时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定排序，属于比较排序
计数排序
计数排序是一种稳定的排序算法，要求输入的数据必须是有确定范围的整数。算法核心在于将输入的数值转换为键值存储在额外开辟的数组空间中。
过程：
- 对每个输入数据进行统计，得到频率表
- 将频率表转换为各个数据的开始索引
- 根据开始索引，将数据存放到临时数组中
- 将临时数组回写到原数组
代码：
时间复杂度：O(n+k)
空间复杂度：O(k)
稳定排序，不属于比较排序
桶排序
桶排序是计数排序的升级版，利用了函数的映射关系。工作原理：假设输入数据符合均匀分布，将数据分到有限量的桶里，每个桶再分别排序（可以选择其他的排序方式）
过程：
- 根据输入数据建立n个桶，每个桶存放一定范围内的数据
- 将特定范围内的数据放入对应得桶中
- 对每个非空桶进行排序，可以选择其他排序算法
- 按划分范围顺序，将排好序的桶中元素取出，排序完成
代码：
时间复杂度：O(n+k)
空间复杂度：O(n+k)
稳定性取决于桶内采用的排序算法，不属于比较排序
基数排序
基数排序也是非比较的排序算法，低位优先排序的思想实现基数排序：从右往左对每一位排序一轮，直至最左边的那位排序，则数列排序完成，其中每一位的排序算法可以使用计数排序，因为我们通常知道每一位的数据范围，且数据范围较小，计数排序相比其他比较排序方法效率更高。
过程：
- 计算数据最长位数，确定有多少轮排序
- 从右往左分别对每一位做计数排序
- 最后一轮结束后，排序完成
代码：
时间复杂度：O(n*k)
空间复杂度：O(n+k)
稳定排序，不属于比较排序
以上就是十种基本排序算法的总结，自己实现了一遍印象更深刻了，哈哈，努力学习~