精华内容
下载资源
问答
  • JAVA算法竞赛输入输出专题
    千次阅读 多人点赞
    2018-12-23 01:27:00

    2020.2.23更新,增加了数组模块


    前言

    小编由于报名了蓝桥杯Java组,所以日常做题从使用C/C++转变成使用Java。在转变的过程中,肯定会遇到很多大大小小的输入输出问题。小编打算总结下来,当做自己学习的材料,也分享给感兴趣的朋友。

    文件名问题

    在比赛提交的代码中,主类必须以public class Main来命名,而且不能带package语句否则会报出编译错误。

    //去掉public或者不使用Main作为类名都会gg,亲测有效orz

    基本的输入和输出

    竞赛入门最经典的问题,莫过于A+B Problem,如果连最基本的输入输出都做不到,学了再多的算法也用不出来。

    import java.util.*;
    public class Main {
    
    	public static void main(String[] args) {
    		Scanner cin = new Scanner(System.in);
    		int a, b;
    		while (cin.hasNext()) {
    			a = cin.nextInt();
    			b = cin.nextInt();
    			System.out.println(a + b);
    		}
    	}
    }
    

    上面代码展示了最基本的输入输出框架,输入类Scanner包含在java.util类包中,首先应该把它导入。

    import java.util.*;
    

    由于java的输入需要预先创建输入类对象,所以我们一般习惯在main函数的第一句先创建这个Scanner类对象,对象命名为cin算是表达对C/C++的热爱和怀念吧hhh
    如果题目数据量比较大的话可以选择第二种初始化方法,运行效率会高上一些。

    Scanner cin = new Scanner(System.in);
    //or
    Scanner cin = new Scanner(new BufferedInputStream(System.in));
    

    由于题目说明“输入包括多组数据,到文件结尾为止”,类比C/C++的格式,我们很容易理解以下的这段java代码

    while (cin.hasNext())  //当输入流中还有数据时
    {
        a = cin.nextInt();
    	b = cin.nextInt();
    }
    

    1.基本数据类型

    这些类型在C/C++中基本上已经用烂了,一般过目一遍就会了。

    int n = cin.nextInt();//读入一个整数
    double d = cin.nextDouble();//读入一个双精度浮点数
    long l = cin.nextLong();//读入一个长整型数
    

    需要注意一点:由于Java的main方法是static类型,所以定义全局变量或者方法的时候就需要加上static关键字!

    2.数组

    关于数组的创建,Java和C/C++也有所不同,它在创建时需要使用new关键字来为其分配存储空间,不过也不会非常麻烦。

    int arr[] = new int[Size];
    //or
    int []arr = new int[Size];
    

    对于二维数组的初始化问题,可以看看我写的另一篇文章:Java 二维数组的初始化

    3.字符&字符串

    Scanner类中并没有提供单个字符char类型的读入方法,但是我们可以先调用next()方法读取只包含一个字符的字符串,然后用charAt(0)返回0号索引处的字符,即可得到读取到单个字符。

    char ch = cin.next().charAt(0);
    

    对于字符串,java中已经封装好了字符串String类,我们也可以用char数组在进行字符串存储。

    String str1 = next(); //相当于C/C++中的scanf("%s",str);或cin>>str;
    String str2 = nextLine();//相当于C/C++中的gets(str2);或者getline(cin,str2);
    
    char s1[] = cin.next().toCharArray();//调用toCharArray()方法将其转化为char类型数组
    char s2[] = cin.nextLine().toCharArray();//类比理解
    

    但是要注意的是,我们不能像C++那样直接用数组下标去访问String类对象中的某号字符。 我们通常利用charAt(int index)方法来访问String类对象中的某号字符,或者不需要调用String类的其他方法的情况下,直接采用char类型数组来存储字符串。

    4.输出

    日常基本的输出:

    System.out.println(); //相当于C++中的cout<<endl;
    System.out.print();   //相当于C++中的cout<<"";
    

    输出到文件中:
    以下情况可能会用到输出到文件中

    • 当数据量过于庞大,java的控制台都无法输出,需要输出到文件中。
    • 用暴力法打表,需要按格式先输入到文件中。
    try {
    	BufferedWriter bw = new BufferedWriter(new FileWriter(new File("E://result.txt")));
    	bw.write(str);//str表示写入文件的内容
    	bw.flush();//立刻将缓存区的数据写入数据流
    	bw.close();//将BufferedWriter流关闭
    } catch (Exception e) {
    	e.printStackTrace();
    }
    

    File(string pathname); 用于初始化文件类,pathname表示文件的路径
    FileWriter(File file); 用于初始化文件写入类FileWriter,file表示文件类对象





    未完待续…

    更多相关内容
  • 什么是java算法

    千次阅读 2021-02-26 10:11:41
    什么是java算法算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,java算法就是采用Java语言来实现解决某一问题的清晰指令。算法的特征:输入性:有零个或多个外部量作为算法的输入输出性:算法产生...

    12da98a592521c0e0eed01394abd4d6b.png

    什么是java算法

    算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,java算法就是采用Java语言来实现解决某一问题的清晰指令。

    算法的特征:

    输入性:有零个或多个外部量作为算法的输入

    输出性:算法产生至少一个量作为输出

    确定性:算法中每条指令清晰,无歧义

    有穷性:算法中每条指令的执行次数有限,执行每条指令是时间也有限

    可行性:算法原则上能够精确的运行,而且人们用纸和笔做有限次运算后即可完成

    程序:算法用某种程序设计语言的具体实现,程序可以不满足又穷性

    算法的四个标准:

    正确性:在合理的数据输入下,能在有限时间内得出正确的结果

    可读性:应易于人的理解,易于调试

    健壮性:具备检查错误和对错误进行适当处理的能力

    效率:算法执行时所需计算机资源的多少,包括运行时间和存储空间

    算法的描述形式:1、自然语言 2、算法框图法 3、伪代码语言 4、高级程序设计语言

    算法设计的一般过程:

    1、理解问题

    2、预测所有可能是输入

    3、在精确解和近似解间做选择

    4、确定适当的数据结构

    5、算法设计技术

    6、描述算法

    7、跟踪算法

    8、分析算法的效率

    9、根据算法编写代码

    下面是Java实现的一个算法:冒泡排序/**

    * 冒泡排序

    */

    public class BubbleSort1 {

    public static void BubbleSort(int[] arr) {

    boolean flag = true;

    while(flag){

    int temp;//定义一个临时变量

    for(int i=0;i

    for(int j=0;j

    if(arr[j+1]

    temp = arr[j];

    arr[j] = arr[j+1];

    arr[j+1] = temp;

    flag = true;

    }

    }

    if(!flag){

    break;//若果没有发生交换,则退出循环

    }

    }

    }

    }

    public static void main(String[] args) {

    int arr[] = new int[]{1,6,2,2,5};

    BubbleSort.BubbleSort(arr);

    System.out.println(Arrays.toString(arr));

    }

    }

    相关文章教程推荐:java入门教程

    展开全文
  • java常用几种加密算法

    2017-05-16 14:34:50
    详细描述了java常用几种加密算法以及例子
  • java算法大全

    热门讨论 2015-01-21 10:10:43
    · 探索使用C、C++、Java以及Ruby实现的算法解决方案以及开发小贴士。 · 了解算法预期的性能,以及它达到最高性能时所需要的条件。 · 发现不同算法之间相似的设计哲学。 · 学习高级数据结构,来提升算法的性能...
  • Java算法刷题带注释Leetcode,基础算法
  • kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
  • java算法 面试必备 安卓面试 必备算法
  • java遗传算法编程pdf

    热门讨论 2017-09-15 09:58:37
    一本基于java遗传算法编程技术的讲解书书籍,全书讲解很全面,适合对遗传算法感兴趣的读者。本书共分为6章,每章都会有实例。
  • SVM 算法 java 实现

    2016-12-21 13:44:09
    SVM 算法 java 实现了调用接口,只要传入数据即可,调用了encog这个开源包的SVM算法,也是官方libsvm的。
  • java实现apriori算法

    2016-12-15 15:43:53
    本实验使用的编程语言为:Java 编程环境为:Intellij idea 实现频繁项集的挖掘算法为Apriori算法 用于挖掘的样本个数为:1000个(retail.txt的前1000条数据) 样本示例: { 38,39,47,48} 表示一个顾客购买了ID为38、...
  • 一份很好的java 算法大全,java进阶的必备神器。非常经典的一些小算法。搞java的可以备一份
  • 采用java实现的常用hash算法归总。
  • 协同过滤算法 java源码 协同过滤常常被用于分辨某位特定顾客可能感兴趣的东西,这些结论来自于对其他相似顾客对哪些产品感兴趣的分析。协同过滤以其出色的速度和健壮性,在全球互联网领域炙手可热。
  • 遗传算法(GeneticAlgorithm)的Java实现源码工程,可导入eclipse后可直接运行工程,main方法在类GeneticAlgorithmTest文件中。带有图形界面动态展示遗传算法的收敛过程。你可以在此基础上改动后运用于你的项目中。
  • java 国密算法实现,包含SM2 SM3 SM4和数字签名、数字证书的验证以及相应的说明文档
  • java算法大全源码包 java算法大全,有近100多种常见算法的源代码,是学习JAVA算法的难得资料。
  • 协同过滤推荐算法java实现

    千次下载 热门讨论 2014-05-14 20:55:30
    本资源是推荐系统中最基本且最精但的协同过滤推荐算法实现,包括数据集,以及算法的评价指标MAE的计算,数据集采用MovieLens中两个数据集进行测试,需要别的数据集可以根据自己需要添加,只需修改Base.java文件中的...
  • 《神经网络算法与实现基于Java语言》 用java实现多种人工神经网络附带多个示例,花费了很长时间重新做了完整标签,目录一目了然
  • Java数据结构和算法

    2017-09-09 21:50:29
    Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法
  • Java实现蚁群算法

    2015-12-04 20:11:25
    Java实现蚁群算法,简单易懂的代码,比较适合新手学习
  • AES加密算法java)实现

    热门讨论 2015-01-15 16:32:38
    这个标准用来替代原先的DES,已经被多方分析且广为全世界所使用。...本软件是用java语言开发,实现了AES算法对文件的加密和解密,并在界面上加了进度条,来提示用户加密解密的进度。如果不足之处,欢迎留言。
  • java校验和算法

    2015-01-20 14:17:22
    由于需要和蓝牙通讯,协议需要用到校验和,找了很久才找到,给大家共享。java校验和算法绝对可以用。
  • Java实现simHash算法

    热门讨论 2015-05-21 00:05:33
    Java实现simHash算法,对应博客http://www.cnblogs.com/hxsyl/p/4518506.html
  • 匈牙利算法java实现

    热门讨论 2012-12-06 11:12:07
    java实现的匈牙利算法,
  • Java数据结构和算法中文第二版源码

    热门讨论 2015-09-01 12:02:09
    数据结构和算法能起到什么作用? 数据结构的概述 算法的概述 一些定义 面向对象编程 软件工程 对于C++程序员的Java Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将程序划分成类...
  • java用遗传算法解决旅行商问题
  • Java基础算法详解

    万次阅读 多人点赞 2018-06-20 07:56:13
    查找和排序算法算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只要熟悉了思想,灵活运用也不是难事。一般在...

    前言

      查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只要熟悉了思想,灵活运用也不是难事。一般在面试中最常考的是快速排序和归并排序,并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。面试官对于这些排序可能会要求比较各自的优劣、各种算法的思想及其使用场景。还有要会分析算法的时间和空间复杂度。通常查找和排序算法的考察是面试的开始,如果这些问题回答不好,估计面试官都没有继续面试下去的兴趣都没了。所以想开个好头就要把常见的排序算法思想及其特点要熟练掌握,有必要时要熟练写出代码。

      接下来我们就分析一下常见的排序算法及其使用场景。限于篇幅,某些算法的详细演示和图示请自行寻找详细的参考。

    冒泡排序

      冒泡排序是最简单的排序之一了,其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样,因此而得名。举个栗子,对5,3,8,6,4这个无序序列进行冒泡排序。首先从后向前冒泡,4和6比较,把4交换到前面,序列变成5,3,8,4,6。同理4和8交换,变成5,3,4,8,6,3和4无需交换。5和3交换,变成3,5,4,8,6,3.这样一次冒泡就完了,把最小的数3排到最前面了。对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)。

    实现代码:

    /**
     *@Description:<p>冒泡排序算法实现</p>
     *@author 王旭
     *@time 2016-3-3 下午8:54:27
     */
    public class BubbleSort {
        
        public static void bubbleSort(int[] arr) {
            if(arr == null || arr.length == 0)
                return ;
            for(int i=0; i<arr.length-1; i++) {
                for(int j=arr.length-1; j>i; j--) {
                    if(arr[j] < arr[j-1]) {
                        swap(arr, j-1, j);
                    }
                }
            }
        }
        
        
        public static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    选择排序

      选择排序的思想其实和冒泡排序有点类似,都是在一次排序后把最小的元素放到最前面。但是过程不同,冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。举个栗子,对5,3,8,6,4这个无序序列进行简单选择排序,首先要选择5以外的最小数来和5交换,也就是选择3和5交换,一次排序后就变成了3,5,8,6,4.对剩下的序列一次进行选择和交换,最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化,因为其目的相同,只是选择排序只有在确定了最小数的前提下才进行交换,大大减少了交换的次数。选择排序的时间复杂度为O(n^2)

    实现代码:

    /**
     *@Description:<p>简单选择排序算法的实现</p>
     *@author 王旭
     *@time 2016-3-3 下午9:13:35
     */
    public class SelectSort {
        
        public static void selectSort(int[] arr) {
            if(arr == null || arr.length == 0)
                return ;
            int minIndex = 0;
            for(int i=0; i<arr.length-1; i++) { //只需要比较n-1次
                minIndex = i;
                for(int j=i+1; j<arr.length; j++) { //从i+1开始比较,因为minIndex默认为i了,i就没必要比了。
                    if(arr[j] < arr[minIndex]) {
                        minIndex = j;
                    }
                }
                
                if(minIndex != i) { //如果minIndex不为i,说明找到了更小的值,交换之。
                    swap(arr, i, minIndex);
                }
            }
            
        }
        
        public static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
    }

    插入排序

      插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。相信大家都有过打扑克牌的经历,特别是牌数较大的。在分牌时可能要整理自己的牌,牌多的时候怎么整理呢?就是拿到一张牌,找到一个合适的位置插入。这个原理其实和插入排序是一样的。举个栗子,对5,3,8,6,4这个无序序列进行简单插入排序,首先假设第一个数的位置时正确的,想一下在拿到第一张牌的时候,没必要整理。然后3要插到5前面,把5后移一位,变成3,5,8,6,4.想一下整理牌的时候应该也是这样吧。然后8不用动,6插在8前面,8后移一位,4插在5前面,从5开始都向后移一位。注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O(n^2)。

    实现代码:

    /**
     *@Description:<p>简单插入排序算法实现</p>
     *@author 王旭
     *@time 2016-3-3 下午9:38:55
     */
    public class InsertSort {
        
        public static void insertSort(int[] arr) {
            if(arr == null || arr.length == 0)
                return ;
            
            for(int i=1; i<arr.length; i++) { //假设第一个数位置时正确的;要往后移,必须要假设第一个。
                
                int j = i;
                int target = arr[i]; //待插入的
                
                //后移
                while(j > 0 && target < arr[j-1]) {
                    arr[j] = arr[j-1];
                    j --;
                }
                
                //插入 
                arr[j] = target;
            }
                
        }
    
    }

    快速排序

      快速排序一听名字就觉得很高端,在实际应用当中快速排序确实也是表现最好的排序算法。快速排序虽然高端,但其实其思想是来自冒泡排序,冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端,而快速排序是比较和交换小数和大数,这样一来不仅把小数冒泡到上面同时也把大数沉到下面。

    举个栗子:对5,3,8,6,4这个无序序列进行快速排序,思路是右指针找比基准数小的,左指针找比基准数大的,交换之。

    5,3,8,6,4 用5作为比较的基准,最终会把5小的移动到5的左边,比5大的移动到5的右边。

    5,3,8,6,4 首先设置i,j两个指针分别指向两端,j指针先扫描(思考一下为什么?)4比5小停止。然后i扫描,8比5大停止。交换i,j位置。

    5,3,4,6,8 然后j指针再扫描,这时j扫描4时两指针相遇。停止。然后交换4和基准数。

    4,3,5,6,8 一次划分后达到了左边比5小,右边比5大的目的。之后对左右子序列递归排序,最终得到有序序列。

    上面留下来了一个问题为什么一定要j指针先动呢?首先这也不是绝对的,这取决于基准数的位置,因为在最后两个指针相遇的时候,要交换基准数到相遇的位置。一般选取第一个数作为基准数,那么就是在左边,所以最后相遇的数要和基准数交换,那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。

    快速排序是不稳定的,其时间平均时间复杂度是O(nlgn)。

    实现代码:

    /**
     *@Description:<p>实现快速排序算法</p>
     *@author 王旭
     *@time 2016-3-3 下午5:07:29
     */
    public class QuickSort {
        //一次划分
        public static int partition(int[] arr, int left, int right) {
            int pivotKey = arr[left];
            int pivotPointer = left;
            
            while(left < right) {
                while(left < right && arr[right] >= pivotKey)
                    right --;
                while(left < right && arr[left] <= pivotKey)
                    left ++;
                swap(arr, left, right); //把大的交换到右边,把小的交换到左边。
            }
            swap(arr, pivotPointer, left); //最后把pivot交换到中间
            return left;
        }
        
        public static void quickSort(int[] arr, int left, int right) {
            if(left >= right)
                return ;
            int pivotPos = partition(arr, left, right);
            quickSort(arr, left, pivotPos-1);
            quickSort(arr, pivotPos+1, right);
        }
        
        public static void sort(int[] arr) {
            if(arr == null || arr.length == 0)
                return ;
            quickSort(arr, 0, arr.length-1);
        }
        
        public static void swap(int[] arr, int left, int right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        
    }

       其实上面的代码还可以再优化,上面代码中基准数已经在pivotKey中保存了,所以不需要每次交换都设置一个temp变量,在交换左右指针的时候只需要先后覆盖就可以了。这样既能减少空间的使用还能降低赋值运算的次数。优化代码如下:

    /**
     *@Description:<p>实现快速排序算法</p>
     *@author 王旭
     *@time 2016-3-3 下午5:07:29
     */
    public class QuickSort {
        
        /**
         * 划分
         * @param arr
         * @param left
         * @param right
         * @return
         */
        public static int partition(int[] arr, int left, int right) {
            int pivotKey = arr[left];
            
            while(left < right) {
                while(left < right && arr[right] >= pivotKey)
                    right --;
                arr[left] = arr[right]; //把小的移动到左边
                while(left < right && arr[left] <= pivotKey)
                    left ++;
                arr[right] = arr[left]; //把大的移动到右边
            }
            arr[left] = pivotKey; //最后把pivot赋值到中间
            return left;
        }
        
        /**
         * 递归划分子序列
         * @param arr
         * @param left
         * @param right
         */
        public static void quickSort(int[] arr, int left, int right) {
            if(left >= right)
                return ;
            int pivotPos = partition(arr, left, right);
            quickSort(arr, left, pivotPos-1);
            quickSort(arr, pivotPos+1, right);
        }
        
        public static void sort(int[] arr) {
            if(arr == null || arr.length == 0)
                return ;
            quickSort(arr, 0, arr.length-1);
        }
        
    }

    总结快速排序的思想:冒泡+二分+递归分治,慢慢体会。。。

    堆排序

      堆排序是借助堆来实现的选择排序,思想同简单的选择排序,以下以大顶堆为例。注意:如果想升序排序就使用大顶堆,反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。

      首先,实现堆排序需要解决两个问题:

      1. 如何由一个无序序列键成一个堆?

      2. 如何在输出堆顶元素之后,调整剩余元素成为一个新的堆?

      第一个问题,可以直接使用线性数组来表示一个堆,由初始的无序序列建成一个堆就需要自底向上从第一个非叶元素开始挨个调整成一个堆。

      第二个问题,怎么调整成堆?首先是将堆顶元素和最后一个元素交换。然后比较当前堆顶元素的左右孩子节点,因为除了当前的堆顶元素,左右孩子堆均满足条件,这时需要选择当前堆顶元素与左右孩子节点的较大者(大顶堆)交换,直至叶子节点。我们称这个自堆顶自叶子的调整成为筛选。

      从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树,则最后一个非终端节点是n/2取底个元素,由此筛选即可。举个栗子:

    49,38,65,97,76,13,27,49序列的堆排序建初始堆和调整的过程如下:

     

     

     

    实现代码:

    /**
     *@Description:<p>堆排序算法的实现,以大顶堆为例。</p>
     *@author 王旭
     *@time 2016-3-4 上午9:26:02
     */
    public class HeapSort {
        
        /**
         * 堆筛选,除了start之外,start~end均满足大顶堆的定义。
         * 调整之后start~end称为一个大顶堆。
         * @param arr 待调整数组
         * @param start 起始指针
         * @param end 结束指针
         */
        public static void heapAdjust(int[] arr, int start, int end) {
            int temp = arr[start];
            
            for(int i=2*start+1; i<=end; i*=2) {
                //左右孩子的节点分别为2*i+1,2*i+2
                
                //选择出左右孩子较小的下标
                if(i < end && arr[i] < arr[i+1]) {
                    i ++; 
                }
                if(temp >= arr[i]) {
                    break; //已经为大顶堆,=保持稳定性。
                }
                arr[start] = arr[i]; //将子节点上移
                start = i; //下一轮筛选
            }
            
            arr[start] = temp; //插入正确的位置
        }
        
        
        public static void heapSort(int[] arr) {
            if(arr == null || arr.length == 0)
                return ;
            
            //建立大顶堆
            for(int i=arr.length/2; i>=0; i--) {
                heapAdjust(arr, i, arr.length-1);
            }
            
            for(int i=arr.length-1; i>=0; i--) {
                swap(arr, 0, i);
                heapAdjust(arr, 0, i-1);
            }
            
        }
        
        public static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
    }

    希尔排序

      希尔排序是插入排序的一种高效率的实现,也叫缩小增量排序。简单的插入排序中,如果待排序列是正序时,时间复杂度是O(n),如果序列是基本有序的,使用直接插入排序效率就非常高。希尔排序就利用了这个特点。基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。

    举个栗子:

     

       从上述排序过程可见,希尔排序的特点是,子序列的构成不是简单的逐段分割,而是将某个相隔某个增量的记录组成一个子序列。如上面的例子,第一堂排序时的增量为5,第二趟排序的增量为3。由于前两趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关键字进行比较,因此关键字较小的记录就不是一步一步地向前挪动,而是跳跃式地往前移,从而使得进行最后一趟排序时,整个序列已经做到基本有序,只要作记录的少量比较和移动即可。因此希尔排序的效率要比直接插入排序高。

      希尔排序的分析是复杂的,时间复杂度是所取增量的函数,这涉及一些数学上的难题。但是在大量实验的基础上推出当n在某个范围内时,时间复杂度可以达到O(n^1.3)。

    实现代码:

    /**
     *@Description:<p>希尔排序算法实现</p>
     *@author 王旭
     *@time 2016-3-3 下午10:53:55
     */
    public class ShellSort {
        
        /**
         * 希尔排序的一趟插入
         * @param arr 待排数组
         * @param d 增量
         */
        public static void shellInsert(int[] arr, int d) {
            for(int i=d; i<arr.length; i++) {
                int j = i - d;
                int temp = arr[i];    //记录要插入的数据  
                while (j>=0 && arr[j]>temp) {  //从后向前,找到比其小的数的位置   
                    arr[j+d] = arr[j];    //向后挪动  
                    j -= d;  
                }  
          
                if (j != i - d)    //存在比其小的数 
                    arr[j+d] = temp;
                
            }
        }
        
        public static void shellSort(int[] arr) {
            if(arr == null || arr.length == 0)
                return ;
            int d = arr.length / 2;
            while(d >= 1) {
                shellInsert(arr, d);
                d /= 2;
            }
        }
    
    }  

    归并排序

      归并排序是另一种不同的排序方法,因为归并排序使用了递归分治的思想,所以理解起来比较容易。其基本思想是,先递归划分子问题,然后合并结果。把待排序列看成由两个有序的子序列,然后合并两个子序列,然后把子序列看成由两个有序序列。。。。。倒着来看,其实就是先两两合并,然后四四合并。。。最终形成有序序列。空间复杂度为O(n),时间复杂度为O(nlogn)。

    举个栗子:

    实现代码:

    /**
     *@Description:<p>归并排序算法的实现</p>
     *@author 王旭
     *@time 2016-3-4 上午8:14:20
     */
    public class MergeSort {
        
        public static void mergeSort(int[] arr) {
            mSort(arr, 0, arr.length-1);
        }
    
        /**
         * 递归分治
         * @param arr 待排数组
         * @param left 左指针
         * @param right 右指针
         */
        public static void mSort(int[] arr, int left, int right) {
            if(left >= right)
                return ;
            int mid = (left + right) / 2;
            
            mSort(arr, left, mid); //递归排序左边
            mSort(arr, mid+1, right); //递归排序右边
            merge(arr, left, mid, right); //合并
        }
        
        /**
         * 合并两个有序数组
         * @param arr 待合并数组
         * @param left 左指针
         * @param mid 中间指针
         * @param right 右指针
         */
        public static void merge(int[] arr, int left, int mid, int right) {
            //[left, mid] [mid+1, right]
            int[] temp = new int[right - left + 1]; //中间数组
            
            int i = left;
            int j = mid + 1;
            int k = 0;
            while(i <= mid && j <= right) {
                if(arr[i] <= arr[j]) {
                    temp[k++] = arr[i++];
                }
                else {
                    temp[k++] = arr[j++];
                }
            }
            
            while(i <= mid) {
                temp[k++] = arr[i++];
            }
            
            while(j <= right) {
                temp[k++] = arr[j++];
            }
            
            for(int p=0; p<temp.length; p++) {
                arr[left + p] = temp[p];
            }
            
        }
    }

    计数排序

      如果在面试中有面试官要求你写一个O(n)时间复杂度的排序算法,你千万不要立刻说:这不可能!虽然前面基于比较的排序的下限是O(nlogn)。但是确实也有线性时间复杂度的排序,只不过有前提条件,就是待排序的数要满足一定的范围的整数,而且计数排序需要比较多的辅助空间。其基本思想是,用待排序的数作为计数数组的下标,统计每个数字的个数。然后依次输出即可得到有序序列。

    实现代码:

    /**
     *@Description:<p>计数排序算法实现</p>
     *@author 王旭
     *@time 2016-3-4 下午4:52:02
     */
    public class CountSort {
        
        public static void countSort(int[] arr) {
            if(arr == null || arr.length == 0)
                return ;
            
            int max = max(arr);
            
            int[] count = new int[max+1];
            Arrays.fill(count, 0);
            
            for(int i=0; i<arr.length; i++) {
                count[arr[i]] ++;
            }
            
            int k = 0;
            for(int i=0; i<=max; i++) {
                for(int j=0; j<count[i]; j++) {
                    arr[k++] = i;
                }
            }
            
        }
        
        public static int max(int[] arr) {
            int max = Integer.MIN_VALUE;
            for(int ele : arr) {
                if(ele > max)
                    max = ele;
            }
            
            return max;
        }
    
    }

    桶排序

      桶排序算是计数排序的一种改进和推广,但是网上有许多资料把计数排序和桶排序混为一谈。其实桶排序要比计数排序复杂许多。

      对桶排序的分析和解释借鉴这位兄弟的文章(有改动):http://hxraid.iteye.com/blog/647759

      桶排序的基本思想:

       假设有一组长度为N的待排关键字序列K[1....n]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数 ,将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ,那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]....B[M]中的全部内容即是一个有序序列。bindex=f(key)   其中,bindex 为桶数组B的下标(即第bindex个桶), k为待排序列的关键字。桶排序之所以能够高效,其关键在于这个映射函数,它必须做到:如果关键字k1<k2,那么f(k1)<=f(k2)。也就是说B(i)中的最小数据都要大于B(i-1)中最大数据。很显然,映射函数的确定与数据本身的特点有很大的关系。

    举个栗子:

      假如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。这些数据全部在1—100之间。因此我们定制10个桶,然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中,并在每个非空的桶中进行快速排序后得到如图所示。只要顺序输出每个B[i]中的数据就可以得到有序序列了。

    桶排序分析:

      桶排序利用函数的映射关系,减少了几乎所有的比较工作。实际上,桶排序的f(k)值的计算,其作用就相当于快排中划分,希尔排序中的子序列,归并排序中的子问题,已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。 

    对N个关键字进行桶排序的时间复杂度分为两个部分:

      (1) 循环计算每个关键字的桶映射函数,这个时间复杂度是O(N)。

      (2) 利用先进的比较排序算法对每个桶内的所有数据进行排序,其时间复杂度为  ∑ O(Ni*logNi) 。其中Ni 为第i个桶的数据量。

    很显然,第(2)部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N*logN)了)。因此,我们需要尽量做到下面两点:

      (1) 映射函数f(k)能够将N个数据平均的分配到M个桶中,这样每个桶就有[N/M]个数据量。

      (2) 尽量的增大桶的数量。极限情况下每个桶只能得到一个数据,这样就完全避开了桶内数据的“比较”排序操作。当然,做到这一点很不容易,数据量巨大的情况下,f(k)函数会使得桶集合的数量巨大,空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。

    对于N个待排数据,M个桶,平均每个桶[N/M]个数据的桶排序平均时间复杂度为:

                 O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

    当N=M时,即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。

    总结: 桶排序的平均时间复杂度为线性的O(N+C),其中C=N*(logN-logM)。如果相对于同样的N,桶数量M越大,其效率越高,最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。此外,桶排序是稳定的。

    实现代码:

    /**
     *@Description:<p>桶排序算法实现</p>
     *@author 王旭
     *@time 2016-3-4 下午7:39:31
     */
    public class BucketSort {
        
        public static void bucketSort(int[] arr) {
            if(arr == null && arr.length == 0)
                return ;
            
            int bucketNums = 10; //这里默认为10,规定待排数[0,100)
            List<List<Integer>> buckets = new ArrayList<List<Integer>>(); //桶的索引
            
            for(int i=0; i<10; i++) {
                buckets.add(new LinkedList<Integer>()); //用链表比较合适
            }
            
            //划分桶
            for(int i=0; i<arr.length; i++) {
                buckets.get(f(arr[i])).add(arr[i]);
            }
            
            //对每个桶进行排序
            for(int i=0; i<buckets.size(); i++) {
                if(!buckets.get(i).isEmpty()) {
                    Collections.sort(buckets.get(i)); //对每个桶进行快排
                }
            }
            
            //还原排好序的数组
            int k = 0;
            for(List<Integer> bucket : buckets) {
                for(int ele : bucket) {
                    arr[k++] = ele;
                }
            }
        }
        
        /**
         * 映射函数
         * @param x
         * @return
         */
        public static int f(int x) {
            return x / 10;
        }
    
    }

    基数排序

      基数排序又是一种和前面排序方式不同的排序方式,基数排序不需要进行记录关键字之间的比较。基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。所谓的多关键字排序就是有多个优先级不同的关键字。比如说成绩的排序,如果两个人总分相同,则语文高的排在前面,语文成绩也相同则数学高的排在前面。。。如果对数字进行排序,那么个位、十位、百位就是不同优先级的关键字,如果要进行升序排序,那么个位、十位、百位优先级一次增加。基数排序是通过多次的收分配和收集来实现的,关键字优先级低的先进行分配和收集。

    举个栗子:

     

     

    实现代码:

    /**
     *@Description:<p>基数排序算法实现</p>
     *@author 王旭
     *@time 2016-3-4 下午8:29:52
     */
    public class RadixSort {
        
        public static void radixSort(int[] arr) {
            if(arr == null && arr.length == 0)
                return ;
            
            int maxBit = getMaxBit(arr);
            
            
            for(int i=1; i<=maxBit; i++) {
                
                List<List<Integer>> buf = distribute(arr, i); //分配
                collecte(arr, buf); //收集
            }
            
        }
        
        /**
         * 分配
         * @param arr 待分配数组
         * @param iBit 要分配第几位
         * @return
         */
        public static List<List<Integer>> distribute(int[] arr, int iBit) {
            List<List<Integer>> buf = new ArrayList<List<Integer>>();
            for(int j=0; j<10; j++) {
                buf.add(new LinkedList<Integer>());
            }
            for(int i=0; i<arr.length; i++) {
                buf.get(getNBit(arr[i], iBit)).add(arr[i]);
            }
            return buf;
        }
        
        /**
         * 收集
         * @param arr 把分配的数据收集到arr中
         * @param buf 
         */
        public static void collecte(int[] arr, List<List<Integer>> buf) {
            int k = 0;
            for(List<Integer> bucket : buf) {
                for(int ele : bucket) {
                    arr[k++] = ele;
                }
            }
            
            
        }
        
        /**
         * 获取最大位数
         * @param x
         * @return
         */
        public static int getMaxBit(int[] arr) {
            int max = Integer.MIN_VALUE;
            for(int ele : arr) {
                int len = (ele+"").length();
                if(len > max)
                    max = len;
            }
            return max;
        }
        
        /**
         * 获取x的第n位,如果没有则为0.
         * @param x
         * @param n
         * @return
         */
        public static int getNBit(int x, int n) {
            
            String sx = x + "";
            if(sx.length() < n)
                return 0;
            else
                return sx.charAt(sx.length()-n) - '0';
        }
    
    }
    总结

      在前面的介绍和分析中我们提到了冒泡排序、选择排序、插入排序三种简单的排序及其变种快速排序、堆排序、希尔排序三种比较高效的排序。后面我们又分析了基于分治递归思想的归并排序还有计数排序、桶排序、基数排序三种线性排序。我们可以知道排序算法要么简单有效,要么是利用简单排序的特点加以改进,要么是以空间换取时间在特定情况下的高效排序。但是这些排序方法都不是固定不变的,需要结合具体的需求和场景来选择甚至组合使用。才能达到高效稳定的目的。没有最好的排序,只有最适合的排序。

      下面就总结一下排序算法的各自的使用场景和适用场合。

      1. 从平均时间来看,快速排序是效率最高的,但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是,在n较大时归并排序使用时间较少,但使用辅助空间较多。

      2. 上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。其中直接插入排序最简单,但序列基本有序或者n较小时,直接插入排序是好的方法,因此常将它和其他的排序方法,如快速排序、归并排序等结合在一起使用。

      3. 基数排序的时间复杂度也可以写成O(d*n)。因此它最使用于n值很大而关键字较小的的序列。若关键字也很大,而序列中大多数记录的最高关键字均不同,则亦可先按最高关键字不同,将序列分成若干小的子序列,而后进行直接插入排序。

      4. 从方法的稳定性来比较,基数排序是稳定的内排方法,所有时间复杂度为O(n^2)的简单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。稳定性需要根据具体需求选择。

      5. 上面的算法实现大多数是使用线性存储结构,像插入排序这种算法用链表实现更好,省去了移动元素的时间。具体的存储结构在具体的实现版本中也是不同的。

    附:基于比较排序算法时间下限为O(nlogn)的证明:

      基于比较排序下限的证明是通过决策树证明的,决策树的高度Ω(nlgn),这样就得出了比较排序的下限。

    首先要引入决策树。 首先决策树是一颗二叉树,每个节点表示元素之间一组可能的排序,它予以京进行的比较相一致,比较的结果是树的边。 先来说明一些二叉树的性质,令T是深度为d的二叉树,则T最多有2^片树叶。 具有L片树叶的二叉树的深度至少是logL。 所以,对n个元素排序的决策树必然有n!片树叶(因为n个数有n!种不同的大小关系),所以决策树的深度至少是log(n!),即至少需要log(n!)次比较。 而 log(n!)=logn+log(n-1)+log(n-2)+...+log2+log1 >=logn+log(n-1)+log(n-2)+...+log(n/2) >=(n/2)log(n/2) >=(n/2)logn-n/2 =O(nlogn) 所以只用到比较的排序算法最低时间复杂度是O(nlogn)。
    
    参考资料:
      《数据结构》 严蔚敏 吴伟民 编著
        桶排序分析:http://hxraid.iteye.com/blog/647759
        部分排序算法分析与介绍:http://www.cnblogs.com/weixliu/archive/2012/12/23/2829671.html
    展开全文
  • JAVA基础编程练习题50题及经典算法90题【含源码及答案】
  • java排课算法核心代码及思想

    热门讨论 2012-04-29 22:18:29
    java排课算法,基于贪婪法,对老师,教室和课程都进行了合理的调整,可作为毕业设计参考,这是本人毕业设计的核心算法,有不足之处请大家多多包涵。
  • 几个推荐算法java实现

    千次下载 热门讨论 2012-01-05 20:00:28
    java实现的几个推荐算法:slopeone SVD,RSVD,ItemNeighborSVD 内有readme,相关内容在blog.csdn.net/lgnlgn

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,320,934
精华内容 528,373
关键字:

java算法是什么

java 订阅