排序

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

1. 排序算法的执行效率
   1.1 最好情况、最坏情况、平均情况时间复杂度
   1.2 时间复杂度的系数、常数 、低阶
   1.3 比较次数和交换（或移动）次数
2. 排序算法的内存消耗
3. 排序算法的稳定性

为什么要考察排序算法的稳定性呢？
答：在真正软件开发中，我们要排序的往往不是单纯的整数，而是一组对象，我们需要按照对象的某个key来排序。比如有下单时间和商品价格两个属性，对价格排序后还需要在相同价格内保证下单时间有序的话，就需要稳定排序算法了。

冒泡排序

冒牌排序代码
isOrderly用于在发现数组已经有序时进行提前结束排序

static void bubbleSort(int[] arr){
        int len=arr.length;
        for(int i=0;i<len;i++){
            boolean isOrderly=true;
            for(int j=0;j<len-i-1;j++){
                if(arr[j]>arr[j+1]){
                    isOrderly=false;
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
            }
            if(isOrderly){ break; }
        }
    }

算法分析：
1、空间复杂度：只有交换操作和几个临时变量 即O(1)
2、稳定性：代码中相邻两数相等时不会进行交换，维护了稳定性
3、时间复杂度：
最好情况O(n) （至少也要一次遍历）
最坏情况O(n^2) （纯粹的倒序）

作者这里讲了一种分析平均时间复杂度的方法：使用逆序数和有序数
逆序对：a[i] >= a[j] 且 i < j，则这里称为一个逆序对
逆序数：数组中逆序对的个数，有序对同理
我们还可以得到一个公式：逆序度=满有序度-有序度。我们排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，

插入排序

思想：将数组中的数据分为两个区间，已排序区间和未排序区间，取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

static void insertionSort(int[] arr){
        int len=arr.length;
        for(int i=1;i<len;i++){
            int temp=arr[i];
            int j=i-1;
            for(;j>=0;j--){
                if(arr[j]<=temp){
                    break;
                }
                arr[j+1]=arr[j];
            }
            //注意这里必须写在外面，不能写在break前一句
            arr[j+1]=temp;
        }
    }

算法分析：
1、空间复杂度：O(1)
2、稳定性：对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。
3、时间复杂度：最好O(n)，最坏和平均O(n^2)

选择排序

也是把数组分为有序和无序的两部分，但是每次是从无序中选取最值，放在有序部分的尾部，但是因为这个“放在”其实是交换操作，使得选择排序不具有稳定性

static void selectionSort(int[] arr){
  	int len=arr.length;
    for(int i=0;i<len-1;i++){
        int min=Integer.MAX_VALUE;
        int tag=i;
        //得到无序部分最小值
        for(int j=i;j<len;j++){
            if(min>arr[j]){
                min=arr[j];
                tag=j;
            }
        }
        if(tag!=i){
            int temp=arr[tag];
            arr[tag]=arr[i];
            arr[i]=temp;
        }
    }
}

算法分析：
1、空间复杂度：O(1)
2、稳定性：不稳定
3、时间复杂度：最好O(n)，最坏和平均O(n^2)

这里作者还说了一下

我们把执行一个赋值语句的时间粗略地计为单位时间（unit_time），然后分别用冒泡排序和插入排序对同一个逆序度是K的数组进行排序。用冒泡排序，需要K次交换操作，每次需要3个赋值语句，所以交换操作总耗时就是3*K单位时间。而插入排序中数据移动操作只需要K个单位时间。
这个只是我们非常理论的分析，为了实验，针对上面的冒泡排序和插入排序的Java代码，我写了一个性能对比测试程序，随机生成10000个数组，每个数组中包含200个数据，然后在我的机器上分别用冒泡和插入排序算法来排序，冒泡排序算法大约700ms才能执行完成，而插入排序只需要100ms左右就能搞定！
所以，虽然冒泡排序和插入排序在时间复杂度上是一样的，都是O(n2)，但是如果我们希望把性能优化做到极致，那肯定首选插入排序。

然后翻出来我以前写的希尔排序（算是插入排序的优化吧）
空间复杂度O(1)，平均时间复杂度O(nlogn)
下面是我从别人博客那复制过来的演示动图

void ShellSort(int N,int *a)
{
	int gap,temp;
	int i,j;
	for(gap=N/2;gap>0;gap/=2)
	{
		for(i=gap+1;i<=N;i++)
		{
			temp=a[i];
			for(j=i-gap;j>=0&&a[j]>temp;j-=gap)
			{
				a[j+gap]=a[j];
			}
			a[j+gap]=temp;
		}
	}
}