一.冒泡排序
什么是冒泡排序？
然后继续与下一个相邻元素的比较，一直到一次遍历完成。一次遍历的过程就被成为一次冒泡，一次冒泡的结束至少会让一个元素移动到了正确的位置。
冒泡排序又有两种情况：向上冒泡和向下冒泡
向上冒泡指的是：在排序的时候把大的数据排在前面，小数据在后面，这样排序出来的小序列会是从大到小的顺序
具体的冒泡方向要根据自己的要求去设计
它排序需要两次循环来设计：
第二循环负责每次交换遍历数据的相邻数据交换
下面我们来图示一下我们的排序方法：
下面我们来看看冒泡排序的伪代码：
冒泡排序的交换关键在于那个if判断语句：
但是我使用的是大于号，因为排序的稳定性，如果使用大于等于号，两个相等的数据，它也会交换，这样的排序计算就不稳定，也提高了系统开销，
二.选择排序
什么是选择排序？
选择排序的原理就是在一个待排序的数组中，首先从前至后（或从后至前）对数组遍历后选取最大 （或最小）的数，与数组首（尾）的数进行交换。
他会根据次数的减少，待排序的数据也会减少
这里图解一下选择排序：
时间复杂度是O（n^2）
我们使用伪代码来实现一下选择排序：
遍历的次数也会随着已排序的次数减少，因为没排序最大/小数就已经被找出来了，不需反复去校对
三.插入排序
什么是插入排序？
在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
这个覆盖其实是动态的，只要没找到位置，就会先往后覆盖一个，然后向前继续找位置，继续覆盖
我们一起去看看插入排序的伪代码：
j > = 0 如果这个条件不满足，说明前面的数据都比它大，这个数据肯定是最小数据，就直接插入在 第一个位置
插入排序的时间复杂度：O（N ^2）
四.希尔排序
什么是希尔排序？
希尔排序(Shell's Sort是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。从上面我们很容易看出来，它是插入排序的高级版
最快的Sedgewick增量序列：时间复杂度只有 N的7/6次方
希尔排序的排序次数比选择排序要少很多，
一般使用 N/2 , N/4 , N/8 等等构成的数据序列
所以第二次增量排序为什么能直接把 5，6，9给一次排序出来就是根据插入排序的移动覆盖
我们来看看希尔排序的伪代码：
也导致了希尔排序比插入排序快
总的来说，希尔排序的优劣取决于增量序列
五.归并排序
什么是归并排序？
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法
- 自上而下的递归
- 自下而上的迭代
归并排序是分治法演化来的，他与分治法一样，
我们来图解一下归并排序：
找到分界点的时候划分成两半，然后依次进行，直到划分到最小分量的时候就合并。
当比较完了，可能有一个半区还有数据，因为那个（或那几个数据都是）最大的，没有数据能把它们比进临时数组，所以要注意把这些数据直接copy到临时数组中
现在我们用伪代码来描述一下这个算法：
merge_sort 函数负责的是申请一个临时的空间，辅助我们在归并的时候转存这个数据，因为这个函数是归并排序的入口，当归并排序完成以后他还会回到这个函数，
msort 函数负责把传过来的一个函数给他拆分成成局部最小分量
merge 函数负责归并，连=两个小半区的比较，小的就先存入临时数组，当小分区比较完成以后，我们需要对有一个半区残留的元素直接copy到临时数组中，残留的元素一定是当前分区最大的且是有序的，
归并排序：
归并层数为O（LogN+1）
六. 快速排序
什么是快速排序？
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。
-
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
在快速排序中，基准的选择一般是数据第一个元素，中间元素，最后一个元素，
一个是左指针，它是从左往右去找比基准大的数据
当左右指针都找到以后进行交换，然后一直重复，直到两指针相遇，再相遇点我们要比较，如果此数据比基准大，则交换，反之，左指针就往后移动一个位置
然后这个数据就是有序的了，我们需要对于有序的数据继续去划分左右半区，然后把左半区和右半区的最后一个数据作为两个半区的基准，分别计算，
所以快速排序的时间复杂度是：O（nlogn） 最坏的情况就是 O（n^2）
所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
下面我们来图解一下快速排序：
当重合的时候要考虑一下是否需要和基准交换，只有比基准大的数据才能和基准交换否则就让左指针向后移动一次
我们一定要注意：一定是左指针先移动，不然是拍不出来结果的
我们接下来使用伪代码实现一下（递归的方式）：
归并排序需要先拆分成最小元素后，然后在比较的时候，边比较，便合并
在绝大多数情况下，快速排序都要优于归并排序
七.堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。
两种堆的结构：
- 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
- 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的核心思想就是在大顶堆和小顶堆上建立起来的，因为大/小顶堆的性质：根节点比子节点大/小，所以在这两种顶堆中，最上面一层只有一个根节点的哪里，他一定是此序列中最大/小的
这个数据就是有序的了即最大/小数，然后被换到根节点的数就开始维护，此时排序中最大的数又到了根节点，也就是整个序列的第二大数，然后重复操作
堆排序的平均时间复杂度为 Ο(nlogn，它的排序过程很复杂，包括建堆，对维护，然后排序，它们相互依赖最后才做出最后的堆排序
首先我们来看看建堆的过程：
当下一次又会来新的数据，依旧构成三个节点构成，它们也会有一个维护阶段，把最大的元素放到父节点，
当堆构建完成以后，我们就会开始进行排序：
然后二次交换，重复操作，最后完成排序
我们来看看堆排序的伪代码：
堆排序中我们构造的堆其实也是抽象的，并不是在内存中真的开辟了一个图形像堆一样，它是利用数组下标构造的一个联系，比如 下标为 0 的，它的子节点是 ：下标为 1 和下标为2
堆排序是不稳定的，大家可以自己去推一下
八.计数排序
它只适合小范围的排序，空间开销大
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
首先它需要一个数组去计数，还需要一个数据去计算累计值，还需要一个数组用于临时存储 原数组和累计数组的计算结果
计数数组 count [ ]：数据每出现一次，对应数据为下标的计数数组加一，计数数组是临时数组，需要申请，它的大小取决于原数组数据的最大值的加一
排序数组output [ ] : 排序数组是最后的结果，需要拷贝回原数组，它是通过 原数组和累计数组计算的 output[ count 1 [ arr [ i ] ] -1 ] = arr [ i ]
下面我们使用图解一下计数排序：
然后是伪代码实现：
但是它只适合小范围的计算，因为计算数组的申请需要根据元素的最大值，而不是元素个数，也就是我只有一个元素，它的值是100，那么我也得申请 100的空间大小
计数排序的时间复杂度是：O(n ，空间开销太大
九.桶排序
桶排序是另外一种以O(n或者接近O(n的复杂度排序的算法. 它假设输入的待排序元素是等可能的落在等间隔的值区间内。
桶排序与其它排序不同，它依靠的是下标代表元素，数组里的值只是确定整个序列有没有此元素，我们最开始会初始化我们的桶数组，都初始化为零
当数据装完了以后我们再去遍历桶数组，当数组的值不为零的时候就打印下标，
我们来图解一下桶排序：
而是根据原数组的数据中的最大值来判定的的，也就是我只有两个元素分别是，100和1000的时候，在申请辅助数组的时候，我们要根据数组的中元素的最大值
所以桶排序只适合小范围的计数，他和计数排序的适用区间差不多，比如：记录班级各个同学的成绩，然后排序，这种计算是很合适的，它不仅能排序还能计数，这种小范围的计数是可以使用桶排序的
下面就是使用区间来描述桶的容量：
这种一个桶就代表一个区间的算法就不能光使用辅助数组了，还需要使用链表，把位于同一桶的元素串联起来
它的复杂度就是：O（N ^2）
接下来我们看看桶排序的一般代码描述：
空间开销就很大了，在使用桶排序的时候一定注意它的使用区间，它只是用于小范围且连续的序列，而且序列中的最大元素尽量不断地靠近 0，开辟的空间越小越好
十.基数排序
什么是基数排序？
由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
比如 ： 我们对两位数要根据基数排序 33 和 69
个位进桶了以后表示各位已经是在整个序列是有序的了，
此时十位在整个序列是有序的了，只需要将桶内的元素按顺序拿出，然后往后一个个拿桶，最后就的到了最后的数据
但是思想上还是桶排序的思想
我们来图解一下基数排序：
对比桶排序，很明显的就是在数据量变多的时候，桶排序所需的空间就会越来越大，反而基数排序就只需要十个桶，但它和基数排序一样要申请一个辅助数组，所以开销依旧很大
我们来看看基数排序的代码实现：
max是数组中的最大数，它是几位数就决定了要进行几次基数排序
基数排序的时间复杂度是：O（n） 也是线性的，也是稳定的排序
十一.总结
十大排序的时间空间复杂度以及稳定性
后面三种排序大多是线性的，理解起来也比较容易，时间复杂度最好的情况都是O（n），但是空间开销真的很大
当然我推荐必须掌握的就是：快速排序，归并排序，堆排序，这也是重点的算法。