摘自
http://www.vogella.com/articles/JavaAlgorithmsMergesort/article.html
这个对本人实在是很有难度。。
起初是在java的Collections.sort()的api里面看到, 说是java所使用的排序是修改了的mergesort .- The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist).
网上查了一下就看到这个。
拿着纸和比在debug模式里研究了半天,大概明白了那么一点点。
实现代码:
public class Mergesort
{
private int[] numbers;
/**
* int[] helper在算法中起到存放数据并和numbers里进行大小比较的作用。
*/
private int[] helper;
/**
* number是要排序的数组的大小
*/
private int number;
public void sort(int[] values){
this.numbers=values;
number=values.length;
this.helper=new int[number];
mergesort(0,number-1);
}
private void mergesort(int low, int high){
//check if low is smaller than high, if not
//then the array is sorted.
if(low<high){
//get the index of the element which is in the middle
int middle=low+(high-low)/2;
//sort the left side of the array
mergesort(low,middle);
//sort the right side of the array
mergesort(middle+1, high);
//combine them both
merge(low,middle,high);
}
}
private void merge(int low, int middle, int high){
//copy both parts into the helper array
for(int i=low; i<=high; i++){
helper[i]=numbers[i];
}
int i=low;
int j=middle+1;
int k=low;
//copy the smallest values from either the left or the right
//side back to the original array
while(i<=middle&&j<=high){
//这里进行排序,如果helper[i]和helper[j]根据大小进行位置调整
//比如helper[0]==3和helper[1]==1,则进入if里面
//number[1]=helper[0]
if(helper[i]<=helper[j]){
numbers[k]=helper[i];
i++;
}else{
numbers[k]=helper[j];
j++;
}
//k代表numbers的索引,是一定会加1的。因为这里就是要将helper[i]
//和helper[j]做比较。最终将小的那个值放入numbers[k]
k++;
}
//copy the rest of the left side of the array into the target array
while(i<=middle){
//完成刚才排序的位置调整
numbers[k]=helper[i];
k++;
i++;
}
}
}
测试代码:
public class Test01
{
public static void main(String[] args)
{
int[] numbers={3,1,2,6,7,3,4};
Mergesort sorter=new Mergesort();
sorter.sort(numbers);
for(int i:numbers){
System.out.println(i);
}
//1 2 3 3 4 6 7
}
}
jdk的各种算法包括binary search,mergesort都在Arrays类里面。
都是加入了泛型的。
都是sun公司的高手写的。 想提高的话可以去研究研究。。
分享到:
相关推荐
归并排序 归并排序算法的实现。
归并排序并行和顺序归并排序算法
归并排序 归并排序 归并排序 归并排序 归并排序
归并排序 (相当)无痛依赖类型编程的案例:Agda 中完全认证的归并排序 Agda 中的合并排序正确性证明 我们在 Agda 中展示了一个经过完全认证的合并排序版本。 它的特点是:终止的句法保证(即不需要明确的终止证明)...
MergeSort合并排序
用C++实现归并排序,题目基于MIT的算法导论中的第二章中的归并排序算法要求,visual studio 2010 实现
归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 算法步骤: 1. 申请空间,使其大小为两个已经排序序列之...
计算机算法课程的作业,用c++实现了归并排序和快速排序,并比较了两种算法的速度。测试数据为随机生成,可设置为10万、100万、1000万大小的数组。在代码中提供了详细的注释,在容易出错的地方进行了解释。下面是得到...
归并排序,两种实现方法,一种是递归实现,另一种是非递归实现……可直接在vc6.0平台上编译运行,并按要求输入,便可从小到大的顺序输出……
排序算法-归并排序详细讲解(MergeSort)
%mergesort 分治算法——归并排序 %divide——将数组一分为二 %conquer——对两部分数组分别排序 %combine——将各自排好序的数组融合 %以此类推递归调用
归并排序执行三路归并排序
代码是归并排序的c语言实现,归并算法MergeSortList.cpp
//归并排序 public void MergeSort(int low, int high, int[] a) { int mid, i, j, k; int[] b = new int[high+1]; if (low >= high) { return; } mid = (low + high) / 2; MergeSort(low,mid,a); ...
使用C++书写的归并排序算法,希望对各位有用。也请大牛指教代码中有何不足的地方!
实现归并排序的c++代码,根据算法导论书籍内伪代码改写
printf("\t6: 归并排序\n"); printf("\t7: 希尔排序\n"); printf("\t***************************\n"); scanf("%d",&i); //输入整数1-7,选择排序方式 switch (i){ case 1: InsertSort(R); break; //值为1,...
I created a complex MIPS assembler program and execute a simulation with SPIM.In my program,I implemented several sub-programs:mergesort,binary search,a sum total value,average,maximum and minimum. ...
mergeSort 方法实现了归并排序算法。它使用递归的方式将数组不断划分为更小的子数组,直到每个子数组只有一个元素,然后再依次将这些子数组进行合并,从而实现排序。 merge 方法用于合并两个有序子数组。它借助两个...