图解JavaScript合并排序

JavaScript也可以做算法练习
服务器君一共花费了589.304 ms进行了4次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

合并排序是一个O(nlogn)的算法,其基本思想就是一个分治的策略,先进行划分,然后再进行合并,下面举个例子。

有这样一组数据,{5,4,1,22,12,32,45,21},如果对它进行合并排序的话,首先将它从中间分开,这样,它就被分成了两个数组{5,4,1,22} {12,32,45,21}。

对这两个数组,也分别进行这样的操作,逐步的划分,直到不能再划分为止(每个子数组只剩下一个元素),这样,划分的过程就结束了。

划分的过程如下图所示:

接下来,我们进行合并操作,依照上图,划分过程是从上到下进行的,而合并的过程是从下往上进行的,例如上图中,最下层{5},{4}这两个数组,如果按升序排列,将他们合并后的数组就是{4,5}。{1},{22}这两个子数组合并后是{1,22}。而{4,5}与{1,22},这两个数组同属一个分支,他们也需要进行合并,由于这两个子数组本身就是有序的,所以合并的过程就是,每次从待合并的两个子数组中选取一个最小的元素,然后把这个元素放到合并后的数组中,前面两个数组合并后就是{1,4,5,22}。依次类推,直到合并到最上层结束,这是数据的排序已经完成了。

合并的过程如下图所示。这个过程是从下往上的。

C语言实现代码如下:

#include <stdlib.h>
	//合并过程
	void merge(int data[],int start,int mid,int end)
    {
		int *tmpLeft,*tmpRight;
		int leftSize,rightSize;
		int l,r,j;
		printArray(data,8);
		printf("\n");
		l = 0;
		r = 0;
		j = 0;
		leftSize = mid - start + 1;
		rightSize = end - mid;
		tmpLeft = (int *)malloc(leftSize * sizeof(int));
		tmpRight = (int *)malloc(rightSize * sizeof(int));
		while(j < leftSize)
        {
			tmpLeft[j] = data[start + j];
			j++;
		}
		j = 0;
		while(j < rightSize)
        {
			tmpRight[j] = data[mid + 1 + j];
			j++;
		}
		j = 0;
		while(l < leftSize && r < rightSize)
        {
			if(tmpLeft[l] < tmpRight[r])
            {
				data[start + j++] = tmpLeft[l++];
			}
            else
            {
				data[start + j++] = tmpRight[r++];
			}        
		}
		while(l < leftSize)
        {
			data[start + j++] = tmpLeft[l++];
		}
		while(r < rightSize)
        {
			data[start + j++] = tmpRight[r++];
		}
		free(tmpLeft);
		free(tmpRight);
	}
void merge_sort(int data[],int start,int end)
{
	int mid;
	if(start < end)
    {
		//将数组划分
		mid = (start + end) / 2;
		merge_sort(data,start,mid);
		merge_sort(data,mid + 1,end);
		//合并划分后的两个数组
		merge(data,start,mid,end);
	}
}  

javascript版本:

function merge(left, right)
{
	var result = [];
	while (left.length > 0 && right.length > 0)
    {
		if (left[0] < right[0])
        {
			result.push(left.shift());//把最小的最先取出,放到结果集中
		} 
        else 
        {
			result.push(right.shift());
		}
	} 
    return result.concat(left).concat(right);//剩下的就是合并,这样就排好序了
}
function mergeSort(array)
{
	if (array.length == 1) 
    {
		return array;
	}
	var middle = Math.floor(array.length / 2),//求出中点
	left = array.slice(0, middle),//分割数组
	right = array.slice(middle);
	return merge(mergeSort(left), mergeSort(right));//递归合并与排序
}  

ruby版本:

def merge(left, right)
final = []
until left.empty? or right.empty?
final << ( left.first < right.first ? left.shift : right.shift )
end
final + left + right
end
def mergeSort(array)
return array if array.size < 2
left = array.first(array.size/2)
right = array.last(array.size - array.size/2)
merge(mergeSort(left), mergeSort(right))
end  

可运行版本:

<script language="javascript">
function merge(left, right)
{  
	var result = [];  
	while (left.length > 0 && right.length > 0)
	{  
    	if (left[0] < right[0])
		{  
      		result.push(left.shift());//把最小的最先取出,放到结果集中  
    	} 
		else 
		{  
      		result.push(right.shift());  
    	}  
  	} 
	return result.concat(left).concat(right);//剩下的就是合并,这样就排好序了  
}  
function mergeSort(array)
{  
  	if (array.length == 1) 
	{  
    	return array;  
  	}  
  	var middle = Math.floor(array.length / 2),//求出中点  
  		left = array.slice(0, middle),//分割数组  
  		right = array.slice(middle);  
  	return merge(mergeSort(left), mergeSort(right));//递归合并与排序  
}  
  
var a = [49, 38 ,65 ,97 ,76, 13, 27]  
  
document.write(mergeSort(a)); 
</script>
  

运行结果:

本文地址:http://www.nowamagic.net/librarys/veda/detail/1241,欢迎访问原出处。

不打个分吗? 还木有人打分噢!

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1241

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《php和mysql web开发(原书第4版)》 Luke Welling (作者), Laura Thomson (作者), 武欣 (译者)

《php和mysql web开发(原书第4版)》将PHP开发与MySQL应用相结合,分别对PHP和MySQL做了深入浅出的分析,不仅介绍PHP和MySQL的一般概念,而且对PHP和MySQL的Web应用做了较全面的阐述,并包括几个经典且实用的例子。《php和mysql web开发(原书第4版)》是第4版,经过了全面的更新、重写和扩展,包括PHP 5.3最新改进的特性(例如,更好的错误和异常处理),MySQL的存储过程和存储引擎,Ajax技术与Web 2.0以及Web应用需要注意的安全问题。

更多计算机宝库...