排序是数据结构中比较重要的一种基础算法，排序也会考验对线性表和链表、树的灵活运用，本篇文章我们重点讲述下常见的3种基础排序冒泡排序、插入排序、选择排序，下一篇会重点讲述实际工作中用的比较多的快速排序和归并排序。

排序算法基础

排序算法执行效率一般从以下几方面进行衡量：

1）最好情况、最坏情况、平均情况下的时间复杂度

对于待排序数据有的接近有序，有的完全无序，会导致部分算法执行效率上有很大的差异，所以我们在选择算法的时候除了要考虑算法的平均时间复杂度还要参考在实际业务场景下待排数据的实际有序性，和各类排序算法在实际业务场景下的待排数据的时间复杂度来选择合适的算法。

2）比较次数和交换次数

在考虑排序算法的时候，因为基于比较的排序算法会涉及到元素大小比较和元素的交换，所以要把比较次数和交换次数也考虑进去。

3）排序算法的稳定性

仅用效率判断一额排序算法好坏还是不够的，还要看算法的稳定性，什么是算法的稳定性？如果待排序中存在值相等的元素，经过排序后，相等元素之间原有的先后顺序不变，这就说明算法是稳定的。

算法的稳定性在很多多次排序场景下是非常有效的，例如我们需要对一个用户类先按照用户的年龄排序，再按照用户的姓名排序，如果使用的不是稳定算法那么在按照年龄排完序后还需要对相等值再分别进行内部排序，这将非常麻烦，如果是稳定的排序算法，那么处理起来将非常容易，只需要用稳定排序算法对数据进行两次排序就行了，因为排序属性相等的数据在排序前后相对顺序不会变的。

冒泡排序

冒泡排序一般是我们在学习排序算法遇到的第一个排序算法，也是最简单的一种排序算法，冒泡排序的核心思路是相邻两个元素之间的比较，不满足大小关系则交换一次，冒泡排序至少让一个元素移动到它应该在的位置，重复n次完成排序。对于冒泡排序比较形象的解释就是水里的气泡，一堆气泡，含空气多的气泡会从下面慢慢往上升。冒泡排序属于原地排序，只需要一个额外的临时空间所以空间复杂度为O(1)，在待排序数据是有序的情况下最好的时间复杂度为O(n)，平均时间复杂度为O(n^2)。

public void bubbleSort(int nums[]){

int temp;

for(int i=0;i<nums.length;i++){

for(int j=0;j<nums.l

来自简书作者monkey01

联系作者longtestyan