合并排序代码Java 合并排序代码Java

java归并排序

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是归并排序算法：

创新互联公司主要从事网站制作、网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务石泉,10多年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18982081108

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）； 自下而上的迭代；

在《数据结构与算法 JavaScript 描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而，在 JavaScript 中这种方式不太可行，因为这个算法的递归深度对它来讲太深了。

说实话，我不太理解这句话。意思是 JavaScript 编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

2. 算法步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

设定两个指针，最初位置分别为两个已经排序序列的起始位置；

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

重复步骤 3 直到某一指针达到序列尾；

将另一序列剩下的所有元素直接复制到合并序列尾。

3. 动图演示

代码实现 JavaScript 实例 function mergeSort ( arr ) {   // 采用自上而下的递归方法

var len = arr. length ;

if ( len

java合并排序

从

代码

可以看出楼主是一个

新手

，你的这个错误是

Comparable

a[]

=

{3,

6,

4,

12,

8,

5,

14

};这里，

3,6,4这些数据不是Comparable

实现类，为什么会不是呢？为什么会在这里出错呢？我猜测楼主的这个代码曾经在别的环境下可以运行的，你这里错误的应该是

你现在

的JDK是1.4的，活着你的编译环境是1.4的，而要Comparable

a[]

=

{3,

6,

4,

12,

8,

5,

14

};能被正常编译需要在1.5的环境下，因为1.5的

特性

使得3,6,4这些

数字

可以当作一个Integer

对象

来处理，而Integer类是实现了Comparable

接口

的。

下面是如果你是用eclipse的话，右键点击项目－－properties---JAVA

compiler修改编译环境

java编程合并排序算法

package p1;

import java.util.Arrays;

public class Guy

{

/**

 * 归并排序

 */

private static void mergeSort ( int[] array, int start, int end, int[] tempArray )

{

if (end = start)

{

return;

}

int middle = ( start + end ) / 2;

mergeSort (array, start, middle, tempArray);

mergeSort (array, middle + 1, end, tempArray);

int k = 0, leftIndex = 0, rightIndex = end - start;

System.arraycopy (array, start, tempArray, 0, middle - start + 1);

for ( int i = 0; i  end - middle; i++ )

{

tempArray[end - start - i] = array[middle + i + 1];

}

while (k  end - start + 1)

{

if (tempArray[rightIndex]  tempArray[leftIndex]) // 从小到大

{

array[k + start] = tempArray[leftIndex++];

}

else

{

array[k + start] = tempArray[rightIndex--];

}

k++;

}

}

public static void main ( String[] args )

{

int[] array = new int[] { 11, 213, 134, 65, 77, 78, 23, 43 };

mergeSort (array, 0, array.length - 1, new int[array.length]);

System.out.println (Arrays.toString (array));

}

}