如何识别排序算法的优劣
所有的排序都需要两个过程；
- 比较大小 每个类型都有其对应的比较大小的方法
- 交换顺序 两个数交换位置需要用到中间临时变量，就像一杯可乐和一杯雪碧如何将他们杯中的饮料互换，肯定要借用一个杯子，将可乐先放进去然后再把雪碧放入到可乐杯中，最后把借用杯子中的可乐倒入雪碧的杯中。从而实现了两杯饮料的互换内容。
在数据结构和算法中有很多排序，比如冒泡排序、选择排序、插入排序等。他们的实现都会经过比较大小和交换顺序这两个过程，无疑他们的思路不太一样。那么他们如何比较优劣呢？
从三点进行判断
1.时间复杂度 ：使用大O法判断即可，实际耗时的地方在于比较的次数，交换顺序，在交换顺序时需要用到中间变量，中间变量的多少也影响耗时。
2.空间复杂度 : 原来存储数据的大小和排序之后的大小是否一致
3.稳定性 ： 如果两个数据相同，排序后他们的顺序保持不变，则该排序算法为稳定的。
下面从这个三个方面依次分析 冒泡排序、选择排序、插入排序。
冒泡排序
冒泡排序的实现思路是取第一个元素与后一个比较，如果大于后者，就与后者互换位置，不大于，就保持位置不变。再拿第二个元素与后者比较，如果大于后者，就与后者互换位置。一轮比较之后，最大的元素就移动到末尾。相当于最大的就冒出来了。再进行第二轮，第三轮，直到排序完毕。
分析冒泡排序的时间复杂度：最好情况时间复杂度是O(n)。最好的情况本身就是有序的，比较了一轮，一次冒泡，不需要移动元素，排序完成。
最坏情况时间复杂度是O(n2)。最坏情况刚好是反序的（结合本例，就是倒序），要进行（n-1）轮的比较，每轮比较都要进行（n-1）次的位置移动。
平均情况时间复杂度也是为O(n2)。这个用加权平均算概率有点复杂。理论是，n个元素，排列方式就在有 n! 种，每种情况下，比较多少轮，每次多少数据移动都不一样。有一点是确定的，上限是O(n2)，下限是o(n)。
这里，我们引入一个简化的比较方式。
有序度：满足 a[m] > a[n]，且 m > n 的一对数，
逆序度：满足 a[m] > a[n]，且 m < n 的一对数，
满序度：有序度的最大值（或逆序度的最大值）。潢序度 = 有序度 + 逆序度
对于冒泡排序，冒泡一次，有序度至少增加一，当达到满度时，排序就结束。在 n! 种排列中，有序度最小值是0，最大值是(n-1)n/2，平均值就是(n-1)n/4。有序度可以评价冒泡排序的比较操作，移动元素的操作肯定比比较的操作少，那冒泡排序的平均情况时间复杂度是 (n-1)*n/4 至 最坏情况时间复杂度之间的值，不考虑系数，低阶，得O(n2)。
冒泡排序的空间复杂度是O(1)，数据移动需要一个临时变量，属于常量级别。
冒泡排序是稳定性算法，从实现的代码，可以推知，当相同元素比对时，不会进行数据移动。
代码实现
/**
* 冒泡排序 从小到大排序
*/
public void bubbleSort(Integer[] datas) {
this.compareTimes = 0;
this.exchangeTimes = 0;
for (int i = 0; i < datas.length - 1; i++) {
for (int j = 0; j < datas.length - i - 1; j++) {
this.compareTimes++;
if (datas[j] > datas[j + 1]) {
this.exchangeTimes++;
int flag = datas[j];
datas[j] = datas[j + 1];
datas[j + 1] = flag;
}
}
}
System.out.println("比较了"+this.compareTimes);
System.out.println("交换了"+this.exchangeTimes);
}
选择排序
实现思路：把所有数据分为已排序区间和未排序区间。每次从未排序区间中，选出最小值，之后将该值与未排序区间第一个元素互换位置，此时已排序区间元素个数多了一个，未排序区间内的元素少了一个。如此循环直到未排序区间没有元素为止。
选择排序算法，最好情况时间复杂度与最坏情况时间复杂度，都是O(n2)，空间复杂度是O(1)，它是不稳定的算法。相同元素，排序后，相对位置可能发生改变。
代码实现
/**
* 选择排序
* @param datas
*/
public void selectSort(Integer[] datas){
for (int i = 0; i < datas.length; i++) {
int index = 0;
int flag = datas[0];
for (int j = 1; j < datas.length - i; j++) {
this.compareTimes ++;
if (datas[j] > datas[index]){
flag = datas[j];
index = j;
}
}
this.exchangeTimes ++;
datas[index] = datas[datas.length-i-1];
datas[datas.length-i-1] = flag;
}
System.out.println("比较了"+this.compareTimes);
System.out.println("交换了"+this.exchangeTimes);
}
插入排序
实现思路：把元素分为已排序的和未排序的。每次从未排序的元素取出第一个，与已排序的元素从尾到头逐一比较，找到插入点，将之后的元素都往后移一位，腾出位置给该元素。
记得比较的时候从后往前比较
插入排序，最好情况时间复杂度，如果已经是一个有序数组了，就不需要移动数据。只要查找到插入位置即可，每次只需要一次比较就可以找到插入位置，所以，这种情况下，最好情况时间复杂度为O(n)。
如果数组是倒序的，每次插入都相当于在数组的第一个位置插入数据，有大量移动数据的操作，所以，最坏情况时间复杂度是O(n2)。
数组中插入一个数据平均时间复杂度是O(n)，要进行n次操作，所以，平均情况时间复杂度是O(n2)。
空间复杂度是O(1)。也是一种稳定性算法。
代码实现
/**
* 插入排序
* @param datas
*/
public void insertSort(Integer[] datas){
for (int i = 1; i < datas.length; i++) {
int flag = datas[i];
int j = i-1;
for (; j >= 0; j--) {
if (datas[j] > flag){
datas[j+1] = datas[j];
}else {
break;
}
}
datas[j+1] = flag;
}
}
那么三种排序方式，哪种更常用呢？肯定不是选择排序，首先他不是稳定的的算法。那么插入排序和冒泡排序哪个更好呢？答案是插入排序。可以观察一下插入排序中的中间变量是在第一层循环中，而冒泡排序的中间变量在第二层循环中，可见在冒泡排序需要更多次创建临时变量，所以他的消耗时间更长。
