文档章节

经典排序算法(Java实现)

whc20011
 whc20011
发布于 2016/02/02 14:37
字数 2261
阅读 25
收藏 0
点赞 1
评论 0

以下程序均将数据封装于DataWrap数据包装类中,如下所示:

class DataWrap implements Comparable<DataWrap>
      {
         int data;
         String flag;
         public DataWrap(int data,String flag)
         {
             this.data = data;
             this.flag = flag;
         }
         //重写compareTo方法
         public int compareTo(DataWrap other)
         {
             return this.data > other.data ? 1 : (this.data == other.data ? 0 : -1);
         }
         public String toString()
         {
             return this.data + this.flag;
         }
     }

 

一、选择排序

1、直接选择排序

  数组分成有序区和无序区,初始时整个数组都是无序区,然后每次从无序区选一个最小的元素直接放到有序区的最后,直到整个数组变有序区。

1 public static void directSelectSort(DataWrap[] dw)
 2     {
 3         int n = dw.length;
 4         for(int i = 0;i < n-1;i++)
 5         {
 6             int minIndex = i;  
 7             for(int j = i+1;j < n;j++)
 8             {
 9                 if(dw[minIndex].compareTo(dw[j]) > 0)
10                 {
11                     minIndex = j;  //minIndex为每趟比较重最小数的索引
12                 }
13             }
14             swap(dw,minIndex,i);
15             System.out.println("直接选择排序中的元素:" + Arrays.toString(dw));
16         }
17         
18     }

2、堆排序

  1)二叉堆

    二叉堆是完全二叉树或者是近似完全二叉树。

    父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。

    每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。

      当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。

  2)堆的存储

    一般都用数组来表示堆,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。

  3)堆排序原理(以最小堆为例)

    堆排序是先建立一个最小堆,然后第一次将A[0]与A[n - 1]交换,再对A[0…n-2]重新恢复最小堆。第二次将A[0]与A[n – 2]交换,再对A[0,…,n - 3]重新恢复最小堆,重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间,故操作完成后整个数组就有序(为降序)了。

建立最小堆就是先从最后一个非叶子节点(即n/2-1节点)开始,节点依次往前就行,直到第二个节点。对于每个节点,先比较其左右节点选出较小的节点,然后将较小的节点与父节点进行比较。如果父节点比最小的子节点还小的话则不需要调整,否则的话将较小的子节点作为新的父节点,将原先的父节点与其子节点的子节点中较小的进行比较,直到该父节点找到能够插入的位置或者是到达堆的结束。

  4)代码实现

1 public class HeapSort 
 2 {
 3     /**
 4      * 从某一节点向下调整大小  
 5      * @param dw 待排序数据包
 6      * @param i     开始向下调整的堆索引
 7      * @param n  所调整堆数据的大小
 8      */
 9     public static void MinHeapFixDown(DataWrap[] dw,int i,int n)
10     {
11         int j;
12         DataWrap temp;
13         j = 2 * i +1;
14         temp = dw[i];
15         while(j < n)
16         {
17             if(j+1 < n && dw[j+1].compareTo(dw[j]) < 0)
18             { //找出左右子节点中较小的
19                 j++;
20             }
21             if(temp.compareTo(dw[j]) <= 0)
22             {  //将父节点与子节点进行比较
23                 break;
24             }
25             dw[i] = dw[j];  //将较小的子节点上移
26             i = j;
27             j = 2 * i +1;
28         }
29         dw[i] = temp; 
30     }
31     //构建最小堆并进行堆排序
32     public static void heapSort(DataWrap[] dw)
33     {
34         int n = dw.length;
35         //构建最小堆
36         for(int i = n/2-1;i >= 0;i--)
37         {
38             HeapSort.MinHeapFixDown(dw, i, n);
39         }
40         //堆排序
41         for(int i = n-1;i >=1;i--)
42         {  
43             swap(dw,0,i);   //每次将第n-1,n-2,...1个元素与dw[0]交换后,将最后一个元素从堆中排除
44             MinHeapFixDown(dw, 0, i); //将每次交换后-1的堆从dw[0]开始,调整为新的最小堆
45         }
46     }
47     
48     //交换DataWrap数组中i,j两数值
49     public static void swap(DataWrap[] dw,int i,int j)
50     {
51         DataWrap temp;
52         temp = dw[i];
53         dw[i] = dw[j];
54         dw[j] = temp;
55     } 
56     
57     public static void main(String[] args)
58     {
59         DataWrap[] dw = {new DataWrap(25,""),new DataWrap(42,""),new DataWrap(36,""),new DataWrap(8,""),new DataWrap(78,""),new DataWrap(99,"")};
60         System.out.println("待排序数据为:" + Arrays.toString(dw));
61         HeapSort.heapSort(dw);
62         System.out.println("排序后数据为:" + Arrays.toString(dw));        
63     }
64 }

