`
woxiaoe
  • 浏览: 283307 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

归并排序

阅读更多

用java写的一个归并排序,测试的时候发现JDK默认的排序也是用归并排序实现的,真好测试一下,发现效率上差距还是好大的,纠结!

 

package com.woxiaoe.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

/**
 * 合并排序
 * @author 小e
 *
 * 2010-4-4 下午11:25:57
 */
public class MergeSort {
	public static void mergeSortManager(Comparable[] a){
		Comparable[] d = a.clone();
		mergeSort(a,d,0,a.length - 1);
	}
	public static void mergeSort(Comparable[] a,Comparable[] d,int left,int right){
		
		if(left < right){
			int middle = (left + right)>>>1;
			mergeSort(a, d,left, middle);
			mergeSort(a,d, middle + 1, right);
			merge(a,d,left,middle,right);
		}
	}
	private static void merge(Comparable[] a,Comparable[] d, int left, int middle, int right) {
		
		int i = left;
		int j = middle + 1;
		int index = left;
		
		while((i<= middle) && (j<= right)){
		if(a[i].compareTo(a[j]) <= 0){
			d[index ++] = a[i++];
		}else{
			d[index ++] = a[j++];
		}
		}
		
		/*for(i=left,j=middle + 1; i<=middle&&j<=right;){
		//while((i<= middle) && (j<= right)){
			if(a[i].compareTo(a[j]) <= 0){
				d[index ++] = a[i++];
			}else{
				d[index ++] = a[j++];
			}
		}*/
		if( i > middle){
			for(int k = j; k<=right; k++){
				d[index++] = a[k];
			}
		}else{
			for(int k = i; k<=middle; k++){
				d[index++] = a[k];
			}
		}
		//System.arraycopy(d, left,a,left ,right - left);
		for(int k = left; k <= right; k++){
			a[k] = d[k];
		}
	}
	
	public static void main(String[] args) {
		
		Random r = new Random();
		List<Comparable[]> list = new ArrayList<Comparable[]>();
		for(int i = 0; i<500; i++){
			Item[] items = new Item[5000];
			for(int j = 0; j < 5000; j++){
				items[j] = new Item(r.nextInt(1000));
			}
			list.add(items);
		}
		
		//System.out.println("in" + Arrays.toString(items));
		//mergeSort(items, 0, 9);
		long start = System.currentTimeMillis();
		for (Iterator iterator = list.iterator(); iterator.hasNext();) {
			Comparable[] items = (Comparable[]) iterator.next();
			sort(items);
			//System.out.println("out" + Arrays.toString(items));
			
		}
		System.out.println("用时:" + (System.currentTimeMillis() - start) + "ms");
		start = System.currentTimeMillis();
		for (Iterator iterator = list.iterator(); iterator.hasNext();) {
			Comparable[] items = (Comparable[]) iterator.next();
			Arrays.sort(items);
			//System.out.println("out" + Arrays.toString(items));
			
		}
		System.out.println("用时:" + (System.currentTimeMillis() - start) + "ms");
		
	}
	

	public static void sort(Comparable[] items){
		mergeSortManager(items);
	}
}
class Item implements Comparable {
	private int data;
	public Item(int data) {
		this.data = data;
	}
	public Item() {
		// TODO Auto-generated constructor stub
	}
	@Override
	public int compareTo(Object o) {
		Item t = (Item)o;
		return this.data - t.getData();
	}
	public int getData() {
		return data;
	}
	public void setData(int data) {
		this.data = data;
	}
	
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return this.data + "";
	}
	
	
}
out put

用时:1219ms
用时:172ms




  


  
分享到:
评论

相关推荐

    MATLAB实现插入排序、二分归并排序、归并排序.rar

    在本资源中,我们主要关注的是使用MATLAB编程语言实现三种经典的排序算法:插入排序、二分归并排序以及归并排序。这些算法是计算机科学基础中的重要组成部分,特别是在算法设计与分析领域。MATLAB是一种强大的数值...

    归并排序C语言实现

    归并排序是一种高效的排序算法,基于分治策略。在C语言中实现归并排序,我们需要理解以下几个关键知识点: 1. **分治法**:归并排序的核心思想是将大问题分解为小问题来解决。首先将数组分为两半,分别对两半进行...

    三路归并_C语言_三路归并排序_三路归并_

    **三路归并排序**是一种高效的排序算法,尤其在处理含有大量重复元素的序列时表现优秀。该算法基于归并排序的思想,但将其分为三个部分处理,而不是传统的两个部分。在本文中,我们将深入探讨三路归并排序的原理、...

    归并排序算法实现

    ### 归并排序算法实现详解 #### 一、引言 归并排序是一种经典的排序算法,采用分治法的思想,将待排序数组分为若干个子序列,这些子序列是已排序的,然后再按照一定的方式合并这些子序列得到最终排序后的数组。...

    归并排序算法实现(排序算法系列1)

    归并排序是一种高效的、稳定的排序算法,由著名计算机科学家John W. Backus在1946年提出。它是基于分治策略的一种经典算法,适用于处理大量数据。在本系列的第一部分,我们将深入探讨归并排序的基本原理、实现过程...

    java实现归并排序

    Java实现归并排序 Java 实现归并排序是一种常用的排序算法,通过分治策略将原始数组分成小组,然后对每个小组进行排序,最后将排序好的小组合并成一个有序数组。下面是 Java 实现归并排序的知识点总结: 基本思想 ...

    直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码

    直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序和二路归并排序是计算机科学中经典的排序算法,它们在数据处理和算法学习中占有重要地位。这些排序算法各有特点,适用场景不同,下面将逐一详细介绍,并结合...

    归并排序 归并排序示例

    ### 归并排序详解 #### 一、归并排序简介 归并排序是一种采用分治策略的高效排序算法。其核心思想是将待排序数组分为若干子数组,这些子数组是已排序的,在合并这些子数组的过程中得到完全排序的数组。这种排序...

    二路归并排序

    二路归并排序 二路归并排序是指将两个有序表归并成一个有序表的过程。它是一种常用的排序算法,特别是在外部排序和数据库管理系统中。下面是对给定文件的知识点解释: 归并排序 归并排序是一种基于比较的排序算法...

    C语言二路归并排序算法

    ### C语言二路归并排序算法 #### 概述 归并排序是一种高效的排序算法,其基本思想是采用分治法(Divide and Conquer),将一个数组分成两个子数组,然后递归地对这两个子数组进行排序,最后将两个有序的子数组合并...

    归并排序,排序等算法,数据结构,快速排序,链表排序

    本主题将深入探讨四种常见的排序算法:归并排序、快速排序以及与链表相关的排序方法。 首先,我们来讨论归并排序(Merge Sort)。这是一种基于分治策略的排序算法。归并排序将大问题分解为小问题,然后逐步合并这些...

    归并排序(Merge sort)(台灣譯作:合併排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

    归并排序(Merge Sort)是一种基于分治策略的高效排序算法,由计算机科学家John W. Backus于1945年提出。它的工作原理可以分为三个主要步骤:分解、解决和合并。 1. 分解:将原始数据序列分成两个相等(或接近相等...

    数据结构堆排序 快速排序 归并排序

    本文将深入探讨三种常见的高效排序算法:堆排序、快速排序和归并排序。它们都是基于不同的原理和策略,具有各自的优势和适用场景。 首先,堆排序是一种基于比较的排序算法,利用了二叉堆的数据结构。二叉堆是一个...

    用单链表和队列实现归并排序

    归并排序是一种高效的排序算法,基于分治策略。在计算机科学中,分治法是一种将大问题分解为小问题来解决的方法。归并排序的基本思想是将待排序的数据分成两个或更多的子序列,分别对这些子序列进行排序,然后将排好...

    插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序

    以下是关于"插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序"这十大经典排序算法的详细解释: 1. 插入排序:插入排序是一种简单的排序算法,它通过构建有序...

    归并排序Java_归并排序_

    归并排序是一种高效的排序算法,基于分治策略。在Java中实现归并排序,我们可以创建一个名为`MergeSort`的类来封装整个过程。归并排序的基本思想是将待排序的序列分成两个或更多的子序列,对每个子序列分别进行排序...

    算法设计实验报告-快速排序和归并排序

    本实验旨在通过对两种经典排序算法——快速排序和归并排序的研究与实现,深入理解它们的基本原理、时间复杂度,并通过编程实践比较这两种算法在不同数据规模下的性能表现。 #### 二、快速排序 **1. 基本思想** ...

    归并排序、基数排序算法比较

    试通过随机数据比较归并排序、基数排序各算法的关键字比较次数和关键字移动次数。 (1)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有。关键字...

    归并排序插入排序C++代码

    归并排序和插入排序是两种常见的排序算法,它们在计算机科学和编程领域有着广泛的应用。归并排序是一种基于分治思想的排序算法,而插入排序则是一种简单直观的排序算法,适用于小规模或部分有序的数据。 **归并排序...

    C++实现希尔、快速、堆排序、归并排序算法

    本文将详细介绍C++中实现的希尔排序、快速排序、堆排序和归并排序这四种经典排序算法。 希尔排序,由Donald Shell于1959年提出,是一种改进的插入排序。它的基本思想是通过设置一个增量序列,将待排序的元素按照...

Global site tag (gtag.js) - Google Analytics