189 8069 5689

合并排序代码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));

}

}


网站标题:合并排序代码Java 合并排序代码Java
浏览路径:http://cdxtjz.cn/article/hjccce.html

其他资讯