排序算法的执行效率
1.最好时间复杂度，最坏时间复杂度，平均时间复杂度
在分析排序算法的时间复杂度时，需要给出最好、最坏、平均情况下的时间复杂度，以及这些复杂度对应的待排序数据的特点。对于排序算法，原始数据的有序度对排序的执行时间有较大的影响。在极端情况下，对接近有序或完全无序的原始数据进行排序，排序需要的时间会有较大的差别。
2.时间复杂度的系数，常数和低阶
时间复杂度反应的时算哒的执行时间随数据规模n的增长趋势。在用大O表示法表示复杂度的时候，我们常常会忽略系数，常数和低阶.但是在实际的开发中，要排序的数据可能规模很小，因此在对时间复杂度相同的排序算法进行性能比较时，就要把他们考虑进来。
排序算法的内存消耗
算法的内存消耗可以根据空间复杂度来衡量，排序算法也不例外。除空间复杂度分析之外，根据派速算法是否需要额外的非常量级的而数据存储空间，我们还需要把排序算法分为原地排序算法（在原数据存储空间上完成的排序操作）和非原地排序算法（需要额外的非常量级的数据存储空间才能完全排序）。
原地排序并不与O(1)的时间复杂度划等号，他们直接可能不相同。
排序算法的稳定性
排序算法还有一个特有的分析维度：稳定性。根据稳定性，我们把排序算法分为稳定排序算法和不稳定排序算法。如果待排序的数据中存在值相等的元素，经过稳定排序算法排序之后，相等元素之之间原有的先后顺序不变，经过不稳定的排序算法排序之后，相同元素之间原有的先后顺序发生了改变。
看一个例子，有这样一组数据2，9，3，4，8，3按照从小到大排序之后：2，3，3，4，8，9
这组数据中有两个相同的元素3，如果排序后，两个元素的位置发生了改变则为非稳定性排序，没有发生改变就为稳定性排序。
排序算法分类
冒泡排序
冒泡排序过程中包含多次冒泡操作，每一次冒泡都会遍历整个数组，依次对数组中相邻元素进行比较，看是否满足大小关系的要求，如果不满足，就将他们互换位置，一次冒泡排序至少让一个元素移动到它该存在的位置，重复n次，就完成了n个数字的排序工作。
先通过一个例子看看冒泡排序的过程，这是一组数据4,5,6,3,2,1
先看第一张图。
第一次冒泡排序，6这个元素已经在正确的位置上。要完成整个数的需要进行6次这样的排序。
但是这样的冒泡排序却还是可以进行优化，如果不用遍历n次就已经排序好了，我们可以让他提前结束。
再看一组数据。
发现到第四次的时候已经排序好了。
下面看看代码。
void bubbleSort(int[] a,int n){
if(n < 1) return;
for(int i = 0;i < n;i++){
boolean flag = false;
for(int j = i;j < n - i - 1;j++){
if(a[j] > a[j + 1]){
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
flag = true;
}
if(!flag) break;
}
}
由于冒泡排序的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，因此空间复杂度为O(1)，是一个原地排序算法。
再冒泡排序过程中，我们只针对两个不同的元素进行位置的交换，不涉及相同元素的交换，所以冒泡排序时稳定性排序。
在最好的情况下，要排序的数据已经时有序的了，我们只需要进行一遍冒泡排序，就可以得到需要的数据，此时最好时间复杂度为O(n)，如果需要全部遍历完所有元素,才能得到需要的数据，此时最坏时间复杂度为O(n^2)。
平均复杂度为O(n^2)。
插入排序
先来看这样一个问题，对于一个有序数组,往里添加一个新数据后，如何继续保持数据任然有序呢？
很容易想到，用新数据一次与数组的数据比较大小，找到他应该插入的位置，再将其插入进去就行。
这是维护动态数组有序的一个办法，即动态的往有序集合中添加数据。我们可以通过这种方法来保证数组一直是有序的。而对于一组静态数据，我们仍然可以借用这套方法。
思路是这样的，首先我们需要将数组中的元素划分为两个区间：已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组中的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到一个合适的位置将他插入进去，并保证已排序区间数据一直有序。重复这个过程，保证未排序区间为空，算法结束。
看一个例子，需要排序的数为4,5,6,1,2,3,其中左侧为已排序区间，右侧为未排序区间
插入排序的过程也包括两种操作：元素的比较和移动。当我们需要将数据a插入到已排序区间时，需要用数据a与已排序区间的数据进行比较大小，找到合适的插入点。在找到插入点之后还需要将插入点之后的元素后移。
现在来看代码。
void insertSort(int[] a,int n){
if(n < 1) return;
//留出第一个元素，作为已排序区间
for(int i = 1;i < n;i++){
//储存数组下标为1的元素
int value = a[i];
//查找元素并进行数据迁移
for(int j = i - 1;j >= 0;j--){
if(a[j] > value){
a[j + 1] = a[j];//数据后移
} else {
beak;
}
}
a[j] = value;//插入数据
}
}
插入排序的运行过程并不需要额外的存储空间，因此，他是原地排序算法。空间复杂度为O(1)
对于未排序区间的某个元素，如果在已排序区间存在与他值相同的而元素，我们选择直接将他插入到已排序区间的后面，这样就可以保证相同元素原有的先后顺序不变，所以插入排序是稳定排序算法。
如果数组是有序的，那么就不需要移动任何数据。如果我们选择从尾到头在已排序区间里查找插入位置，那么只需比较一个数据就能确定插入位置。所以最好时间复杂度为O(1)。
如图：
如果数组是倒序的，那么每次插入都是在数组的第一个位置插入新的元素，因此要移动大量的数据，时间复杂度为O(n^2)。
选择排序
选择排序的实现思路类似插入排序，也将整个数组划分为已排序区间和未排序区间。两者的不同在于：选择排序每次从未排序区间找到最小的元素，将其放到已排序区间的末尾。
看看代码
public void selectionSort(int[] a,int n){
if(n < 1) return;
for(int i = 0;i < n - 1;i++){
int minPos = i;
for(int j = i;j < n;j++){
if(a[j] < a[minPos]){
minPos = j;
}
}
//交换元素
int temp = a[i];
a[i] = a[minPos];
a[minPos] = temp;
}
}
选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
三种排序算法的比较