二、交换排序

1、冒泡排序

  1.比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交换。

  2.这样对数组的第0个数据到N-1个数据进行一次遍历后,最大的一个数据就“沉”到数组第N-1个位置。

  3.N=N-1,如果N不为0就重复前面二步,否则排序完成。

1 public static void bubbleSort(DataWrap[] dw)
 2     {
 3         int n = dw.length;
 4         boolean flag;//设置标志位,若发生未交换的情况,说明已经有序,退出循环即可
 5         for(int i = n-1;i > 0 ;i--)
 6         {
 7             flag = false;
 8             for(int j = 0;j < i;j++)
 9             {
10                 if(dw[j].compareTo(dw[j+1]) > 0)
11                 {
12                     swap(dw,j+1,j);
13                     flag = true;
14                 }
15             }
16             if(!flag)
17             {
18                 break;
19             }
20             System.out.println("排序中顺序:" + Arrays.toString(dw));
21         }
22     }

2、快速排序

  快速选择排序主要思路是:

  “挖坑填数+分治法”,首先令i =L; j = R; 将a[i]挖出形成第一个坑,称a[i]为基准数。然后j--由后向前找比基准数小的数,找到后挖出此数填入前一个坑a[i]中,再i++由前

向后找比基准数大的数,找到后也挖出此数填到前一个坑a[j]中。重复进行这种“挖坑填数”直到i==j。再将基准数填入a[i]中,这样i之前的数都比基准数小,i之后的数都比基准数

大。因此将数组分成二部分再分别重复上述步骤就完成了排序。

public class QuickSort {

  static int partition(int[] data, int left, int high) {
    int midData = data[left];
    while (left < high) {
      while (left < high && midData < data[high])
        high--;
      data[left] = data[high];
      while (left < high && midData >= data[left])
        left++;
      data[high] = data[left];
    }
    data[left] = midData;
    return left;
  }

  /**
   * 快速排序
   * 
   * @param data
   * @param left
   * @param high
   */
  static void quick_sort(int[] data, int left, int high) {
    int loc = 0;
    if (left < high) {
      loc = partition(data, left, high);
      quick_sort(data, left, loc - 1);
      quick_sort(data, loc + 1, high);
    }
  }

  public static void main(String[] args) {
    int[] data = {6, 2, 4, 8, 5, 9};
    quick_sort(data, 0, data.length - 1);
    System.out.print("排序后数据为:" + Arrays.toString(data));
  }



}

三、插入排序

1、直接插入排序

  每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。

public static void directInsertSort(DataWrap[] dw,int n)
 2     {
 3         for(int i = 1;i < n;i++)
 4         {
 5             if(dw[i].compareTo(dw[i-1]) < 0)
 6             {
 7                 DataWrap temp = dw[i];
 8                 int j;
 9                 for(j = i-1;j >= 0 && dw[j].compareTo(temp) > 0;j--)
10                 {
11                     dw[j+1] = dw[j];
12                 }
13                 dw[j+1] = temp;
14             }
15         }
16     }

2、希尔排序(Shell排序、缩小增量排序)

  ‍先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。由于希尔排序是对相隔若干距离的数据进行直接插入排序,因此可以形象的称希尔排序为“跳着插”‍

public static void directInsertSort(DataWrap[] dw,int n)
 2     {
 3         for(int i = 1;i < n;i++)
 4         {
 5             if(dw[i].compareTo(dw[i-1]) < 0)
 6             {
 7                 DataWrap temp = dw[i];
 8                 int j;
 9                 for(j = i-1;j >= 0 && dw[j].compareTo(temp) > 0;j--)
10                 {
11                     dw[j+1] = dw[j];
12                 }
13                 dw[j+1] = temp;
14             }
15         }
16     }

