另一道面试题是实现归并排序,当然,本人很不喜欢递归法,因为递归一般都是没有迭代法好。所以首选都是用迭代法,但是迭代法确实是难做啊,至底而上的思想不好把握。
这是我的实现代码
/*
*
* 非递归版归并排序,思路如下:
* 至底而上的思路,二和一,四和一,最后是一半一半和整。
* 循环从左到右依次执行,为了节省空间,我节省了右序列,将原数列的一部分作为右小序列,这一部分不会被覆盖。
* 作者:吴伟欣
* */
function mergeSearch(arr)
{
var len = arr.length;
var left_s,left_e,right_s,right_e;
var left_list = null; //只需要一半即可,节省空间,因为原数组后半段是不可能被覆盖的。
for (var i = 1;i<len;i*=2)
{
var next = 0;//每一次合并以后初始化next
for(left_s=0;left_s<len;left_s=right_e)
{
next = left_s;
left_e = right_s = left_s + i;
right_e = right_s + i;
if(right_e > len)
{
right_e = len;
}
//复制左边的数组
left_list = arr.slice(left_s,left_e);
var left_index = 0;
var left_len = left_list.length;//空间换取时间
while(left_index<left_len) //归并代码
{
if((right_s>=right_e)||(left_list[left_index]<=arr[right_s])) //短路逻辑,优化性能
{
arr[next++] = left_list[left_index++];
}else
{
arr[next++] = arr[right_s++];
}
}
}
}
}
//测试代码
var a = [3,7,1,2,10,9,1,6];
var b = [10,9,8,2,7,10,10,10,9,9,9,8];
mergeSearch(a);
mergeSearch(b);
alert(a);
alert(b);
运行结果还是正确的:
首先,归并思路应该不难写。我的思路是这样的,先整体思维是,很自然的从单个合并,然后在合并,最后合成一个整体。每次都是两两合并。细节方面是,合并的时候到底怎么做比较好呢,可以想象,我们可以创建一个整数列,然后合并的时候放进去,整条合并完,在给原来的,这当然是很笨的方式。我采用的是,每两个需要合并的子序列肯定是不可以在原数列的空间上进行排序,但是至少需要多少空间呢,你会发现,这两个序列的右边那个是不可能被覆盖,那意味着,这两个序列的右边序列是可以在原数列上玩,左序列我会每次创建空间,然后放进原数列。短路逻辑那里,是考虑到如果左边序列完全排序好了,那么右序列默认是在原序列上,并且排好序,所以很明显已经搞定,后面的是不需要在动了,直接进入下一个序列合并。整体最坏复杂度,应该是这样的,一个logn 和一个n循环,整体应该是nlogn