Java 归并排序算法、堆排序算法实例详解

基本思想:

  归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序示例:

合并方法:

设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成,两个子表长度分别为n-i +1、n-m。

j=m+1;k=i;i=i; //置两个子表的起始下标及辅助数组的起始下标

若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束
//选取r[i]和r[j]较小的存入辅助数组rf

如果r[i]<r[j],rf[k]=r[i]; i++; k++; 转⑵

否则,rf[k]=r[j]; j++; k++; 转⑵

//将尚未处理完的子表中元素存入rf

如果i<=m,将r[i…m]存入rf[k…n] //前一子表非空

如果j<=n ,  将r[j…n] 存入rf[k…n] //后一子表非空

合并结束。

算法实现:  

/**
   * 归并排序
   * 简介:将两个(或两个以上)有序表合并成一个新的有序表 即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列
   * 时间复杂度为O(nlogn)
   * 稳定排序方式
   * @param nums 待排序数组
   * @return 输出有序数组
   */
  public static int[] sort(int[] nums, int low, int high) {
    int mid = (low + high) / 2;
    if (low < high) {
      // 左边
      sort(nums, low, mid);
      // 右边
      sort(nums, mid + 1, high);
      // 左右归并
      merge(nums, low, mid, high);
    }
    return nums;
  }
  /**
   * 将数组中low到high位置的数进行排序
   * @param nums 待排序数组
   * @param low 待排的开始位置
   * @param mid 待排中间位置
   * @param high 待排结束位置
   */
  public static void merge(int[] nums, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low;// 左指针
    int j = mid + 1;// 右指针
    int k = 0;
    // 把较小的数先移到新数组中
    while (i <= mid && j <= high) {
      if (nums[i] < nums[j]) {
        temp[k++] = nums[i++];
      } else {
        temp[k++] = nums[j++];
      }
    }
    // 把左边剩余的数移入数组
    while (i <= mid) {
      temp[k++] = nums[i++];
    }
    // 把右边边剩余的数移入数组
    while (j <= high) {
      temp[k++] = nums[j++];
    }
    // 把新数组中的数覆盖nums数组
    for (int k2 = 0; k2 < temp.length; k2++) {
      nums[k2 + low] = temp[k2];
    }
  }

二、堆排序算法

