如何识别排序算法的优劣

  所有的排序都需要两个过程；

1. 比较大小 每个类型都有其对应的比较大小的方法
2. 交换顺序 两个数交换位置需要用到中间临时变量，就像一杯可乐和一杯雪碧如何将他们杯中的饮料互换，肯定要借用一个杯子，将可乐先放进去然后再把雪碧放入到可乐杯中，最后把借用杯子中的可乐倒入雪碧的杯中。从而实现了两杯饮料的互换内容。
   在数据结构和算法中有很多排序，比如冒泡排序、选择排序、插入排序等。他们的实现都会经过比较大小和交换顺序这两个过程，无疑他们的思路不太一样。那么他们如何比较优劣呢？
   从三点进行判断
   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;
        }
    }

那么三种排序方式，哪种更常用呢？肯定不是选择排序，首先他不是稳定的的算法。那么插入排序和冒泡排序哪个更好呢？答案是插入排序。可以观察一下插入排序中的中间变量是在第一层循环中，而冒泡排序的中间变量在第二层循环中，可见在冒泡排序需要更多次创建临时变量，所以他的消耗时间更长。