Java实现归并排序

简介: Java实现归并排序

归并是将两个或多个存序记录序列合并成一个有序序列。归并方法有多种,一次对两个有序记录序列进行归并,称为路归并排序,也有三路归并排序及多路归并排序。本实例是二路归并排序,基本方法如下:

(1) 将 n 个记录看成是 n 个长度为 1 的有序子表。

(2) 将两两相邻时有序无表进行归并。

(3) 重复执行步骤 (2) 直到归并成一个长度为 n 的有序表。

源码

package com;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
  public static void main(String[] args) {
    Scanner s=new Scanner (System.in);
    int n=s.nextInt();
    int [] a=new int [n];
    int [] temp=new int [n];
    for(int i=0;i<n;i++)
      a[i]=(int)(Math.random()*100);
    mergesort(a,0,a.length-1,temp);
    System.out.println(Arrays.toString(a));
  }
  public static void mergesort (int[] a,int left,int right,int[] temp) {
    if(left<right) {
      int mid=(left+right)/2;
      mergesort(a,left,mid,temp);
      mergesort(a,mid+1,right,temp);
      merge(a,left,mid,right,temp);
    }
  } 
  public static void merge(int[] a,int left,int mid,int right,int[] temp) {
    int i=left;
    int j=mid+1;
    int t=0;
    while(i<=mid&&j<=right) {
      if(a[i]<=a[j]) {
        temp[t]=a[i];
        t++;
        i++;
      }else {
        temp[t]=a[j];
        t++;
        j++;
      }
    }
    while(i<=mid) {
      temp[t]=a[i];
      t++;
      i++;
    }
    while(j<=right) {
      temp[t]=a[j];
      t++;
      j++;
    }
    t=0;
    int templeft=left;
    while(templeft<=right) {
      a[templeft]=temp[t];
      t++;
      templeft++;
    }
  }
}

以上代码仅供参考


目录
相关文章
|
10月前
|
Java
java实现归并排序
java实现归并排序
65 0
|
10月前
|
存储 搜索推荐 算法
Java代码归并排序
Java代码归并排序
44 0
|
7月前
|
搜索推荐 Java
|
7月前
|
数据采集 搜索推荐 算法
【高手进阶】Java排序算法:从零到精通——揭秘冒泡、快速、归并排序的原理与实战应用,让你的代码效率飙升!
【8月更文挑战第21天】Java排序算法是编程基础的重要部分,在算法设计与分析及实际开发中不可或缺。本文介绍内部排序算法,包括简单的冒泡排序及其逐步优化至高效的快速排序和稳定的归并排序,并提供了每种算法的Java实现示例。此外,还探讨了排序算法在电子商务、搜索引擎和数据分析等领域的广泛应用,帮助读者更好地理解和应用这些算法。
70 0
|
9月前
|
Java
归并排序(java)
归并排序(java)
|
9月前
|
搜索推荐 算法 Java
Java中的快速排序、归并排序和堆排序是常见的排序算法。
【6月更文挑战第21天】Java中的快速排序、归并排序和堆排序是常见的排序算法。快速排序采用分治,以基准元素划分数组并递归排序;归并排序同样分治,先分割再合并有序子数组;堆排序通过构建堆来排序,保持堆性质并交换堆顶元素。每种算法各有优劣:快排平均高效,最坏O(n²);归并稳定O(n log n)但需额外空间;堆排序O(n log n)且原地排序,但不稳定。
68 3
|
10月前
|
算法 Java
<八大排序>万字详解(Java实现).插入排序、希尔排序、堆排序、快速排序、归并排序、计数排序...
<八大排序>万字详解(Java实现).插入排序、希尔排序、堆排序、快速排序、归并排序、计数排序
41 0
|
算法 Java
java实现归并排序
java实现归并排序
83 0
|
10月前
|
机器学习/深度学习 算法 搜索推荐
数据结构与算法(Java篇)笔记--归并排序
数据结构与算法(Java篇)笔记--归并排序
|
10月前
|
Java
使用Java实现合并两个数组[归并排序]
使用Java实现合并两个数组[归并排序]

热门文章

最新文章