最经典最常用的排序算法有：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序和桶排序。这些排序算法可以按照时间复杂度分为三类：
冒泡排序每次只会比较相邻的两个元素，只有在不满足要求的大小关系情况下，才会发生交换行为。一次冒泡迭代会让至少一个元素移动到它最终应该在的位置上，最多n次冒泡迭代，当某次冒泡迭代没有发生元素的交换行为，就可以判定数列已经完成了排序。
比如我们需要对如下数列进行从小到大的排列：
冒泡排序过程示意图
对应的实现代码如下：
public static void mAIn(String[] args) {
int[] data = {4,5,6,3,2,1};
int size = 6;
log.info("原始数列为：{}",data);
bubbleSort(data,size);
log.info("冒泡排序后的结果为：{}",data);
}
public static void bubbleSort(int[] data, int n){
if(n <= 1){
log.info("数组中元素少于2个，无需进行排序！");
return;
}
// 最多需要迭代n次冒泡
for(int i=0;i<n;i++){
// 表示当前迭代冒泡中是否发生了元素交换
boolean switchFlag = false;
for(int j=0;j<n-i-1;j++){
if(data[j] > data[j+1]){
// 不满足从小到大的关系，需要交换
int temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
switchFlag = true;
}
}
// 当前冒泡迭代中没有发生元素交换，说明数列已经有序，完成了排序，可以提前结束
if(!switchFlag){
break;
}
}
}
冒泡排序没有借助很多额外的存储空间，因此是原地排序；
冒泡排序只有在前后两个元素不满足大小关系时才发生交换，因此是稳定的排序算法；
最好情况下原始数列就是满足要求的大小关系的，那么只需要迭代一个冒泡就完成了排序，时间复杂度为O(n)；最坏情况下原始数列正好和要求的大小关系完全相反，那么需要迭代n此冒泡，因此时间复杂度为O(n^2)。
插入排序将整个数列划分为已排序和未排序两个区间，初始情况下，已排序区间只有一个元素，那就是数列的第一个元素，然后重复取未排序区间中的元素逐个插入到已排序区间中，直至未排序区间元素数量为0，需要注意的是，将元素插入已排序区间会引起插入位置后方所有元素的移动。
比如，我们对如下数列进行插入排序的过程为：
插入排序过程示意图
对应的实现代码如下：
public static void main(String[] args) {
int[] data = {4,5,6,3,2,1};
int size = 6;
log.info("原始数列为：{}",data);
insertionSort(data,size);
log.info("插入排序后的结果为：{}",data);
}
public static void insertionSort(int data[], int n){
if(n <= 1){
log.info("数组中元素少于2个，无需进行排序！");
return;
}
// 从未排序区间开始遍历
for(int i=1;i<n;i++){
// 放到临时空间保存，因为后续已排序区间元素的向后移动会覆盖掉data[i]的值
int value = data[i];
int j=i-1;
for(;j>=0;j--){
// 已排序区间从后往前遍历和当前需要插入的元素进行比较
if(data[j] > value){
// 当前已排序区间的元素往后移动一位
data[j+1] = data[j];
} else {
break;
}
}
// 插入到已排序区间中小于等于自己元素的后面，保证排序算法的稳定性
data[j+1] = value;
}
}
插入排序没有借助很多额外的存储空间，因此是原地排序；
插入排序可以在算法中约定，将未排序区间的元素插入到排序区间相同元素的后方，因此也是稳定的排序算法；
最好情况下原始数列就是满足要求的大小关系的，那么只需要迭代一遍数列就完成了排序，时间复杂度为O(n)；最坏情况下，每将一个元素插入已排序区间，都会引起所有已排序区间元素的向后移动，那么时间复杂度就是O(n^2)。
选择排序也是将整个数列分为已排序区间和未排序区间，和插入排序的区别是，每次迭代都是从未排序区间中寻找到最小值，然后将其和未排序区间中的第一个元素进行交换，直至未排序区间元素为空。
选择排序过程示意图
选择排序也是原地排序；
选择排序是不稳定的，在交换元素的时候，极有可能改变相同元素的前后顺序，比如：
1，2，| 5，4，5，3
此时未排序区间最小元素为3，会和未排序区间第一个元素5进行交换：
1，2，3，| 4，5，5
此时，未排序区间的两个5实际上已经发生了顺序上的变化，在排序完成后，它们也极有可能是维持现在变化了的顺序的。
最好情况和最坏情况下的时间复杂度都是O(n2)，无论最好还是最坏，每次迭代都要从未排序区间中找到最小值，每次找最小值的时间复杂度为O(n)，所以无论哪种情况，选择排序的时间复杂度都是O(n2)。
冒泡排序和插入排序虽然时间复杂度在同一量级，并且都是稳定的、原地排序算法，但是通常来说，插入排序的性能要优于冒泡排序。因为插入排序的交换次数和赋值次数更少，在大数据量数列排序时，效果尤为明显。
插入排序还存在优化的空间，在大数据量和比较无序的情况下使用希尔排序能很好地提升排序性能，希尔排序的核心思想是对数列按照增量序列进行逻辑分组，对分组的数列使用插入排序，保证基本有序，然后逐步减小增量序列，迭代进行插入排序。
希尔排序的时间复杂度视增量序列值的不同而不同，最坏情况是O(n^2)，并且不是稳定的排序算法。
总之，这三种排序算法的时间复杂度都是O(n^2)，比较适合小数据量的排序场景。
快速排序是由冒泡排序进化而来，能够迭代更少的次数，更加快速地完成排序，因此得名。其使用了分治思想和递归的实现方式，其大致的思路如下：
排序过程示意图可以参考：什么是快速排序
快速排序在排序的过程中并不会借助很多的额外存储空间，因此属于原地排序；
快速排序可能会改变相同元素的顺序，因此是不稳定的排序算法；
快速排序的时间复杂度是O(nlogn)，前提是每次递归选取的基准元素正好可以将数列分成两个差不多的子数列，在最坏情况下，每次选取的基准元素不是最大值就是最小值的话，那么时间复杂度就会退化为O(n^2)。
归并排序也是使用了分治思想和递归的实现方式，其大致的思路如下：
分解和合并的大致示意图如下：
归并排序的分解合并过程
需要注意的是，在合并的过程中，算法需要借助额外的存储空间来合并相邻的两个子数列，合并的过程如下：
归并排序合并过程示意图
递归的代码示例如下：
public static void MergeSort(int[] data, int begin, int end){
if(begin >= end){
log.info("当前子数列仅有一个元素，无需再分解");
return;
}
int middle = (begin + end) / 2;
MergeSort(data,begin,middle);
MergeSort(data,middle+1,end);
Merge(data,begin,middle,end);
}
归并排序在合并的时候需要借助很多额外的存储空间，空间复杂度为O(n)，因此它不是原地排序算法；
归并排序在合并的时候，我们可以通过代码控制相同的元素保持原始数列的顺序，因此是稳定的；
归并排序在任何情况下的时间复杂度都是O(nlogn)；
快速排序和归并排序都是比较复杂的排序算法，它们都是采用了分治思想和递归的实现方法，区别在于：
桶排序示意图
桶排序需要借助额外的存储空间“桶”，因此，不是原地排序算法；
桶排序是否稳定取决于单个桶内排序使用的算法，如果使用的快速排序，因为快排本身就不是稳定的，因此桶排序就不是稳定的；
桶排序的空间复杂度为O(n)，因为它需要将全部元素都放到桶中；时间复杂度也是O(n)，这个是由公式推到而来，假设n个元素被平均放到m个桶里面，那么每个桶中的元素个数为k=n/m，每个桶中排序的时间复杂度就是快速排序的时间复杂度，为O(klogk)，因为有m个桶，因此总的时间复杂度就是O(mklogk)，我们把k替换为n/m，那么时间复杂度就可以表示为O(nlog(n/m)，当桶的个数m接近元素个数n时，log(n/m)就是很小的常数可以忽略，因此时间复杂度就接近O(n)；
桶排序对待排序数列的要求比较高，即待排序数列必须是容易被划分为m个桶的，并且每个桶中的元素要能均匀，否则，有的桶中元素很多，有的很少，那么就会退化为O(nlogn)的时间复杂度；
桶排序比较适用于大数据量的外部排序场景中（非内存排序），比如对10GB的订单数据按照金额进行排序，内存一次性加载不了这么大的数据，可以使用桶排序划分若干个有次序的相同大小的文件，一次只把一个文件中的数据加载到内存进行快速排序；但是订单金额分布不一定是均匀的，有的桶中的数据比较多，会导致该桶文件也无法被一次性加载到内存中进行排序，此时可以对该文件迭代进行桶排序，直至所有桶文件都可以被加载到内存中为止。
计数排序是桶排序的一种特殊情形，当待排序数列的范围区间不是很大的时候，我们为每一个数值划分一个桶，桶之间要有顺序，然后遍历数列，将元素放到它对应的桶中，最后再将桶按照顺序合并起来就得到了有序的数列；每个桶中的元素都是相同的，因此我们省掉了桶内快速排序的时间；
计数排序需要借助额外的存储空间“桶”，因此，不是原地排序算法；
计数排序再将相同的元素放到同一个桶中的时候，可以设置保持它们在原始数列中顺序来保证算法的稳定性；
计数排序的空间复杂度是O(n)，时间复杂度为O(n+k)，k表示数据范围即有多少各个桶，当数据范围不大，可以考虑为常数，那么时间复杂度就是O(n)；
计数排序只能适用在数列范围区间不大的场景中，比如给50万考生的分数进行排名，分数范围k为0~600，数据元素m为50万，k远远小于m，所以适合适用计数排序；计数排序只能给非负整数进行排序，如果待排序数列不是非负整数，需要先想办法把数列转换为非负整数后才能使用计数排序进行排序；
有时候待排序数列的范围区间非常大，分布也不一定是均匀的，且数列本身位数比较多，可以考虑基数排序；基数排序是从最低位开始排序，逐步遍历到最高位，等到最高位完成排序后，整个数列就是有序的。
有一个要求，对每一位的排序算法一定要使用稳定的排序算法，不然高位的排序会弄乱低位已经排好的顺序，排序算法就不对了。
基数排序在每一位上会使用到线性排序算法，比如计数排序，需要使用额外的存储空间，因此不是原地排序算法；
基数排序每一位的排序算法都是采用的稳定的算法，因此整体上也是稳定的；
基数排序的空间复杂度为O(1)，时间复杂度为O(kn)，当k（元素的位数）不大的时候，并且每一位的排序采用的是线性排序算法（比如计数排序，这就要求每一位上的范围区间不是很大），那时间复杂度就是O(n)；如果每一位排序采用的不是线性排序算法，那么时间复杂度就很难保证是O(n)了。
基数排序的适用场景有给手机号、身份证号、银行卡号排序，这些场景下，数列的范围区间非常大，并且分布不一定均匀，不适合使用桶排序和计数排序，但是却非常适合基数排序。
有的待排序数列不是等长的，比如单词表序列的排序，可以把每一个单词元素通过补0的方式补充到一样长，再通过基数排序进行排序。
这三种排序算法的时间复杂度是线性的，因此也被成为线性排序算法，虽然它们在时间复杂度上面很占优势，但是对待排序数列的要求比较高，只有待排序数列符合它们各自的特点时，使用它们进行排序才能得到O(n)的效率，因此，实际使用中也不是太多。
如下是八种基本排序算法的总结：
八大排序算法总结
以上是比较基本的排序算法，还有其它的排序算法会在以后总结。
当你拿到一个数列考虑使用哪一种排序算法的时候：
京公网安备 11010802035086号