排序算法分为三类：
1、冒泡排序，插入排序，选择排序。时间复杂度 O(n^2) ，是基于比较的排序,适合小规模数据的排序。
2、快速排序，归并排序。时间复杂度O(N logN) 是基于比较的排序，法适合大规模的数据排序。主要是用到了分治的思想。
3、桶排序，基数排序，计数排序，时间复杂度O(n)，不是基于比较的排序。

冒泡排序

for (int i = 0; i < list.length - 1; i++) {
boolean flag = false;
for (int j = 0; j < list.length - 1 - i; j++) {
if (list[j] > list[j + 1]) {
int temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
flag = true;
}
}
if(!flag){
break;// 没有数据交换提前退出
}
}
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是一个原地排序算法。
在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
冒泡排序的算法的交换次数 = n*(n-1)/2–初始有序度

有序度: 如果 有序元素对：a[i] <= a[j], 如果i < j。

插入排序

将数据分为两部分，一部分是已经排序的，一部分未排序的，用未排序的数据插入到已排序的部分。涉及到元素的比较和移动。
从第一个元素开始，该元素可以认为已经被排序,取出下一个元素，在已经排序的元素序列中从后向前扫描,如果该元素（已排序）大于新元素，将该元素移到下一位置 。
for (int i = 0; i < list.length; i++) {
int insert = list[i];
for (int j = i; j > 0; j—) {
if (insert < list[j-1]) {
list[j] = list[j-1];
list[j-1] = insert;
}
}
}

希尔排序

如果你想要结果从大到小排列，它会首先将数组进行分组，然后将较大值移到前面，较小值移到后面，最后将整个数组进行插入排序，这样比起一开始就用插入排序减少了数据交换和移动的次数，可以说希尔排序是加强版的插入排序

数组5, 2, 8, 9, 1, 3，4来说，数组长度为7，当increment为3时，数组分为两个序列5，2，8和9，1，3，4，第一次排序，9和5比较，1和2比较，3和8比较，4和比其下标值小increment的数组值相比较此例子是按照从大到小排列，所以大的会排在前面，第一次排序后数组为9, 2, 8, 5, 1, 3，4第一次后increment的值变为3/2=1,此时对数组进行插入排序，

归并排序

如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

快速排序

如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。我们遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。经过这一步骤之后，数组p到r之间的数据就被分成了三个部分，前面p到q-1之间都是小于pivot的，中间是pivot，后面的q+1到r之间是大于pivot的。
快排和归并的递推公式
mergesort(p,q) = mergesort(p,r) ,mergesort(r+1,q), 终止条件 p>= r

桶排序

核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
比如0-50的排序分为0-9，10-19，20-29，30-39，40-49五个桶。然后分别对桶内的数据进行快速排序。

计数排序

计数排序其实是桶排序的一种特殊情况。当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，我们就可以把数据划分成k个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
计数排序只能用在数据范围不大的场景中，如果数据范围k比要排序的数据n大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。
比如，还是拿考生这个例子。如果考生成绩精确到小数后一位，我们就需要将所有的分数都先乘以10，转化成整数，然后再放到9010个桶内。再比如，如果要排序的数据中有负数，数据的范围是[-1000, 1000]，那我们就需要先对每个数据都加1000，转化成非负整数。

基数排序

基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到O(n)了。

堆排序

是一种树形选择排序，是对直接选择排序的有效改进。
冒泡排序：快速排序 https://www.cnblogs.com/0201zcr/p/4763806.html
选择排序、插入排序、希尔排序可查看：http://www.cnblogs.com/0201zcr/p/4764427.html
归并排序、堆排序可查看：http://www.cnblogs.com/0201zcr/p/4764705.html

冒泡排序和插入排序的时间复杂度都是O(n^2)，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢

冒泡排序需要3个赋值操作，而插入排序只需要1个。我们来看这段操作：
冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true;
}
插入排序中数据的移动操作：
if (a[j] > value) {
a[j+1] = a[j]; // 数据移动
} else {
break;
}
我们把执行一个赋值语句的时间粗略地计为单位时间（unit_time），然后分别用冒泡排序和插入排序对同一个逆序度是K的数组进行排序。用冒泡排序，需要K次
交换操作，每次需要3个赋值语句，所以交换操作总耗时就是3*K单位时间。而插入排序中数据移动操作只需要K个单位时间。

快排与归并排序的区别

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为O(nlogn)的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。Java语言采用堆排序实现排序函数，C语言使用快速排序实现排序函数。

如何优化快速排序？

快速排序算法的核心是选择合理的分区点。尽可能地让每次分区都比较平均。
常用的分区算法：
1.三数取中法
我们从区间的首、尾、中间，分别取出一个数，然后对比大小，取这3个数的中间值作为分区点。这样每间隔某个固定的长度，取数据出来比较，将中间值作为分区点的分区算法，肯定要比单纯取某一个数据更好。但是，如果要排序的数组比较大，那“三数取中”可能就不够了，可能要“五数取中”或者“十数取中”。
2.随机法
随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度来看，也不大可能会出现每次分区点都选的很差的情况，所以平均情况下，这样选的分区点是比较好的。时间复杂度退化为最糟糕的O(n2)的情况，出现的可能性不大。

桶排序的时间复杂度为什么是O(n)呢？

如果要排序的数据有n个，我们把它们均匀地划分到m个桶内，每个桶里就有k=n/m个元素。每个桶内部使用快速排序，时间复杂度为O(k logk)。m个桶排序的时间复杂度就是O(m k logk)，因为k=n/m，所以整个桶排序的时间复杂度就是O(nlog(n/m))。当桶的个数m接近数据个数n时，log(n/m)就是一个非常小的常量，这个时候桶排序的时间复杂度接近O(n)。
应用场景：桶与桶之间有着天然的大小顺序，数据在各个桶之间的分布是比较均匀的。