四、归并排序

  当一个数组左边和右边都有序时,将两边合并就完成了排序,而要使两边都有序,则需要用递归。先递归下去,再合并上来,就是归并排序。

1 public class MergeSort
 2 {
 3     
 4     public static void mergeSort(int[] data)
 5     {
 6         int n = data.length;
 7         sort(data, 0, n-1);//归并排序
 8     }
 9     
10     public static void sort(int[] data,int left,int right)
11     {
12         if(left <right)
13         {
14             int center = (left + right)/2;//中间索引
15             sort(data, left, center);//堆左边数组进行递归
16             sort(data, center+1, right);//堆右边数组进行递归
17             merge(data, left, center, right);//合并
18         }
19     }
20     
21     public static void merge(int[] data,int left,int center,int right)
22     {
23         int[] array = new int[data.length];//定义临时数组
24         int mid = center+1;
25         int k = left;//临时数组索引
26         int temp = left;
27         while(left <= center && mid <= right)
28         {
29             if(data[left] < data[mid])
30                 array[k++] = data[left++];
31             else
32                 array[k++] = data[mid++];
33         }
34         while(left <= center)
35             array[k++] = data[left++];
36         while(mid <= right)
37             array[k++] = data[mid++];
38         while(temp <= right)
39             data[temp] = array[temp++];
40     }
41     
42     public static void main(String[] args)
43     {
44         int[] data = {2,27,56,8,24,12,99,0,56};
45         MergeSort.mergeSort(data);
46         for(int i:data)
47         {
48             System.out.print(i + ",");
49         }
50     }
51 }

 

 

 

© 著作权归作者所有

共有 人打赏支持
whc20011
粉丝 0
博文 48
码字总数 29707
作品 0
朝阳
程序员
Java程序员必读书单,家族又添新成员

点击关注异步图书,置顶公众号 每天与你分享IT好书 技术干货 职场知识 参与文末话题讨论,每日赠送异步图书。 ——异步小编 有些革命出其不意地吸引了全世界的眼球。Twitter、Linux操作系统和...

异步社区 ⋅ 05/09 ⋅ 0

阿里一面 京东一面+二面 | 掘金技术征文

阿里一面 简单说说在学校做过最有成就感的事情(和技术相关的) 你的项目用到了数据库,谈谈对事务的理解 假设你要做一个银行app,有可能碰到多个人同时向一个账户打钱的情况,有可能碰到什么...

京东一面 ⋅ 04/18 ⋅ 0

JDK 11 特性抢先看:5 月新增三个 JEP

一周前(2018年5月7日),JDK11 新增了三个 JEP 。在 jdk-dev 邮件列表中出现了三封邮件,Mark Reinhold 发表了以下公告: JDK 11 实现了 JEP:324:关于 Curve25519 和 Curve448 的重要协议...

oschina ⋅ 05/16 ⋅ 0

通过 HttpAuthenticationMechanism 执行 Web 身份验证

通过 Java EE 8 中新的注解驱动的 HTTP 身份验证机制执行经典和自定义的 Servlet 身份验证 系列内容: 此内容是该系列 4 部分中的第 # 部分: Java EE 8 Security API 入门,第 2 部分 http...

Alex Theedom ⋅ 04/02 ⋅ 0

java中的全局变量如何实现?ThreadLocal~

全局变量就是不管你在哪里,都能够直接引用的变量,还不用担心各种问题。每个语言都有自己的全局变量,我想!   一般地,面向过程的语言当中,可能就是一个声明在最前面的变量,后面的代码...

美的让人心动 ⋅ 05/09 ⋅ 0

Java面试需要准备哪些多线程并发的技术要点

一、概念 什么是线程 一个线程要执行任务,必须得有线程 一个进程(程序)的所有任务都在线程中执行的 一个线程执行任务是串行的,也就是说一个线程,同一时间内,只能执行一个任务 多线程原理 同一...

码蚁说架构 ⋅ 05/31 ⋅ 0

Java语言标准(第10版)第一章(节选)翻译与评注

