将杂乱无章的 数据元素 ，通过一定的方法按关键字顺序排列的过程叫做 排序

一、冒泡排序

两个数比较大小，较大的数下沉，较小的数冒起来

1. 比较相邻的元素，如果第一个比第二个大，就交换它们两个
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
3. 继续重复上述过程，依次将第 n -1、n-2...1 个最大数排好位置
   
   设置标志位 flag，如果发生了交换 flag 设置为 true；如果没有交换就设置为 false。当一轮比较结束后如果 flag 仍为 false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。

二、选择排序

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完

1. 第一次遍历 n - 1 个数，找到最小的数值与第一个元素交换
2. 第二次遍历 n - 2 个数，找到最小的数值与第二个元素交换
3. 一直重复到第 n - 1 次
   

三、插入排序

在要排序的一组数中，假定前 n - 1 个数已经排好序，现在将第 n 个数插到前面的有序数列中，使得这 n 个数也是排好顺序的。如此反复循环，直到全部排好顺序。

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；回到步骤 2 直到最后一个元素
   

四、希尔排序

也称为缩小增量排序，希尔排序是把记录按一定增量分组，对每组使用直接插入排序算法排序，直到增量减至 1

1. 在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
2. 然后逐渐将增量减小, 并重复上述过程。直至增量为 1, 此时数据序列基本有序, 最后进行插入排序。

五、归并排序

将已有序的子序列合并，得到完全有序的序列，重复直到只有一个序列；即先使每个子序列有序，再使子序列段间有序

1. 把长度为 n 的输入序列分成两个长度为 n / 2 的子序列；
2. 对这两个子序列分别采用归并排序；
3. 将两个排序好的子序列合并成一个最终的排序序列。

六、快速排序

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序

1. 先从数列中取出一个数作为 key 值；
2. 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
3. 对左右两个小数列重复第二步，直至各区间只有 1 个数。
   

七、堆排序

利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

1. 将数据构造成大顶堆（或小顶堆）
   2、按大顶堆规则重复取出堆顶元素，即为有序序列

八、计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数

1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
3. 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
4. 反向填充目标数组：将每个元素 i 放在新数组的第 C(i)项，每放一个元素就将 C(i)减去 1
   

九、桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定

1. 将待排序元素划分到不同的痛。先扫描一遍序列求出最大值 maxV 和最小值 minV ，设桶的个数为 k ，则把区间 [minV, maxV] 均匀划分成 k 个区间，每个区间就是一个桶。将序列中的元素分配到各自的桶
2. 对每个桶内的元素进行排序。可以选择任意一种排序算法
3. 将各个桶中的元素合并成一个大的有序序列

十、基数排序

想法非常简单，首先创建数组 A[MaxValue]；然后将每个数放到相应的位置上（例如 17 放在下标 17 的数组位置）；最后遍历数组，即为排序后的结果。

1. 取得数组中的最大数，并取得位数；
2. arr 为原始数组，从最低位开始取每个位组成 radix 数组；

3. 对 radix 进行计数排序（利用计数排序适用于小范围数的特点）
   

   计数排序和基数排序不一样