精华内容
下载资源
问答
  • 堆排序的思路主要就是建堆排序两部分组成。 2.建堆算法 Williams算法建堆法【Wil64】 时间复杂度为O(nlogn),空间为O(1) Floyd算法建堆法【Floo64】 一种更为高效的建堆方法,可以在O(时间)O(1)空间内完成建...

    一、概述

    1.堆排序的思路主要就是建堆和排序两部分组成。堆排序是基于二叉树的,那么我们首先得知道二叉树得基本特性。我们在堆排序中定义这样一种完整二叉树,其中每个结点的值都大于等于它的孩子,那么我们就称之为最大堆,同理还有最小堆。接下来重要的是我们在建立完最大堆之后,我们需要再次进行上浮或者下沉操作,使得二叉树仍然满足最大对的定义。

    2.二叉树概述

    二叉树得结点一般用于存储我们要处理的数据,而结点位置可以通过编号给出简单且唯一的描述:

    • 结点编号一般取整数,我们称树中编号为k的结点为结点k
    • 一棵非空二叉树根结点的编号为1,这是最小的编号
    • 结点k的左孩子和右孩子编号分别为2k和2k+1,而节点k称为这两个孩子的父亲

       按照上述规则,可知结点k的父亲结点编号为k/2。另外二叉树的层次也很重要,一般定义根节点 处于第0层,以此为基础不断递增,也即所有位于第L层的结点其孩子所在层次为L+1。二叉树的高度定义为该树中结点的最大层数,若二叉树是一颗结点总数为2^(h+1)-1的完整二叉树(h为二叉树的高度),那么称该二叉树为完美二叉树。
       二叉树中结点的的孩子数称为该节点的度,显然度为0的结点称为叶子结点,否则称为非叶子结点。若二叉树中非叶子结点的度均为2,那么就称该二叉树为满二叉树

    3.总结

    • 非空二叉树的第i层最多有2^i个结点
    • 高为h的非空二叉树最多包含的结点数为2^(h+1)-1个
    • 设i = 0,1,2 ,若非空二叉树中度为i的结点数为Ni,则N0 = N2 + 1

    二、建堆算法

    这里我在课本上学习的建堆方法有两种,分别是Williams建堆法Floyd建堆法,接下来将讲述这两种建堆方法的区别,在一般的堆排序中我们建议使用Floyd建堆法,因为它的时间复杂度更低并且代码更加容易实现。但是还是要将每种的实现步骤画一遍。

    1.Williams算法建堆法【Wil64】

    时间复杂度为O(nlogn),空间为O(1)
    例如我们对数组[4,7,5,8,6,0,2,3,9,1]进行从小到大排列,因为我们是要从小到达进行排列所以我们应该建立最大堆。
    我们知道在建立完最大堆之后,就要开始进行弹出操作,我们最先弹出的数字永远放在最后面因此从小到大的排列就需要建立最大堆。

    这是我们要排序的数组。
    在这里插入图片描述
    开始建堆
    第一步
    在这里插入图片描述
    第二步(因为7比4大所以交换顺序)
    在这里插入图片描述
    第三步(5比父节点小,所以当作6的右孩子就可以)
    在这里插入图片描述
    第四步
    在这里插入图片描述
    第五步
    在这里插入图片描述
    第六步
    在这里插入图片描述
    第七步
    在这里插入图片描述
    第八步
    在这里插入图片描述
    第九步
    在这里插入图片描述
    第十步
    在这里插入图片描述
    到这里我们就建完了我们的最大堆,
    接下来我们就开始进行弹出操作:
    首先走到这里我们一斤建好了我们的最大堆,我们现在就开始进行弹出操作,也就是我们的排序。
    第一步(弹出9)
    在这里插入图片描述
    第二步(弹出8)
    在这里插入图片描述
    第三步(弹出7)
    在这里插入图片描述
    第四步(弹出6)
    在这里插入图片描述
    第五步(弹出5)
    在这里插入图片描述
    第六步(弹出4)
    在这里插入图片描述
    第七步(弹出3)
    在这里插入图片描述
    第八步(弹出2)
    在这里插入图片描述
    第九步(弹出1)
    在这里插入图片描述
    第十步(弹出0)
    这里我们就已经排序完成,我们首先弹出来的在后面
    在这里插入图片描述

    2.Floyd算法建堆法【Floo64】

    一种更为高效的建堆方法,可以在O(时间)和O(1)空间内完成建堆任务。
    他的要点就是从最后一个非叶子结点从后向前对那些有孩子的结点执行下沉操作 ,从而来建立我们的最大堆。在开始之前还是要强调要会计算某个结点的左右孩子结点,和孩子节点的父结点。

    最开始的数组
    在这里插入图片描述
    建堆
    第一步(最开始的堆)
    在这里插入图片描述第二步(元素8无需调整,因为以它为根的子树已经是子堆)
    在这里插入图片描述
    第三步(元素0下沉后原位置对应一个以9为对顶的子堆)
    在这里插入图片描述第四步(元素6无需调整,因为以它为根的子树已经是子堆)
    在这里插入图片描述
    第五步(元素4下沉后原位置对应一个以9为对顶的子堆)
    在这里插入图片描述第六步(元素7下沉后原位置(已经是根节点)对应一个以9为对顶的子堆)
    在这里插入图片描述到这里我们就已经完成建堆任务,这里有一个定义Floyd算法可以在O(n)时间内完成对n个元素建堆的任务。
    后面的就和上一个弹出操作类似,这里就不展示每一次步骤了。

    三、基于Floyd建堆算法进行堆排序

    1.最小堆
    在开始之前我们前面已经知道了怎样表示一个结点的左孩子和右孩子,以及知道某个结点可以求出其父亲结点。先下面我们对数组进行从大到小排序,因此我么应该建立最小堆

    package org.westos.demo;
    
    
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class HeapSort3 {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入你要排序的数字的个数");
            int n = sc.nextInt();
            int[] tree = new int[n];
            for (int i = 0; i < tree.length; i++) {
                tree[i] = sc.nextInt();
            }
            heap_sort(tree,tree.length);
            System.out.println(Arrays.toString(tree));
        }
        //我们在建好堆的基础之上,进行排序,每次排完序之后要记得重新进行下沉操作,从而使得堆满足最大(小)堆的特性
        public static void heap_sort(int[]tree,int n){
            build_heap(tree,n);
            for (int i = n-1; i >= 0; i--) {
                swap(tree,i,0);
                heapify(tree,i,0);
            }
        }
    
        /**
         *
         * @param tree 要排序的数组
         * @param n    数组的长度
         * 从最后一个非叶子结点从后向前进行建堆,这里我们使用的是Floyd建堆算法
         */
        public static void build_heap(int[]tree,int n){
            int last_node = n - 1;
            int parent = (last_node - 1)/2;
            for (int i = parent;i >= 0;i--){
                heapify(tree,n,i);
            }
        }
    
        /**
         *
         * @param tree 要排序的数组
         * @param n    数组的长度
         * @param i    表示第i个节点
         * 这里我们对元素进行下沉操作
         */
        public static void heapify(int[]tree,int n,int i){
            if(i >= n){
                return;
            }
            int c1 = 2 * i +1;//左孩子结点
            int c2 = 2 * i +2;//右孩子结点
            int max = i;//父亲结点
            //下面就是判断父亲结点和孩子结点的大小,从而进行下沉操作
            if (c1 < n && tree[max] > tree[c1]){//这里得加上c1 < n 防止越界
                max = c1;
            }
            if (c2 < n && tree[max] > tree[c2]){//这里得加上c2 < n 防止越界
                max = c2;
            }
            if (max != i){
                swap(tree,max, i);
                heapify(tree,n,max);
            }
        }
        public static void swap(int[]tree,int i,int j){
            int temp = tree[i];
            tree[i] = tree[j];
            tree[j] = temp;
        }
    }
    
    

    验证

    请输入你要排序的数字的个数
    10
    7
    4
    6
    0
    8
    1
    5
    9
    2
    3
    [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    
    Process finished with exit code 0
    

    2.最大堆
    这里我们只需要在上面代码出改变一处位置就OK,就是我们在进行下沉操作的时候,判断父亲结点与孩子结点的值的大小就可以。

    package org.westos.demo;
    
    
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class HeapSort3 {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入你要排序的数字的个数");
            int n = sc.nextInt();
            int[] tree = new int[n];
            for (int i = 0; i < tree.length; i++) {
                tree[i] = sc.nextInt();
            }
            heap_sort(tree,tree.length);
            System.out.println(Arrays.toString(tree));
        }
        //我们在建好堆的基础之上,进行排序,每次排完序之后要记得重新进行下沉操作,从而使得堆满足最大(小)堆的特性
        public static void heap_sort(int[]tree,int n){
            build_heap(tree,n);
            for (int i = n-1; i >= 0; i--) {
                swap(tree,i,0);
                heapify(tree,i,0);
            }
        }
    
        /**
         *
         * @param tree 要排序的数组
         * @param n    数组的长度
         * 从最后一个非叶子结点从后向前进行建堆,这里我们使用的是Floyd建堆算法
         */
        public static void build_heap(int[]tree,int n){
            int last_node = n - 1;
            int parent = (last_node - 1)/2;
            for (int i = parent;i >= 0;i--){
                heapify(tree,n,i);
            }
        }
    
        /**
         *
         * @param tree 要排序的数组
         * @param n    数组的长度
         * @param i    表示第i个节点
         * 这里我们对元素进行下沉操作
         */
        public static void heapify(int[]tree,int n,int i){
            if(i >= n){
                return;
            }
            int c1 = 2 * i +1;//左孩子结点
            int c2 = 2 * i +2;//右孩子结点
            int max = i;//父亲结点
            //下面就是判断父亲结点和孩子结点的大小,从而进行下沉操作
            if (c1 < n && tree[max] < tree[c1]){//这里得加上c1 < n 防止越界
                max = c1;
            }
            if (c2 < n && tree[max] < tree[c2]){//这里得加上c2 < n 防止越界
                max = c2;
            }
            if (max != i){
                swap(tree,max, i);
                heapify(tree,n,max);
            }
        }
        public static void swap(int[]tree,int i,int j){
            int temp = tree[i];
            tree[i] = tree[j];
            tree[j] = temp;
        }
    }
    
    

    测试:

    请输入你要排序的数字的个数
    10
    7
    4
    6
    0
    8
    1
    5
    9
    2
    3
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    
    Process finished with exit code 0
    

    四、总结

    在刚开始学完堆排序之后,我只是简单的懂了其中的原理,但是当我真正用代码进行实现的时候,才发现自己遇见了很大的问题,虽然每一步的流程图都可以画出来,但是代码还是不知道怎么实现。首先堆排序利用了二叉树,那么首先就要对二叉树了解,另外还有里面的相关结点的计算,接下来就是按照每一步的流程用代码实现,这里面还有好几处边界问题也应该注意,另外,如果不知道思路大概画一遍就可以更加深入的了解其中的原理。

    展开全文
  • 我们在学习 Java 的过程中肯定会遇到对数组进行升序或降序等排序问题,本节主要介绍如何实现 Java 数组的升序和降序Java 语言使用 Arrays 类提供的 sort() 方法来对数组进行排序。升序使用 java.util.Arrays 类中...

    我们在学习 Java 的过程中肯定会遇到对数组进行升序或降序等排序问题,本节主要介绍如何实现 Java 数组的升序和降序。Java 语言使用 Arrays 类提供的 sort() 方法来对数组进行排序。

    升序

    使用 java.util.Arrays 类中的 sort() 方法对数组进行升序分为以下两步:

    导入 java.util.Arrays 包。

    使用 Arrays.sort(数组名) 语法对数组进行排序,排序规则是从小到大,即升序。

    假设在数组 scores 中存放了 5 名学生的成绩,现在要实现从低到高排列的功能。在这里使用 Arrays.sort() 方法来实现,具体代码如下:

    public static void main(String[] args) {

    // 定义含有5个元素的数组

    double[] scores = new double[] { 78, 45, 85, 97, 87 };

    System.out.println("排序前数组内容如下:");

    // 对scores数组进行循环遍历

    for (int i = 0; i < scores.length; i++) {

    System.out.print(scores[i] + "\t");

    }

    System.out.println("\n排序后的数组内容如下:");

    // 对数组进行排序

    Arrays.sort(scores);

    // 遍历排序后的数组

    for (int j = 0; j < scores.length; j++) {

    System.out.print(scores[j] + "\t");

    }

    }

    如上述代码所示,要对一个数组进行升序排列,只需要调用 Arrays.sort() 方法即可。运行后的输出结果如下所示。

    排序前数组内容如下:

    78.0 45.0 85.0 97.0 87.0

    排序后的数组内容如下:

    45.0 78.0 85.0 87.0 97.0

    降序

    在 Java 语言中使用 sort 实现降序有两种方法,简单了解即可。

    1)利用 Collections.reverseOrder() 方法(Collections 是一个包装类。大家可以学习《Java Collections类》一节详细了解):

    public static void main(String[] args) {

    Integer[] a = { 9, 8, 7, 2, 3, 4, 1, 0, 6, 5 }; // 数组类型为Integer

    Arrays.sort(a, Collections.reverseOrder());

    for (int arr : a) {

    System.out.print(arr + " ");

    }

    }

    输出结果如下:

    9 8 7 6 5 4 3 2 1 0

    2)实现 Comparator 接口的复写 compare() 方法,代码如下:

    public class Test {

    public static void main(String[] args) {

    /*

    * 注意,要想改变默认的排列顺序,不能使用基本类型(int,double,char)而要使用它们对应的类

    */

    Integer[] a = { 9, 8, 7, 2, 3, 4, 1, 0, 6, 5 };

    // 定义一个自定义类MyComparator的对象

    Comparator cmp = new MyComparator();

    Arrays.sort(a, cmp);

    for (int arr : a) {

    System.out.print(arr + " ");

    }

    }

    }

    // 实现Comparator接口

    class MyComparator implements Comparator {

    @Override

    public int compare(Integer o1, Integer o2) {

    /*

    * 如果o1小于o2,我们就返回正值,如果o1大于o2我们就返回负值, 这样颠倒一下,就可以实现降序排序了,反之即可自定义升序排序了

    */

    return o2 - o1;

    }

    }

    输出结果如下所示。

    9 8 7 6 5 4 3 2 1 0

    注意:使用以上两种方法时,数组必须是包装类型,否则会编译不通过。

    在 Java 中实现数组排序的方式很多,除了利用以上的几种方法外,还可以编写自定义方法来实现自己的排序算法,有兴趣的读者可以尝试编写。

    展开全文
  • Java sort()数组排序(升序和降序)我们在学习 Java 的过程中肯定会遇到对数组进行升序或降序等排序问题,本节主要介绍如何实现 Java 数组的升序和降序Java 语言使用 Arrays 类提供的 sort() 方法来对数组进行排序。...

    Java sort()数组排序(升序和降序)

    我们在学习 Java 的过程中肯定会遇到对数组进行升序或降序等排序问题,本节主要介绍如何实现 Java 数组的升序和降序。Java 语言使用 Arrays 类提供的 sort() 方法来对数组进行排序。

    升序

    使用 java.util.Arrays 类中的 sort() 方法对数组进行升序分为以下两步:

    导入 java.util.Arrays 包。

    使用 Arrays.sort(数组名) 语法对数组进行排序,排序规则是从小到大,即升序。

    假设在数组 scores 中存放了 5 名学生的成绩,现在要实现从低到高排列的功能。在这里使用 Arrays.sort() 方法来实现,代码如下:

    public static void main(String[] args) {

    // 定义含有5个元素的数组

    double[] scores = new double[] { 78, 45, 85, 97, 87 };

    System.out.println("排序前数组内容如下:");

    // 对scores数组进行循环遍历

    for (int i = 0; i < scores.length; i++) {

    System.out.print(scores[i] + "\t");

    }

    System.out.println("\n排序后的数组内容如下:");

    // 对数组进行排序

    Arrays.sort(scores);

    // 遍历排序后的数组

    for (int j = 0; j < scores.length; j++) {

    System.out.print(scores[j] + "\t");

    }

    }

    如上述代码所示,要对一个数组进行升序排列,只需要调用 Arrays.sort() 方法即可。运行后的输出结果:

    排序前数组内容如下:

    78.0 45.0 85.0 97.0 87.0

    排序后的数组内容如下:

    45.0 78.0 85.0 87.0 97.0

    降序

    在 Java 语言中使用 sort 实现降序有两种方法,简单了解即可。

    1)利用 Collections.reverseOrder() 方法(Collections 是一个包装类。大家可以学习《Java Collections类》一节详细了解):

    public static void main(String[] args) {

    Integer[] a = { 9, 8, 7, 2, 3, 4, 1, 0, 6, 5 }; // 数组类型为Integer

    Arrays.sort(a, Collections.reverseOrder());

    for (int arr : a) {

    System.out.print(arr + " ");

    }

    }

    输出结果如下:

    9 8 7 6 5 4 3 2 1 0

    2)实现 Comparator 接口的复写 compare() 方法,代码如下:

    public class Test {

    public static void main(String[] args) {

    /*

    * 注意,要想改变默认的排列顺序,不能使用基本类型(int,double,char)而要使用它们对应的类

    */

    Integer[] a = { 9, 8, 7, 2, 3, 4, 1, 0, 6, 5 };

    // 定义一个自定义类MyComparator的对象

    Comparator cmp = new MyComparator();

    Arrays.sort(a, cmp);

    for (int arr : a) {

    System.out.print(arr + " ");

    }

    }

    }

    // 实现Comparator接口

    class MyComparator implements Comparator {

    @Override

    public int compare(Integer o1, Integer o2) {

    /*

    * 如果o1小于o2,我们就返回正值,如果o1大于o2我们就返回负值, 这样颠倒一下,就可以实现降序排序了,反之即可自定义升序排序了

    */

    return o2 - o1;

    }

    }

    输出结果:

    9 8 7 6 5 4 3 2 1 0

    注意:使用以上两种方法时,数组必须是包装类型,否则会编译不通过。

    在 Java 中实现数组排序的方式很多,除了利用以上的几种方法外,还可以编写自定义方法来实现自己的排序算法。

    展开全文
  • 我在java中执行升序和降序编号,这是我的代码:System.out.print("Enter How Many Inputs: ");int num1 = Integer.parseInt(in.readLine());int arr[] = new int[num1];for (int i = 0; iSystem.out.print("Enter ...

    我在

    java中执行升序和降序编号,这是我的代码:

    System.out.print("Enter How Many Inputs: ");

    int num1 = Integer.parseInt(in.readLine());

    int arr[] = new int[num1];

    for (int i = 0; i

    System.out.print("Enter Value #" + (i + 1) + ":");

    arr[i] =Integer.parseInt(in.readLine());

    }

    System.out.print("Numbers in Ascending Order:" );

    for(int i = 0; i < arr.length; i++) {

    Arrays.sort(arr);

    System.out.print( " " +arr[i]);

    }

    System.out.println(" ");

    System.out.print("Numbers in Descending Order: " );

    目前,代码生成以下内容:

    Enter How Many Inputs: 5

    Enter Value #1:3

    Enter Value #2:5

    Enter Value #3:6

    Enter Value #4:11

    Enter Value #5:2

    Numbers in Ascending Order: 2 3 5 6 11

    Numbers in Descending Order:

    因此,Arrays.sort(arr)调用似乎有效 – 但我正在寻找一种类似的简单方法来提供降序排序,并且无法在文档中找到它.有任何想法吗?

    展开全文
  • 我们在学习 Java 的过程中肯定会遇到对数组进行升序或降序等排序问题,本节主要介绍如何实现 Java 数组的升序和降序Java 语言使用 Arrays 类提供的 sort() 方法来对数组进行排序。升序使用 java.util.Arrays 类中...
  • 我们在学习 Java 的过程中肯定会遇到对数组进行升序或降序等排序问题,本节主要介绍如何实现 Java 数组的升序和降序Java 语言使用 Arrays 类提供的 sort() 方法来对数组进行排序。升序使用 java.util.Arrays 类中...
  • 主要介绍了JAVA基于Arrays.sort()实现数组升序和降序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
  • 我们在学习Java的过程中肯定会遇到对数组进行升序或降序等排序问题,本节主要介绍如何实现 Java 数组的升序和降序Java 语言使用 Arrays 类提供的 sort() 方法来对数组进行排序。升序使用 java.util.Arrays 类中的 ...
  • Java 用 sort 实现对数组的升序和降序排序一、升序二、降序 一、升序 使用 java.util.Arrays 类中的 sort() 方法对数组进行升序分为以下两步: 导入 java.util.Arrays 包。 使用 Arrays.sort(数组名) 语法对数组...
  • Java中的升序和降序

    2018-01-13 18:53:00
    package ah; import java.util.Arrays; import java.util.Collections; import java.util.Comparator;...import java.util.List;...// Java降序不容易 ...public class TestJava升序降序 { public st...
  • Java中Arrays.sort()自定义数组的升序和降序排序

    万次阅读 多人点赞 2018-04-13 23:01:19
    Java学习中会遇到对数组进行升序或者降序排序的问题,其实Java语言提供给我们Array.sort(int [] arr)对数组进行升序排列,代码如下:package peng; import java.util.Arrays;  public class Testexample { ...
  • 数组升序降序 package com.itcast.cn; import java.sql.Connection; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; public class demo1 { public static void ...
  • 直接插入算法之升序降序java实现 /* * 直接排序算法 * 从小到大 * 思想:扫描N-1次 每次扫描 前一位比较 temp不变 被比较的数移动位置 * 升序 */ public static int[] straightSortAsc(int ...
  • TreeMap 升序|降序排列import java.util.Comparator;import java.util.TreeMap;public class Main {public static void main(String[] args) {TreeMap map1 = new TreeMap(); //默认的TreeMap升序排列TreeMap map2= ...
  • 最长升序和降序子序列; import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class 作业题 { static class Position { public int x; public int y; public P
  • java升序和降序排序方法及原理

    千次阅读 2019-08-28 17:23:50
    //排序升序 sort(sortArr); print(sortArr); //排序转置 reverse(sortArr); print(sortArr); } public static void sortArr(int arr[]) { System.out.println("原始数组:"); for (int i = 0; i ; i++) {...
  • Arrays的sort方法可以直接对数据进行升序和降序排列。本人小白,前段时间刚学到sort方法时,看到Arrays操作数组只能升序,使用了很多奇怪的办法来进行降序。例如: import java.util.Arrays; public class ...
  • java中对数组进行排序使用Array.sort() 这个默认是升序@Testpublic void index4(){int scores[] = new int[]{1,2,3,89,4};Arrays.sort(scores);for (int i:scores) {System.out.println(i);}}如果想降序怎么办呢?...
  • 总结下java对象升序和降序

    千次阅读 2018-10-18 14:02:49
    //如果想降序,即从大到小排序,那么比较时,如果o1>o2,那么要对比默认的规则 ,反过来 ,让大的一方去左边(意思是你大反而是小,返回-1,往前站,就形成了左--->右,大---小) } else if (dt1.getTime() ()) { ...
  • 1 int[] x={1,6,4,8,6,9,12,32,76,34,23};...升序: 1 Arrays.sort(x); 降序: 1 resort(x); 2 public int[] resort(int[] num){ 3 Arrays.sort(num); 4 int[] resort=new int[num.length]; ...
  • import java.util.Arrays; //冒泡排序 public class Test01 { public static void sort(int[] a){//创建排序的方法 int temp=0;//临时变量 for (int i = 0; i < a.length-1; i++) {//外层循环,相当于排序的...
  • 最长升序和降序子序列; import java.util.Scanner; /*升序  * 它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度。要准备几套这样的导弹拦截系统  * 能有多少个最长降序子...
  • 最长升序和降序子序列; import java.util.Scanner; public class 分分钟的碎碎念 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int arr...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 504
精华内容 201
关键字:

升序和降序java

java 订阅