1、基本思想:

  堆排序是一种树形选择排序,是对直接选择排序的有效改进。

  堆的定义下:具有n个元素的序列 (h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1) (i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项(大顶堆)。完全二 叉树可以很直观地表示堆的结构。堆顶为根,其它为左子树、右子树。

  思想:初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储序,使之成为一个 堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推,直到只有两个节点的堆,并对 它们作交换,最后得到有n个节点的有序序列。从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函 数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

2、实例

初始序列:46,79,56,38,40,84

  建堆:

  交换,从堆中踢出最大数

依次类推:最后堆中剩余的最后两个结点交换,踢出一个,排序完成。

3.算法实现:

public class HeapSort {
  public static void main(String[] args) {
    int[] a={49,38,65,97,76,13,27,49,78,34,12,64};
    int arrayLength=a.length;
    //循环建堆
    for(int i=0;i<arrayLength-1;i++){
      //建堆
      buildMaxHeap(a,arrayLength-1-i);
      //交换堆顶和最后一个元素
      swap(a,0,arrayLength-1-i);
      System.out.println(Arrays.toString(a));
    }
  }
  //对data数组从0到lastIndex建大顶堆
  public static void buildMaxHeap(int[] data, int lastIndex){
     //从lastIndex处节点(最后一个节点)的父节点开始
    for(int i=(lastIndex-1)/2;i>=0;i--){
      //k保存正在判断的节点
      int k=i;
      //如果当前k节点的子节点存在
      while(k*2+1<=lastIndex){
        //k节点的左子节点的索引
        int biggerIndex=2*k+1;
        //如果biggerIndex小于lastIndex,即biggerIndex+1代表的k节点的右子节点存在
        if(biggerIndex<lastIndex){
          //若果右子节点的值较大
          if(data[biggerIndex]<data[biggerIndex+1]){
            //biggerIndex总是记录较大子节点的索引
            biggerIndex++;
          }
        }
        //如果k节点的值小于其较大的子节点的值
        if(data[k]<data[biggerIndex]){
          //交换他们
          swap(data,k,biggerIndex);
          //将biggerIndex赋予k,开始while循环的下一次循环,重新保证k节点的值大于其左右子节点的值
          k=biggerIndex;
        }else{
          break;
        }
      }
    }
  }
  //交换
  private static void swap(int[] data, int i, int j) {
    int tmp=data[i];
    data[i]=data[j];
    data[j]=tmp;
  }
}

以上所述是小编给大家介绍的Java 归并排序算法、堆排序算法实例详解,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持!

时间: 2017-05-03

Java堆排序算法详解

堆是数据结构中的一种重要结构,了解"堆"的概念和操作,可以帮助我们快速地掌握堆排序. 堆的概念 堆是一种特殊的完全二叉树(complete binary tree).如果一棵完全二叉树的所有节点的值都不小于其子节点,称之为大根堆(或大顶堆):所有节点的值都不大于其子节点,称之为小根堆(或小顶堆). 在数组(在0号下标存储根节点)中,容易得到下面的式子(这两个式子很重要): 1.下标为i的节点,父节点坐标为(i-1)/2: 2.下标为i的节点,左子节点坐标为2*i+1,右子节点为2*i+

Java各种排序算法汇总(冒泡,选择,归并,希尔及堆排序等)

本文实例汇总了Java各种排序算法.分享给大家供大家参考,具体如下: 1. 冒泡排序: public class SortTest { public static void main(String[] args) { int[] a = {345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,444,345}; show(a); bubbleSort(a); show(a); } private static void bubbleSo

Java实现堆排序(Heapsort)实例代码

复制代码 代码如下: import java.util.Arrays; public class HeapSort { public static void heapSort(DataWraper[] data){        System.out.println("开始排序");        int arrayLength=data.length;        //循环建堆        for(int i=0;i<arrayLength-1;i++){         

JAVA算法起步之堆排序实例

学习堆排序,首先需要明白堆的概念,堆是一个数组.可以近似当做完全二叉树的数组存储方式.但是跟他还有其他的性质,就是类似于二叉排序树.有最大堆跟最小堆之分,最大堆是指根节点的值都大于子节点的值,而最小堆的是根节点的值小于其子节点的值.堆排序一般用的是最大堆,而最小堆可以构造优先队列.堆里面有一个方法是用来维护堆的性质,也就是我们下面代码中的maxheap方法,这是维护最大堆性质的方法,第一个参数就是堆也就是数组,第二个参数是调整堆的具体节点位置,可能这个节点的值不符合最大堆的性质,那么这个值得位置

Java排序算法总结之堆排序

本文实例讲述了Java排序算法总结之堆排序.分享给大家供大家参考.具体分析如下: 1991年计算机先驱奖获得者.斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W.Floyd)和威廉姆斯(J.Williams)在1964年共同发明了著名的堆排序算法( Heap Sort ).本文主要介绍堆排序用Java来实现. 堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素.堆排序是不稳定的排序方法,辅助空间为O(1), 最坏

堆排序算法的讲解及Java版实现

堆是数据结构中的一种重要结构,了解了"堆"的概念和操作,可以快速掌握堆排序. 堆的概念 堆是一种特殊的完全二叉树(complete binary tree).如果一棵完全二叉树的所有节点的值都不小于其子节点,称之为大根堆(或大顶堆):所有节点的值都不大于其子节点,称之为小根堆(或小顶堆). 在数组(在0号下标存储根节点)中,容易得到下面的式子(这两个式子很重要): 1.下标为i的节点,父节点坐标为(i-1)/2: 2.下标为i的节点,左子节点坐标为2*i+1,右子节点为2*i+2. 堆

深入解析堆排序的算法思想及Java代码的实现演示

一.基础知识 我们通常所说的堆是指二叉堆,二叉堆又称完全二叉树或者叫近似完全二叉树.二叉堆又分为最大堆和最小堆. 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法,它是选择排序的一种.可以利用数组的特点快速定位指定索引的元素.数组可以根据索引直接获取元素,时间复杂度为O(1),也就是常量,因此对于取值效率极高. 最大堆的特性如下: 父结点的键值总是大于或者等于任何一个子节点的键值 每个结点的左子树和右子树都是一个最大堆 最小堆的特性如下: 父结点的键值总是小于或者等于任何一个

java堆排序原理及算法实现

从堆排序的简介到堆排序的算法实现等如下: 1. 简介 堆排序是建立在堆这种数据结构基础上的选择排序,是原址排序,时间复杂度O(nlogn),堆排序并不是一种稳定的排序方式.堆排序中通常使用的堆为最大堆. 2. 堆的定义 堆是一种数据结构,是一颗特殊的完全二叉树,通常分为最大堆和最小堆.最大堆的定义为根结点最大,且根结点左右子树都是最大堆:同样,最小堆的定义为根结点最小,且根结点左右子树均为最小堆. 最大堆满足其每一个父结点均大于其左右子结点,最小堆则满足其每一个父结点均小于其左右子结点. 3.

详解堆排序算法原理及Java版的代码实现

概述 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(k1,k2,...,kn), 当且仅当满足: 时称之为堆.由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)或最大项(大顶堆). 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点(有子女的结点)的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的. (a)大顶堆序列:(96, 83, 27, 38, 11, 09) (b)小顶堆序列:(12, 36,

java 数据结构之堆排序(HeapSort)详解及实例

1 堆排序 堆是一种重要的数据结构,分为大根堆和小根堆,是完全二叉树, 底层如果用数组存储数据的话,假设某个元素为序号为i(Java数组从0开始,i为0到n-1),如果它有左子树,那么左子树的位置是2i+1,如果有右子树,右子树的位置是2i+2,如果有父节点,父节点的位置是(n-1)/2取整.最大堆的任意子树根节点不小于任意子结点,最小堆的根节点不大于任意子结点. 所谓堆排序就是利用堆这种数据结构的性质来对数组进行排序,在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的性质可知,最大的

JAVA线程sleep()和wait()详解及实例

JAVA线程sleep()和wait()详解及实例 sleep 1.sleep是Thread的一个静态(static)方法.使得Runnable实现的线程也可以使用sleep方法.而且避免了线程之前相互调用sleep()方法,引发死锁. 2.sleep()执行时需要赋予一个沉睡时间.在沉睡期间(阻塞线程期间),CPU会放弃这个线程,执行其他任务.当沉睡时间到了之后,该线程会自动苏醒,不过此时线程不会立刻被执行,而是要等CPU分配资源,和其他线程进行竞争. 3.此外如果这个线程之前获取了一个机锁,

java 中 阻塞队列BlockingQueue详解及实例

java 中 阻塞队列BlockingQueue详解及实例 BlockingQueue很好的解决了多线程中数据的传输,首先BlockingQueue是一个接口,它大致有四个实现类,这是一个很特殊的队列,如果BlockQueue是空的,从BlockingQueue取东西的操作将会被阻断进入等待状态,直到BlockingQueue进了东西才会被唤醒.同样,如果BlockingQueue是满的,任何试图往里存东西的操作也会被阻断进入等待状态,直到BlockingQueue里有空间才会被唤醒继续操作.

Java 8 lambda表达式引入详解及实例

Java 8 lambda表达式引入详解及实例 eclipse 下载安装 Help -> EclipseMarketplace -> 搜索Java 8 Kepler ->Java 8 support for eclipse Kepler SR2 安装完成后需要重启 Android Studio 在project的build.gradle文件中添加 buildscript { dependencies { classpath 'me.tatarka:gradle-retrolambda:3

Java中对象的序列化详解及实例

 Java中对象的序列化详解及实例 把java对象转化为字节序列的过程称为对象的序列化. 把字节序列恢复为java对象的过程称为对象的反序列化. 对象序列化的用途: 1.把对象的字节序列永久的保存到硬盘上,通常存放在一个文件中 2.在网络上传送对象的字节序列化 void writeObject(Object obj) 方法可对参数指定的obj对象进行序列化,把得到的字节序列写到一个目标输出流中(将指定的对象写入 ObjectOutputStream.) void readObject()方法 从

java LRU(Least Recently Used )详解及实例代码

java LRU(Least Recently Used )详解 LRU是Least Recently Used 的缩写,翻译过来就是"最近最少使用",LRU缓存就是使用这种原理实现,简单的说就是缓存一定量的数据,当超过设定的阈值时就把一些过期的数据删除掉,比如我们缓存10000条数据,当数据小于10000时可以随意添加,当超过10000时就需要把新的数据添加进来,同时要把过期数据删除,以确保我们最大缓存10000条,那怎么确定删除哪条过期数据呢,采用LRU算法实现的话就是将最老的数据

java 实现单链表逆转详解及实例代码

java 实现单链表逆转详解 实例代码: class Node { Node next; String name; public Node(String name) { this.name = name; } /** * 打印结点 */ public void show() { Node temp = this; do { System.out.print(temp + "->"); temp = temp.next; }while(temp != null); System.o

Java 装箱与拆箱详解及实例代码

Java 装箱与拆箱详解 前言: 要理解装箱和拆箱的概念,就要理解Java数据类型 装箱:把基本类型用它们相应的引用类型包装起来,使其具有对象的性质.int包装成Integer.float包装成Float 拆箱:和装箱相反,将引用类型的对象简化成值类型的数据 Integer a = 100; 这是自动装箱 (编译器调用的是static Integer valueOf(int i)) int b = new Integer(100); 这是自动拆箱 看下面一段代码 m1 public class

Java 使用json-lib处理JSON详解及实例代码

Java 使用json-lib处理JSON详解 [项目环境] <dependency> <groupId>net.sf.json-lib</groupId> <artifactId>json-lib</artifactId> <version>2.4</version> <classifier>jdk15</classifier> </dependency> 1. JSON 数组对象转化

Java中的Static class详解及实例代码

 Java中的Static class详解 Java中的类可以是static吗?答案是可以.在Java中我们可以有静态实例变量.静态方法.静态块.类也可以是静态的. java允许我们在一个类里面定义静态类.比如内部类(nested class).把nested class封闭起来的类叫外部类.在java中,我们不能用static修饰顶级类(top level class).只有内部类可以为static. 静态内部类和非静态内部类之间到底有什么不同呢?下面是两者间主要的不同. (1)内部静态类不需

C++/java 继承类的多态详解及实例代码

C++/java 继承类的多态详解 学过C++和Java的人都知道,他们二者由于都可以进行面向对象编程,而面向对象编程的三大特性就是封装.继承.多态,所有今天我们就来简单了解一下C++和Java在多态这方面的不同. 首先我们各看一个案例. C++ //测试继承与多态 class Animal { public: char name[128]; char behavior[128]; void outPut() { cout << "Animal" << endl