在生活中，我们离不开排序。例如上体育课时，同学们会按照身高顺序进行排队；又如每一场考试后，老师会按照考试成绩排名次。
在编程的世界中，应用到排序的场景也比比皆是。例如当开发一个学生 管理系统时，需要按照学号从小到大进行排序；当开发一个电商平台时，需要把同类商品按价格从低到高进行排序；当开发一款游戏时，需要按照游戏得分从多到少进行排序，排名第一的玩家就是本场比赛的MVP，等等。
由此可见，排序无处不在。排序看似简单，它的背后却隐藏着多种多样的算法和思想。那么常用的排序算法都有哪些呢？
根据时间复杂度的不同，主流的排序算法可以分为3大类。
1. 时间复杂度为O(n2)的排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序（希尔排序比较特殊，它的性能略优于O(n2)，但又比不 上O(nlogn)，姑且把它归入本类）
2. 时间复杂度为O(nlogn)的排序算法
- 快速排序
- 归并排序
- 堆排序
3. 时间复杂度为线性的排序算法
- 计数排序
- 桶排序
- 基数排序
当然，以上列举的只是最主流的排序算法，在算法界还存在着更多五花八门的排序，它们有些基于传统排序变形而来；有些则是脑洞大开，如鸡尾酒排序、猴子排序、睡眠排序等。
此外，排序算法还可以根据其稳定性，划分为稳定排序 和不稳定排序。
即如果值相同的元素在排序后仍然保持着排序前的顺序，则这样的排序算法是稳定排序；如果值相同的元素在排序后打乱了排序前的顺序，则这样的排序算法是不稳定排序。例如下面的例子。
在大多数场景中，值相同的元素谁先谁后是无所谓的。但是在某些场景下，值相同的元素必须保持原有的顺序。
冒泡排序冒泡排序是一种稳定排序 ，值相等的元素并不会打乱原本的顺序。由于该排序算法的每一轮都要遍历所有元素，总共遍历（元素数量-1 ）轮，所以平均时间复杂度是O(n2 ) 。
代码实现
public static void sort(int []nums){
for(int i = 0; i < nums.length - 1; i ){
for(int j = 0; j < nums.length - 1; j ){
int temp = 0;
if(nums[j] > nums[j 1]){
temp = nums[j 1];
nums[j 1] = nums[j];
nums[j] = temp;
}
}
}
}
代码非常简单，使用双循环进行排序。外部循环控制所有的回合，内部循环实现每一轮的冒泡处理，先进行元素比较，再进行元素交换。
冒泡排序的优化优化一原始的冒泡排序有哪些可以优化的点呢？ 让我们回顾一下刚才描述的排序细节，仍然以{5,8,6,3,9,2,1,7}这个数列为例，当排序算法分别执行到第6、第7轮时，数列状态如下。
很明显可以看出，经过第6轮排序后，整个数列已然是有序的了。可是排序算法仍然兢兢业业地继续执行了第7轮排序。在这种情况下，如果能判断出数列已经有序，并做出标记，那么剩下的 几轮排序就不必执行了，可以提前结束工作。冒泡排序第2版 代码示例如下：
for(int i = 0; i < nums.length - 1; i ){
boolean mark = true;
for(int j = 0; j < nums.length - 1; j ){
int temp ;
if(nums[j] > nums[j 1]){
temp = nums[j 1];
nums[j 1] = nums[j];
nums[j] = temp;
mark = false;
}
}
if(mark)break;
}
与第1版代码相比，第2版代码做了小小的改动，利用布尔变量isSorted 作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，则说明数列已然有序，然后直接跳出大循环。
优化二这次以一个新的数列为例。
这个数列的特点是前半部分的元素（3、4、2、1）无序，后半部分的元素（5、6、7、8）按升序排列，并且后半部分元素中的最小值也大于前半部分元素的最大值。下面按照冒泡排序的思路来进行排序，看一看具体效果。
第1轮
