排序（上）

插入排序和冒泡排序的时间复杂度都是O（n²），在实际的软件开发里，为什么我们更倾向于插入排序算法而不是冒泡排序算法呢？

1、如何分析一个“排序算法”

学习排序算法，我们除了学习它的算法原理和代码实现外，更重要的是学会如何评价、分析一个排序算法。分析一个排序算法，要从哪几个方面入手呢？

1.1、排序算法的执行效率

在分析排序算法的时间复杂度时，要分别给出最好、最坏、平均情况下的时间复杂度。除此之外，还要说出最好、最坏时间复杂度对应的要排序的原始数据。我们要知道排序算法在不同数据下的性能表现。

1.2、时间复杂度的系数、常数、低阶

时间复杂度反应的是数据规模n很大时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。但是在实际的开发中，我们排序的可能是10个、100个这样规模很小的数据。所以在对同一阶时间复杂度的排序算法性能进行比较的时候，我们就要把系数、常数、低阶考虑进来。

1.3、比较次数和交换（移动）次数

基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，我们在分析排序算法的执行效率的时候，应该把比较次数和交换（移动）次数也考虑进去。

1.4、排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。不过针对排序算法的空间复杂度，我们引入一个新的概念，原地排序。原地排序算法，就是特指空间复杂度是O（1）的排序算法。

1.5、排序算法的稳定性

稳定性是指，如果待排序的序列中存在相等的值，经过排序之后，相等元素之间原有的先后顺序不变。
比如一组数据2,9,3,4,3，排序之后，就是2,3,3,4,9。
这数组里面有两个3，经过某种排序算法之后，如果两个3的前后顺序没有变，那我们就把这种排序算法叫稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫做不稳定的排序算法。
在软件开发中，我们要排序的往往不是单纯的整数，而是一组对象，我们需要按照对象的某个属性进行排序。
比如，我们要对“订单”排序，订单有两个属性，一个是下单时间，另一个是订单金额。如果我们现在有10万条数据，我们希望按照金额从小到大进行排序；对于金额相同的订单，我们希望按照下单时间，从早到晚排序。
借助稳定排序算法，我们可以先对下单时间进行排序，然后再将排序好的数据按照金额进行排序。两遍排序之后，就能解决问题。稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。

排序订单.jpg

2、冒泡排序

冒泡的排序过程

冒泡排序.jpg

实际上，冒泡过程还可以优化，当某次冒泡操作已经没有数据交换时，说明已经达到完全有序。

 /**
     * 冒泡排序
     * @param a
     * @param count 数组长度
     */
    public void maopaoSort(int[] a,int count){
        if(count<=1){
            return;
        }
        for(int i=0;i<count;i++){
            //标记本轮遍历，是否交换过
            boolean isChanged = false;
            for(int j=0;i<count-1;j++){
                if(a[j]>a[j+1]){
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                    isChanged = true;
                }
            }
            //本轮遍历没有交换元素，跳出排序
            if(!isChanged){
                break;
            }
        }
    }

现在，我们分析下面三个问题

1、冒泡排序是原地排序算法吗？

冒泡的过程只涉及相邻元素的比较和交换，需要常量级的临时空间，所以它的空间复杂度是O（1），是一个原地算法。

2、冒泡排序是稳定的排序算法吗？

在冒泡排序中，只有交换，才可以改变两个元素的前后顺序。当两个相邻元素相等时，我们不做交换，所以冒泡排序是稳定的排序算法。

3、冒泡排序的时间复杂度是多少？

最好情况，数组已经是有序的，时间复杂度是O（n）。最坏情况，数组是倒序的，时间复杂度是O（n²）。
下面通过有序度和逆序度两个概念来分析平均时间复杂度。
有序度是数组中具有有序关系的元素对的个数。

有序度.jpg

逆序度的概念与有序度刚好相反。
逆序度=满有序度-有序度。冒泡排序，每交换一次，有序度就加1，不管怎么改进，交换次序总是确定的，即为逆序度。

3、插入排序

一个有序的数组，我们往里面添加一个新的数据之后，如何保持新的数组也是有序的？其实只要遍历数组，找到数据应该插入位置即可。

插入排序.jpg

首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想，是取未排序区间的元素，在已排序区间内，找到合适的位置，将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间元素为空。

插入排序举例.jpg

/**
     * 插入排序
     * @param a
     * @param count
     */
    public void insertSort(int[] a,int count){
        if(count<=1){
            return;
        }
        for(int i=1;i<count;i++){
            int value = a[i];
            int j = i-1;
            for(;j>=0;j--){
                if(value<a[j]){
                    a[j+1] = a[j];
                }else{
                    break;
                }
            }
            a[j+1] = value;
        }
    }

3.1、插入排序是原地排序算法吗

从代码中可以看出，插入排序不需要额外的存储空间，所以该空间复杂度是O（1），也就是说，是一个原地排序算法。

3.2、插入排序是稳定的排序算法吗

在插入排序中，对于值相同的元素，我们可以选择将后面的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

3.3、插入排序的时间复杂度是多少

如果数组是有序的，每次只需要比较一个数据就能确定插入的位置，最好的情况时间复杂度是O（n）。
如果数组是倒序的，每次插入都相当于在数组的第一个位置插入数据，所以最坏的时间复杂度是O（n²）。

4、选择排序

选择排序算法的实现思路类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

选择排序.jpg

选择排序的空间复杂度是O（1），是一种原地排序算法。选择排序的最好、最坏和平均时间复杂度都是O（n²）。
选择排序是一种不稳定的排序算法，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，破坏了稳定性。

5、选择排序还是冒泡排序

冒泡排序和插入排序的时间复杂度都是O（n²），都是原地排序算法。但是从代码实现上看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要三个赋值操作，而选择排序只需要一个。

if(a[j]>a[j+1]){
  int temp = a[j];
  a[j] = a[j+1];
  a[j+1] = temp;
  isChanged = true;
}

if(value<a[j]){
  a[j+1] = a[j];
}

我们把执行一个赋值语句的时间粗略的记为单位时间（unit_time），然后分别用冒泡排序和插入排序对同一个逆序度是K的数组进行排序。用冒泡排序，需要进行K次交换操作，每次需要3个赋值操作，所以交换操作总耗时就是3*unit_time，而插入排序只需要unit_time。
如果我们希望把性能做到极致，还是首选插入排序。