如何提高排序算法的效率
简单排序的冒泡排序和插入排序的效率都不够高，我们应该如何提高效率？
首先，我们先了解什么是逆序对？
对于下标i<j，如果A[i]>A[j]，则称(i,j)是一对逆序对(inversion)
简单排序的冒泡排序和插入排序都是交换2个相邻的元素，不断重复这个操作使得整个序列有序的。而交换2个相邻元素正好消去1个逆序对！
这就意味着，如果我们要提高排序的效率，我们要满足以下条件
1、 每次消去不止1个逆序对
2、 每次交换相隔较远的2个元素
希尔排序
对给定的数组以间隔进行排序，即先以比较大的间隔对数组进行排序，然后逐渐缩小间隔，直达间隔为1。
更小间隔的排序不会破坏之前间隔排序的有效性
选择排序
将未排序部分的最小元换成有序部分的最后位置，直至没有未排序的部分。
寻找未排序部分的最小元，选择排序是从未排序部分的第一个元素一直扫描到最后一个元素。
显然这样的效率也是不够高的，要提高选择排序的效率，我们就要提高查找未排序部分最小值的效率。我们可以用最小堆整个数据结构达到这个目的。
归并排序
归并：将两个有序的序列归并为同一个有序序列。
我们将要排序的序列分为两个部分，每个部分也平均分成两部分，直到分成最小单元。分成的两个部分进行排序，在归并起来。最后形成的序列就是有序的。