合并排序
package algorithm;
/**
* May 26, 2009
* version 1.1
* @author qinshuangping
*/
public class MergeSort {
/**
* 合并排序(也称归并排序)
* 归并操作的工作原理如下(网上找的这个原理和这个例子似乎对不大上,不过大体上差不多吧):
* 1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
* 2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
* 3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
* 4. 重复步骤3直到某一指针达到序列尾
* 5. 将另一序列剩下的所有元素直接复制到合并序列尾
*/
/**
* 主要是对数组进行细分,应用了递归
* @param ia 待排序的数组
* @param p 数组的开始位置(第一次调用时为0)
* @param r 数组的结束位置(第一次调用时为数组长度-1)
*/
void mergeSort(int ia[], int p, int r){
if(p<r ){
int q = (p+r)/2;
mergeSort(ia, p, q);
mergeSort(ia, q+1, r);
merge(ia, p, q, r);//排序主方法
}
}
/**
* 对已排序数组的两段合并成一段最终的排序
* 如:数组a[] = {8,9,14,17,1,2,3,4,7};p=0;r=8;q=3;
* 则调用该方法为merge(a,0,3,8)
* 通过merge()方法后数组a变成{1,2,3,4,7,8,9,14,17}
* 排序步骤:
* 1.新建两个数组
* 2.对两个数组赋值,
* a.ia1为ia[p]--ia[q],为前段数组,数组长度为[q-p+1]
* b.ia2为ia[q+1]--ia[r],为后段数组,数组长度为[r-q]
* 3.设置k=p,主要是为了对待排序的数组进行赋值
* 4.当k<r时进行循环,即带排序的数组还没有排好序
* 5.对ia1中的数组和ia2中的数组进行比较,即是进行排序,并把结果放进ia中,k++
* @param ia 需要进行排序的数组
* @param p 数组的开始位置
* @param q 数组的中间位置(p+r)/2
* @param r 数组的结束位置
*/
public void merge(int ia[], int p, int q, int r){
int n1 = q - p + 1; // n1 = [p, q]
int n2 = r - q; // n2 = (q, r]
int ia1[]=new int[n1+1];
int ia2[]=new int[n2+1];
for(int i=0; i<n1; i++){
ia1[i] = ia[p+i];
}
//哨兵?
ia1[n1] = 0x7FFFFFFF; // sentinel
for(int i=0; i<n2; i++){
ia2[i] = ia[q+1+i];
}
ia2[n2] = 0x7FFFFFFF; // sentinel
int i, j, k;
i = j = 0;
k = p;
while( k <= r ){
if( ia1[i]<=ia2[j] ){
ia[k] = ia1[i];
i++;
}else{
ia[k] = ia2[j];
j++;
}
k++;
}
}
public static void main(String[] args){
int a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
MergeSort ms=new MergeSort();
ms.mergeSort(a, 0, a.length-1);
for(int i=0; i<a.length; i++){
System.out.print(a[i]+",");
}
// int a[] = {8,9,14,17,1,2,3,4,7};
// MergeSort ms=new MergeSort();
// ms.merge(a, 0, 3, a.length-1);
// for(int i=0; i<a.length; i++){
// System.out.print(a[i]+",");
// }
}
}
分享到:
相关推荐
选择排序、插入排序、冒泡排序以及快速排序和归并排序的C语言实现,绝对可用
归并排序C语言实现
基于visual studio2010,的程序开发,...............................................................................................
一年前做的排序动画,归并排序动画一直未完成,今天完成了,与大家共享
编写选择排序,插入排序,自顶向上合并排序,合并排序,快速排序,理解各排序算法的实现原理,加深对排序算法的理解。
归并排序过程的前半部分,过程示意图见下,从图中可见,步骤1,2,3,4一直分割区间,等到步骤5时,左右区间长度都为1,此时发生一次归并,结果再与另一个区间长度为1的归并,即步骤6;步骤7分割,步骤8归并,步骤9...
它的基本思想是:将待排序的数列分成两个小的数列,先对两个子集进行排序,然后进行两个有序子集的合并,形成... 设归并排序的当前区间是R[low..high],分治法的三个步骤是: ①分解:将当前区间一分为二,即求分裂点
C++ 将产生的随机数存入文件中,使用冒泡、快速、归并、希尔排序并计算排序时间,将排序时间存入excel中
合并排序(MERGE SORT)是又一类不同的排序方法,合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列,因此它又叫归并算法。它的基本思想就是假设数组A有N个元素,那么可以看成数组A是又N个...
算法设计,给出归并排序的C++实现代码,并利用给随机数方式求运行时间
c++实现的合并排序算法 用递归和非递归两种方式实现的
在归并排序中,合并操作是将两个有序表合并成一个有序表的过程。 归并排序的原理是将数组不断分成两半,直到每个子数组只有一个元素,然后将这些子数组合并成一个有序的数组。合并操作需要两个子数组都是有序的,...
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段...
归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
归并排序,消除递归归并排序,快排,Java实现
1、 掌握直接插入排序、折半插入排序、冒泡排序、快速排序和归并排序等排序算 法的思想。 2、 实现直接插入排序、折半插入排序、冒泡排序、快速排序和归并排序等排序算 法的编程应用。 二、 问题描述 实现数据的折半...
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段...
算法练习,仅供参考 用递归实现的一个归并算法 void Merge(int *A,int p,int q,int r)实现对已排序的两部分合并 void Merge_sort(int *A,int p,int r) 调用上述函数实现排序
绝大多数归并算法是每次n/2分,然后再合并排序。而本算法是将n维数组每次分为根号n后递归后归并排序,思想和二路归并类似,不同!
一个算法设计与分析的实验报告,比较归并排序与快速排序的时间差异,这里采用在一个java程序中对随机生成的任意个数分别进行两种方法的排序并记录各自的时间,最后得出结论。 本实验报告附代码以及详细解释