稳定排序：

冒泡排序、插入排序、归并排序

非稳定排序：

选择排序、希尔排序、堆排序、快速排序

1、冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调，比较是相邻的两个元素比较，交换也发生在这两个元素之间。（类似于气泡上浮过程）

动图如下：

1、比较相邻的元素，如果第一个比第二个大，则交换

2、对每对相邻元素重复步骤1操作，筛选出最大元素

3、针对所有元素重复步骤1、2（除最后一个元素，已经是最大）

示例代码：

2、选择排序

 从未排序序列中找到最小（最大），放在已排序序列尾部

动图如下：

1、找到排序队列最小（最大）元素，存放在序列起始位置

2、在未排序序列找到最小（最大）元素，放在已排序序列尾部

3、重复1、2步骤

示例代码：

3、插入排序

用未排序序列第一个元素，从已排序序列尾部到起始位置方向开始比较，也就是插入元素和已排序最大元素开始比较，一直找到比它小的元素位置后插入。

动图如下：

 1、设置第一个元素为已排序

2、取出下一个元素，在已排序序列尾部向前比较

3、如果该元素（已排序）大于新元素（需插入元素），将该元素移到下一位置

4、重复步骤3，找到已排序元素小于或等于新元素

5、将新元素插入已排序序列

6、重复2~5

示例代码：

4、快速排序

以一个元素为基数，将小于基数的元素移到基数前面，大于基数的元素移到基数后面，对左右区间递归以上步骤，知道区间只有一个数

动图如下：

1、选取一个数为基数

2、将比基数小的元素移到基数前面

3、将比基数大的元素移到基数后面 

4、对基数左右区间重复1~3步骤，直到区间只有一个数

示例代码：

5、希尔排序

希尔排序可以理解成插入排序的优化版本。希尔排序是先将任意间隔为N的元素有序，刚开始可以是N=n/2，接着让N=N/2，让N一直缩小，当N=1,时，此时序列间隔为1有序。

动图如下：

1、初始间隔N=数组长度/2

2、对间隔为N的分组进行插入排序，直至有序

3、缩小N值，N=N/2；

4、重复2、3步骤，直至间隔N=1

示例代码：

6、堆排序

堆可以分为大根堆和小根堆，而堆排序是根据堆的数据结构设计的一种排序。

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]  

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]  

动图如下：

1、将待排序序列构建成大根堆，此堆为初始无序堆

2、将堆顶元素和最后一个元素交换，此时得到新的N-1无序堆和有序序列

3、重复2直到无序堆为1，此时有序序列为N-1

示例代码：

7、计数排序

将待排序序列元素出现次数做为键值存在新开辟数组空间中

动图如下：

1、找出待排序序列A最大元素Max

2、新开辟一个Max+1的数组B，初始值为0

3、将序列A中元素值做为数组B索引x，A中元素出现次数做数组B索引为x的值

4、开辟一个长度和A序列大小相同的数组C

5、循环取出数组B的值存入C中，取出一个B值--

示例代码：

8、归并排序

归并排序采用分治思想，把待排序序列分成N个子序列，子序列排序后，合并两个子序列实现排序

动图如下：

1、把长度为N的序列分成N/2个子序列

2、对子序列进行归并排序

3、将有序子序列合并成一个子序列

示例代码：

9、桶排序

桶排序是将数组分别放到有限数量的桶里。每个桶再进行排序。桶排序是鸽巢排序的一种归纳结果

动图如下：

1、设置一定数量的空桶

2、遍历待排序序列，将每个元素放入对应桶里

3、对每个不空的桶进行排序

4、从不空的桶将元素从桶中取出

示例代码：

10、基数排序

基数排序是按照低位先排序，然后收集，再按照高位排序，再收集，以此类推，直到最高位。

动图如下：

1、取待排序序列中最大数，并获取位数

2、从待排序序列每个元素低位相同放到一个radix数组

3、从多个radix数组取出元素，组成新的待排序序列

4、以此重复2、3（步骤2从低到高位）

示例代码：