近日学习了归并排序(Merge Sort), 经典的分治思想的运用：将一个大的问题分解成为若干个小问题，通过解决这些小问题从而将整个问题解决。在算法中运用十分普遍。
而归并排序则是将整个数组不断二分，直到将每个数组分成只有一个元素，再通过Merge操作将这些小数组不断归并，成一个大的数组。
归并排序较之其他排序，大大减少的时间复杂度，达到了O(nlogn)。不过，此算法也有着其缺点，那便是空间复杂度随着N的增长线性增加。
当用归并将一个大数组排序时，我们需要进行很多次归并，因此在每次归并时都创建一个新数组来存储排序结果会带来问题。我们更希望有一种能在原地归并的方法，这样就可以先将前半部分排序，再将后半部分排序，然后在数组中移动元素而不需要使用额外的空间。你可以先停下来想想应该如何实现这一点，乍一看很容易做到，但实际上已有的实现都非常复杂，尤其是和使用额外空间的方法相比。
---------- Algorithm 4th
以下给出merge方法：(merge用于操作已经排序好的数组，由于从一个元素的数组开始，所以在归并过程中所有参与merge的数组已经变成了有序的)
1 private static void merge(Comparable[] a, int lo, int mid, int hi) { 2 int i = lo, j = mid + 1; 3 4 for(int k = lo; k <= hi; k++) //暂存到另一数组中 5 aux[k] = a[k]; 6 7 for(int k = lo; k <= hi; k++) { 8 if(i > mid) //若左数组已全部归并 这放入右数组元素 9 a[k] = aux[j++]; 10 else if(j > hi) //若右数组已全部归并 同上 11 a[k] = aux[i++]; 12 else if(less(a[j], a[i])) // 若右数组元素比左数组未并入元素小 放入右数组元素 13 a[k] = aux[j++]; 14 else 15 a[k] = aux[i++]; 16 } 17 }
常规的归并排序是自顶向下，逐步拆分数组，然后进行归并。然而，我们可以换一种思路，直接从小数组开始归并，最终成为一个大的数组。实现如下
sort():
1 public static void sort(Comparable[] a) { 2 int N = a.length; 3 aux = new Comparable[N]; 4 5 for(int sz = 1; sz < N; sz = sz + sz) { //sz为当前子数组长度 由1个开始 6 // 每次翻倍 7 for(int lo = 0; lo < N - sz; lo += sz + sz) { 8 //当子数组长度为sz时 对依次对每个子数组进行归并 9 merge(a, lo, lo + sz - 1, Math.min(lo + sz +sz - 1, N - 1)); 10 } 11 } 12 13 }
Trace如下：
Vane_Tse On the Road. 2014-06-22 22:55:22