又花了点时间看看算法,这次看的是归并。
感觉归并的效率比插入排序高多了!
代码给上
package oliver.algorithm.sort; public class MergeSort { public static void sort(int[] arr,int first,int last) { int mid=0; if(first<last) { mid=(first+last)/2; sort(arr,first,mid); sort(arr,mid+1,last); merge(arr,first,mid,last); } } private static void merge(int [] arr,int p,int q,int r) { int begin1,end1,begin2,end2; begin1=p;end1=q; begin2=q+1;end2=r; int []temp=new int[r-p+1]; int i=0; while((begin1<=end1)&&(begin2<=end2)) { if(arr[begin1]<arr[begin2]) { temp[i]=arr[begin1]; begin1++; } else { temp[i]=arr[begin2]; begin2++; } i++; } while(begin1<=end1) { temp[i++]=arr[begin1++]; } while(begin2<=end2) { temp[i++]=arr[begin2++]; } for(i=0;i<=(r-p);i++) { arr[p+i]=temp[i]; } } }
测试代码
package oliver.algorithm.sort; import java.util.Date; public class MergeSortTest { /** * @param args */ public static void main(String[] args) { int size=100000; int [] arr=new int[size]; for(int i=0;i<size;i++) { arr[i]=size-i; } Long beginTime=new Date().getTime(); MergeSort.sort(arr,0,size-1); Long endTime=new Date().getTime(); for(int a:arr) { System.out.print(a+" "); } System.out.println(); System.out.println("when n = "+size+" toke "+(endTime-beginTime)+"ms"); } }
相关推荐
本主题将深入探讨四种常见的排序算法:归并排序、快速排序以及与链表相关的排序方法。 首先,我们来讨论归并排序(Merge Sort)。这是一种基于分治策略的排序算法。归并排序将大问题分解为小问题,然后逐步合并这些...
归并排序是一种基于**分而治之**策略的经典排序算法。它将一个数组分成两半,递归地对每一半进行排序,然后将排序后的两部分合并成一个有序数组。 #### 二、归并排序的基本步骤 归并排序主要由两个关键步骤组成: ...
本文将对快速排序、归并排序、堆排序等常见排序算法进行比较和分析,探讨它们的优缺点和适用场景。 首先, let's 看一下这些排序算法的时间复杂度和空间复杂度: | 排序算法 | 平均情况 | 最好情况 | 最坏情况 | ...
十个基础排序算法:冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、桶排序、计数排_SortAlgorithm
java实现10种排序算法:选择排序、冒泡排序、插入排序、快速排序、归并排序、堆排序、希尔排序、桶排_sorting-algorithms
这里我们将深入探讨两种常见的排序算法:归并排序(Merge Sort)和快速排序(Quick Sort)。这两种都是基于分治策略的高效排序算法。 **归并排序**: 归并排序是一种稳定的排序算法,它通过将数据分成较小的部分,...
在本资源中,我们主要关注的是使用MATLAB编程语言实现三种经典的排序算法:插入排序、二分归并排序以及归并排序。这些算法是计算机科学基础中的重要组成部分,特别是在算法设计与分析领域。MATLAB是一种强大的数值...
### C++排序算法之归并排序源码解析 #### 归并排序简介 归并排序是一种高效的、基于分治策略的排序算法。它利用了分而治之的思想,通过递归地将数组分成越来越小的部分,然后将这些部分重新合并为更大的、已排序的...
归并排序是一种高效的、稳定的排序算法,由著名计算机科学家John W. Backus在1946年提出。它是基于分治策略的一种经典算法,适用于处理大量数据。在本系列的第一部分,我们将深入探讨归并排序的基本原理、实现过程...
本文将深入探讨Java编程语言中实现的七种主要排序算法:直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序以及归并排序。每种算法都有其独特性,适用于不同的场景和数据特性。 1. **直接插入排序**:...
**归并排序是一种高效、稳定的排序算法,基于“分治”策略。它的基本思想是将大问题分解成小问题来解决。在归并排序中,我们首先将原始数组分割成两个或更多的子数组,对每个子数组进行排序,然后将排好序的子数组合...
归并排序是一种高效的排序算法,基于分治策略。在C语言中实现归并排序,我们需要理解以下几个关键知识点: 1. **分治法**:归并排序的核心思想是将大问题分解为小问题来解决。首先将数组分为两半,分别对两半进行...
例如,插入排序和选择排序适合小规模数据,冒泡排序简单但效率低,希尔排序对大规模数据有优势,归并排序稳定但需要额外空间,快速排序在大多数情况下高效。在编程实践中,根据具体需求选择合适的排序算法是非常重要...
1. 自底向上归并排序:为了避免递归带来的开销,可以采用自底向上的方法,从长度为1的子序列开始,逐步合并成更大的有序序列。 2. 插入排序优化:对于小规模的子序列,可以考虑使用插入排序,因为插入排序在小规模...
归并排序(Merge Sort)是一种基于分治策略的高效排序算法,由计算机科学家John W. Backus于1945年提出。它的工作原理可以分为三个主要步骤:分解、解决和合并。 1. 分解:将原始数据序列分成两个相等(或接近相等...
本实验旨在通过对两种经典排序算法——快速排序和归并排序的研究与实现,深入理解它们的基本原理、时间复杂度,并通过编程实践比较这两种算法在不同数据规模下的性能表现。 #### 二、快速排序 **1. 基本思想** ...
这七种算法分别是:冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序和快速排序。 1. **冒泡排序**: 冒泡排序是最基础的排序算法之一,通过重复遍历待排序序列,比较相邻元素并交换位置来实现排序...
归并排序:如何使用Java实现归并排序算法,程序详细解读; 归并排序:如何使用Java实现归并排序算法,程序详细解读; 归并排序:如何使用Java实现归并排序算法,程序详细解读; 归并排序:如何使用Java实现归并排序...
常见算法八种常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序、快速排序、归并排序、堆排序和LS_calgorithms
归并排序和插入排序是两种常见的排序算法,它们在计算机科学和编程领域有着广泛的应用。归并排序是一种基于分治思想的排序算法,而插入排序则是一种简单直观的排序算法,适用于小规模或部分有序的数据。 **归并排序...