排序算法(2)
排序算法1中，对于选择排序和插入排序进行了介绍，通过代码，可以看出，假设有一个给定的乱序数组，插入排序因为都只能通过交换相邻的元素，于是得到的时间复杂度是相对来说比较高的。从这也可以看出，在插入排序中，元素只能缓慢的从一端到另一端。从这就可以观察得到，这应该还有优化的空间，于是，基于插入排序的改进算法进一步提出。
希尔排序
既然插入排序对于乱序对象的处理能力比较差，也就是某个对象需要从一端到另外一端。基于这个思想，能不能不让对象只一个一个相邻交换。因此，希尔排序通过扩大每个对象的间隔交换值h，从而保证任意间隔值h都都是有序的；这样通过较大的将间隔值，从而保证对象不是一个一个相邻移动，从而提高效率。看代码，此代码还是基于排序算法1中的模板，以下只展示sort部分，其余部分可参见排序算法1：
//目标：实现a[]按照升序排列
public static void sort(Comparable[] a){
int N = a.length;
//数据间隔h时为有序。
int h = 1;
//找到最大的间隔h,除以几可以根据需要进行调节
while(h < N/3){
h = 3*h + 1;
}
while(h >= 1){
for (int i = h; i < N ; i++) {
for (int j = i; j >= h && less(a[j],a[j-h]); j-=h) {
exch(a,j,j-h);
}
}
show(a);
h = h/3;
}
?
}
在此，可能体会不到希尔排序起到了什么作用，通过一个简单的小实验，体会下
希尔排序结果
原始数组：20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
第一次：7 6 5 4 3 2 1 13 12 11 10 9 8 20 19 18 17 16 15 14
第二次：3 2 1 4 7 6 5 9 8 11 10 13 12 16 15 14 17 20 19 18
第三次：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
通过观察可以得到，希尔排序很快就可以把乱序偏后的元素移动到另外一边，这就是希尔排序的强大之处。所以说，在此也会有很多疑问，如何进行选择间隔递增的h值呢。这个在很多论文都进行了研究，但是是一个比较难的问题，实际中，可以通过调节h值进行测试。也可以看出，希尔排序解决了插入排序在乱序情况下移动困难的问题。并且实践也证明，希尔排序对于中等大小的数组的运行时间是 可以接受的，并且也不需要额外的内存空间。
归并排序
通过希尔排序，可以知道，其思想是通过控制全部对象中间隔长度为h的保持有序。但基于此是否还可以想到，能否通过一直保证部分有序，最终实现全局有序呢。归并排序通过这样的思想。首先给的的对象数组，一分为二，然后有两个子数组对象，通过保证两个子数组对象有序，然后将结果进行归并，从而达到全局有序。也就是说，归并排序通过分治的思想，最后达到全部对象有序。
其实想法是比较简单的，但实现起来却要考虑很多问题。比如说，对于一个很长的大数组来说，如果每次归并都要创建一个新数组来进行存储归并结果，这导致很大的空间浪费，因此，在这可以考虑原地归并的思路，也就是创建一个和原数组大小一样的数组，进行每次的归并存储。归并排序的代码如下
private static Comparable[] aux;
//将两个已排序数组对象进行归并
public static void merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo, j = mid + 1;
for (int k = 0; k <= hi; k++) {
aux[k] = a[k];
}
for (int k = 0; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
//排序
public static void sort(Comparable[] a) {
aux = new Comparable[a.length];
//整个进行排序
sort(a, 0, a.length - 1);
}
?
private static void sort(Comparable[] a, int lo, int hi) {
if(hi <= lo) return;//递归出口
//二分
int mid = lo + (hi-lo)/2;
sort(a, lo, mid);//保证左边有序
sort(a, mid+1, hi);//保证右边有序
merge(a, lo, mid, hi);//进行归并
}
上述是一个自顶向下的归并排序，也就是从整个数组为开端，一步一步的分治，从而达到全部排序的目的。当然，也可以通过自下往上的方式达到目的，在此不再重复赘述。对于归并排序的算法复杂度，可以看见，归并排序似乎有点二分的感觉，是的，每一个都把数据进行二分，因此时间复杂度相对于插入或者选择肯定是降低了的，具体的时间复杂度不在详细讨论，后面会对各种算法的时间空间复杂度进行一个详细的论述。
总结