英文原文链接:https://docs.oracle.com/javase/specs/jls/se10/html/jls-1.html 评注是括在鱼尾号之间的文字,其余均为翻译 Java编程语言是一种通用目的的【有别于VBA、Matlab这些专用型语言...

Jelif ⋅ 06/02 ⋅ 0

IntelliJ IDEA 2018.1.3 + jdk1.8 安装教程

1.写在前面 由于同学的项目缺人手,欲拉我参与其中,该项目由java编写,所以开始了我的java学习。当然首先是安装java环境啦。 2.安装IDEA 由于这个是收费的,我等穷逼哪搞得起。只能破解使用...

我只是一只小小鸟 ⋅ 05/21 ⋅ 0

sharding-jdbc源码分析—准备工作

原文作者:阿飞Javaer 原文链接:https://www.jianshu.com/p/7831817c1da8 接下来对sharding-jdbc源码的分析基于tag为源码,根据sharding-jdbc Features深入学习sharding-jdbc的几个主要特性...

飞哥-Javaer ⋅ 05/03 ⋅ 0

2018年java编程语言经典基础知识总结学习

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰 ⋅ 05/21 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

apollo配置中心的学习笔记

公司现在配置文件太多了,导致配置文件修改起来还是非常麻烦的。在boss(业务运营支撑系统)中,配置文件是存放在jar包的,通过应用jar包来引用配置文件(区分不同环境)。这种方式虽然能够满足...

miaojiangmin ⋅ 4分钟前 ⋅ 0

Jena增删改查AP

插入、更新数据 public static void insert(){ String query = "PREFIX book: <http://www.book.com/jinyong/> \n" + " INSERT DATA \n" + ......

Vincent-Duan ⋅ 4分钟前 ⋅ 0

springMVC之与json数据交互方法

因为我也要返回json数据。所以需要这个注解@ResponseBody,把Java对象转换成json字符串 注意: 1、@RequestBody不能省,因为前台发过来的数据是json数据,得用这个注解去解析该怎么接收这些数...

颖伙虫 ⋅ 8分钟前 ⋅ 0

用实例域代替序号(31)

1、许多枚举天生就与一个单独的int 值相关联 ordinal 方法,返回枚举常量在类型中的数字位置 下述,枚举修改很不方便,不好维护 永远不要根据枚举的序数导出与他相关联的值 而是将他保存在一...

职业搬砖20年 ⋅ 10分钟前 ⋅ 0

并发编程---ConcurrentHashMap源码解析

ConcurrentHashMap是java中为了解决HashMap不能支持高并发而设计的新的实现。 ConcurrentHashMap的类结构 public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> implements C......

千古一梦888 ⋅ 13分钟前 ⋅ 0

微服务 WildFly Swarm 简介

我们将看到的最后一个Java微服务框架是一个相对较新的场景,它利用了 JBoss WildFly 应用服务器中已试过且受信任的 JavaEE 功能。WildFly Swarm 是 WildFly 应用服务器的一个完整的拆下来的组...

woshixin ⋅ 18分钟前 ⋅ 0

android apk 瘦身

头条APK瘦身之路 随着版本迭代,功能增加安装包体积也会慢慢增大。 今日头条576版本APK达到了25M,通过一系列的优化,到目前的607版本为12M。本文主要是介绍头条APK瘦身中用到的一些方法。 ...

GoldenVein ⋅ 22分钟前 ⋅ 1

mac机器学习开发环境部署及helloworld

一、下载并安装Anaconda2.7 https://repo.anaconda.com/archive/Anaconda2-5.2.0-MacOSX-x86_64.pkg 路径:/Users/shijun/anaconda2 二、运行Anaconda Navigator -> Environments -> base(ro......

八戒八戒八戒 ⋅ 33分钟前 ⋅ 0

关于日常开发的经验总结(Java),持续更新中

常量尽量使用枚举来表示,这样表现力会很强,因为枚举比一个常量类要有更多的扩展性 方法的入参和出参尽量不要使用Map,因为Map会让调用者感到迷惑,他不知道你里面装的什么,面向对象的开发...

小99 ⋅ 33分钟前 ⋅ 0

IDEA创建SpringMVC+Mybatis+Maven项目

视频如下(加载有点慢请见谅,服务器不太好): 视频

影狼 ⋅ 34分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部