精华内容
下载资源
问答
  • 作者:失控的的狗蛋~来源:CSDN排序算法待排序的元素需要实现 JAVA 的 Comparable 接口,该接口有 compareTo() 方法,可以用它来判断两个元素的大小关系。使用辅助函数 less() 和 swap() 来进行比较和交换的操作,...

    作者:失控的的狗蛋~

    来源:CSDN

    排序算法

    待排序的元素需要实现 JAVA 的 Comparable 接口,该接口有 compareTo() 方法,可以用它来判断两个元素的大小关系。

    使用辅助函数 less() 和 swap() 来进行比较和交换的操作,使得代码的可读性和可移植性更好。

    敲黑板:排序算法的成本模型是比较和交换的次数,也是衡量排序算法的好坏的方式。

    选择排序(Selection Sort)

    从数组中选择最小元素,将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素,将它与数组的第二个元素交换位置。不断进行这样的操作,直到将整个数组排序。

    选择排序需要 ~N2/2 次比较和 ~N 次交换,它的运行时间与输入无关,这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

    看一张动图(动图网站链接在下面大家没事可以去看看,那个网站有各种算法可以模拟过程让你更直观的理解算法)

    f09250804e2cafe61a6044276bf49f3a.png

    冒泡排序(Bubble Sort)

    从左到右不断交换相邻逆序的元素,在一轮的循环之后,可以让未排序的最大元素上浮到右侧。

    在一轮循环中,如果没有发生交换,那么说明数组已经是有序的,此时可以直接退出。

    9281f6a12eeb880219ba431180dc8611.png

    插入排序(Insertion Sort)

    每次都将当前元素插入到左侧已经排序的数组中,使得插入之后左侧数组依然有序。

    对于数组 {3, 5, 2, 4, 1},它具有以下逆序:(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1),插入排序每次只能交换相邻元素,令逆序数量减少 1,因此插入排序需要交换的次数为逆序数量。

    插入排序的时间复杂度取决于数组的初始顺序,如果数组已经部分有序了,那么逆序较少,需要的交换次数也就较少,时间复杂度较低。

    平均情况下插入排序需要 ~N2/4 比较以及 ~N2/4 次交换;

    最坏的情况下需要 ~N2/2 比较以及 ~N2/2 次交换,最坏的情况是数组是倒序的;

    最好的情况下需要 N-1 次比较和 0 次交换,最好的情况就是数组已经有序了

    c700ea65f7a237dce4e982549c94a5fd.png

    希尔排序(Shell Sort)

    对于大规模的数组,插入排序很慢,因为它只能交换相邻的元素,每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性,它通过交换不相邻的元素,每次可以将逆序数量减少大于 1。

    希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h,最后令 h=1,就可以使得整个数组是有序的。

    9608540f6da24efd29366805a7fde2ef.png

    归并排序(Merge Sort)

    归并排序的思想是将数组分成两部分,分别进行排序,然后归并起来。

    1. 归并方法

    归并方法将数组中两个已经排序的部分归并成一个。

    866631f86046bf80d43e343303f7eb5b.png

    2. 自顶向下归并排序

    将一个大数组分成两个小数组去求解。

    因为每次都将问题对半分成两个子问题,这种对半分的算法复杂度一般为 O(NlogN)。

    dd22d2b22625fffe304165221d865885.png

    3. 自底向上归并排序

    先归并那些微型数组,然后成对归并得到的微型数组。

    8885ee74f8c7385354382162826113f8.png

    快速排序(Quick Sort)

    快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

    快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

    从数列中挑出一个元素,称为 “基准”(pivot);

    重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

    递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    9622fa0b98f3d4d5c91fe941e1dc2ae4.png

    排序算法比较

    1988925a0319315bd1506290dbdf22c7.png

    Java 的排序算法实现

    Java 主要排序方法为 java.util.Arrays.sort(),对于原始数据类型使用三向切分的快速排序,对于引用类型使用归并排序。

    展开全文
  • Java排序算法

    2019-11-06 22:15:53
    Java排序算法 排序算法(二) 排序算法(三) 排序算法(四) 排序算法(五)-双调排序 排序算法(六)-TimSort 排序算法(七)-双轴快速排序 排序算法(八)-三路快速排序 排序算法(九)-Java源码中的...
    展开全文
  • Java排序算法实现方式(算法思路 过程动图)

    千次阅读 多人点赞 2019-10-15 16:33:07
    排序的元素需要实现 Java 的 Comparable 接口,该接口有 compareTo() 方法,可以用它来判断两个元素的大小关系。 使用辅助函数 less() 和 swap() 来进行比较和交换的操作,使得代码的可读性和可移植性更好。 敲...

     排序算法

    待排序的元素需要实现 Java 的 Comparable 接口,该接口有 compareTo() 方法,可以用它来判断两个元素的大小关系。

    使用辅助函数 less() 和 swap() 来进行比较和交换的操作,使得代码的可读性和可移植性更好。

    敲黑板:排序算法的成本模型是比较和交换的次数,也是衡量排序算法的好坏的方式。

     

    • 选择排序(Selection Sort)

        从数组中选择最小元素,将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素,将它与数组的第二个元素交换位置。不断进行这样的操作,直到将整个数组排序。

    选择排序需要 ~N2/2 次比较和 ~N 次交换,它的运行时间与输入无关,这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

     看一张动图(动图网站链接在下面大家没事可以去看看,那个网站有各种算法可以模拟过程让你更直观的理解算法

     

    • 冒泡排序(Bubble Sort)

        从左到右不断交换相邻逆序的元素,在一轮的循环之后,可以让未排序的最大元素上浮到右侧。

    在一轮循环中,如果没有发生交换,那么说明数组已经是有序的,此时可以直接退出。

     

    • 插入排序(Insertion Sort)

        每次都将当前元素插入到左侧已经排序的数组中,使得插入之后左侧数组依然有序。

    对于数组 {3, 5, 2, 4, 1},它具有以下逆序:(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1),插入排序每次只能交换相邻元素,令逆序数量减少 1,因此插入排序需要交换的次数为逆序数量。

    插入排序的时间复杂度取决于数组的初始顺序,如果数组已经部分有序了,那么逆序较少,需要的交换次数也就较少,时间复杂度较低。

    • 平均情况下插入排序需要 ~N2/4 比较以及 ~N2/4 次交换;
    • 最坏的情况下需要 ~N2/2 比较以及 ~N2/2 次交换,最坏的情况是数组是倒序的;
    • 最好的情况下需要 N-1 次比较和 0 次交换,最好的情况就是数组已经有序了

     

     

     

    • 希尔排序(Shell Sort)

    对于大规模的数组,插入排序很慢,因为它只能交换相邻的元素,每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性,它通过交换不相邻的元素,每次可以将逆序数量减少大于 1。

    希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h,最后令 h=1,就可以使得整个数组是有序的。

     

     

    • 归并排序(Merge Sort)

         归并排序的思想是将数组分成两部分,分别进行排序,然后归并起来。

       1. 归并方法

           归并方法将数组中两个已经排序的部分归并成一个。

    public abstract class MergeSort<T extends Comparable<T>> extends Sort<T> {
    
        protected T[] aux;
    
    
        protected void merge(T[] nums, int l, int m, int h) {
    
            int i = l, j = m + 1;
    
            for (int k = l; k <= h; k++) {
                aux[k] = nums[k]; // 将数据复制到辅助数组
            }
    
            for (int k = l; k <= h; k++) {
                if (i > m) {
                    nums[k] = aux[j++];
    
                } else if (j > h) {
                    nums[k] = aux[i++];
    
                } else if (aux[i].compareTo(aux[j]) <= 0) {
                    nums[k] = aux[i++]; // 先进行这一步,保证稳定性
    
                } else {
                    nums[k] = aux[j++];
                }
            }
        }
    }
    
    

       2. 自顶向下归并排序

          将一个大数组分成两个小数组去求解。

    因为每次都将问题对半分成两个子问题,这种对半分的算法复杂度一般为 O(NlogN)。

    public class Up2DownMergeSort<T extends Comparable<T>> extends MergeSort<T> {
    
        @Override
        public void sort(T[] nums) {
            aux = (T[]) new Comparable[nums.length];
            sort(nums, 0, nums.length - 1);
        }
    
        private void sort(T[] nums, int l, int h) {
            if (h <= l) {
                return;
            }
            int mid = l + (h - l) / 2;
            sort(nums, l, mid);
            sort(nums, mid + 1, h);
            merge(nums, l, mid, h);
        }
    }
    

        3. 自底向上归并排序

          先归并那些微型数组,然后成对归并得到的微型数组。

    public class Down2UpMergeSort<T extends Comparable<T>> extends MergeSort<T> {
    
        @Override
        public void sort(T[] nums) {
    
            int N = nums.length;
            aux = (T[]) new Comparable[N];
    
            for (int sz = 1; sz < N; sz += sz) {
                for (int lo = 0; lo < N - sz; lo += sz + sz) {
                    merge(nums, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
                }
            }
        }
    }
    
    •  快速排序(Quick Sort)

           快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

    快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

    • 从数列中挑出一个元素,称为 “基准”(pivot);
    • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
    • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

     排序算法比较

     

    Java 的排序算法实现

    Java 主要排序方法为 java.util.Arrays.sort(),对于原始数据类型使用三向切分的快速排序,对于引用类型使用归并排序。

     

    ps:动图网址:https://visualgo.net

    展开全文
  • java api里面实现的排序接口有Collection.sort和TreeMap,sort原理是归并排序,treeMap是红黑树排序。package com.study.collection;import java.util.*;/*** Created by DELL on 2016-5-12.*/public class Sort {/*...

    算法我不懂,所以直接用现成的东西比较容易。

    java api里面实现的排序接口有Collection.sort和TreeMap,sort原理是归并排序,treeMap是红黑树排序。

    package com.study.collection;

    import java.util.*;

    /**

    * Created by DELL on 2016-5-12.

    */

    public class Sort {

    /**

    * treeMap排序

    */

    public static void treeMapTest(){

    /**

    * treeMap排序,排序原理是红黑树排序

    * 如果没有指定排序器,默认按照key的string的升序排列,

    * string会先转换成char,如果是中文对转换成中文的unicode编码,把编码的升序排列

    * 建议最好指定排序器,否则有中文时会有问题

    */

    Map treeMap = new TreeMap(new CollatorComparator());

    treeMap.put("zbc","zbc");

    treeMap.put("你好","你好");

    treeMap.put("111","111");

    treeMap.put("北京","北京");

    treeMap.put("厦门","厦门");

    treeMap.put("碑海","碑海");

    System.out.println(treeMap);

    }

    /**

    *Collection排序,排序原理归并排序

    */

    public static void ListStortTest(){

    List list = new ArrayList();

    list.add("123");

    list.add("132");

    list.add("abc");

    list.add("acc");

    list.add("碑海");

    list.add("厦门");

    list.add("北京");

    //排序时如果list的元素没有实现Comparable接口,则必须传入排序器

    Collections.sort(list,new CollatorComparator());

    System.out.println(list);

    Collections.reverse(list);

    System.out.println("逆序"+list);

    }

    /**

    * 实现Comparable接口排序

    *Collection排序,排序原理归并排序

    */

    public static void listSortBeanTest(){

    List list = new ArrayList();

    list.add(new SortBean("123"));

    list.add(new SortBean("132"));

    list.add(new SortBean("abc"));

    list.add(new SortBean("acc"));

    list.add(new SortBean("碑海"));

    list.add(new SortBean("厦门"));

    list.add(new SortBean("北京"));

    //排序元素list的元素没有实现Comparable接口,如果传入排序器,则bean的Comparable接口无效

    Collections.sort(list/*,new SortBeanComparator()*/);

    System.out.println(list);

    }

    public static void main(String[] args){

    //Sort.treeMapTest();

    // Sort.ListStortTest();

    Sort.listSortBeanTest();

    }

    }

    package com.study.collection;

    import java.text.CollationKey;

    import java.text.Collator;

    import java.util.Comparator;

    import java.util.Locale;

    /**

    * 排序器

    */

    public class CollatorComparator implements Comparator {

    //本地化语言

    Collator collator = Collator.getInstance(Locale.SIMPLIFIED_CHINESE);

    /**

    * 重写这个方法,使用简体中文排序

    * @param el1

    * @param el2

    * @return

    */

    public int compare(Object el1,Object el2){

    CollationKey key1 = collator.getCollationKey(el1.toString());

    CollationKey key2 = collator.getCollationKey(el2.toString());

    return key1.compareTo(key2);

    }

    }

    package com.study.collection;

    import java.text.Collator;

    import java.util.Comparator;

    import java.util.Locale;

    /**

    * Created by DELL on 2016-5-12.

    */

    public class SortBean implements Comparable{

    private String content;

    Collator collator = Collator.getInstance(Locale.SIMPLIFIED_CHINESE);

    public SortBean(String content){

    this.content = content;

    }

    public String getContent() {

    return content;

    }

    public void setContent(String content) {

    this.content = content;

    }

    @Override

    public int compareTo(SortBean o) {

    return collator.compare(this.getContent(),o.getContent());

    }

    @Override

    public String toString() {

    return this.content;

    }

    }

    展开全文
  • 作者:失控的的狗蛋~来源:CSDN 排序算法待排序的元素需要实现 Java 的 Comparable 接口,该接口有 compareTo() 方法,可以用它来判断两个元素的大小关系。使用辅助函数 less() 和 swap() 来进行比较和交换的操作,...
  • java排序算法汇总

    2010-05-13 18:32:00
    这段时间正在找工作,研究了一下算法。我是做web开发的,但是比较喜欢...我的邮箱:zlljsf@gmail.com 排序算法超类:/** * 排序算法超类 * 所有排序序列中元素必须实现java.lang.Comparable接口 * @author Liangliang
  • 1,对元素进行排列时,元素之间需要进行比较,因此需要实现Comparable...2,InsertionSortArray.java 类实现了从小到大顺序以插入排序的方式对数据进行排序。3,insertionSort方法负责对每一个元素进行排序,insertI...
  • 01归并排序算法JAVA实现 package Utils.Sort; /**归并排序,要求待排序的数组必须实现Comparable接口 */ public class MergeSort implements SortStrategy { private Comparable[] bridge; /** 利用...
  • java提供了两个排序用的接口Comparable和Comparator,一般情况下使用区别如下: Comparable 接口用于类的固定排序方式上面,比如类实现Comparable接口,实现compareTo方法, 做为类默认排序实现。 Comprator接口...
  • java排序接口

    2016-05-20 15:10:00
    java api里面实现的排序接口有Collection.sort和TreeMap,sort原理是归并排序,treeMap是红黑树排序。 package com.study.collection; import java.util.*; /** * Created by DELL on 2016-5-12. */ ...
  • Java常见排序算法

    2018-05-08 21:44:07
    首先定义一个排序接口。ISortNumber.javapackage demo.secapi.net; /** * Created by MXi4oyu on 2018/5/6. */ public interface ISortNumber { /** * * 对整型数组按升序排序 * */ public int[] sortAS....
  • [java]排序算法总结

    2016-04-20 09:12:36
    java写了一个排序算法的总结,可初步用来比较排序算法的效率 使用代理模式,在排序开始和结束时记录机器时间,计算耗时 1. 定义排序接口 public interface sort { void dosort(int[] array,int beg,int end); ...
  • 1、冒泡排序public class Bubble_sort {/*** 公共冒泡排序接口* @param arr 带排序数组*/public static void sort(int[] arr) {if (arr == null) return;int len = arr.length;for (int j = len - 1; j > 0; j--)...
  • 通过实现ComParator接口,并且对Compare函数进行重写,自定义排序规则实现对ArrayList中对象的排序。。Student类定义:通过右键-》source-》自动生成Set和get方法package first;import java.util.Comparator;import ...
  • 排序的元素需要实现 Java 的 Comparable 接口,该接口有 compareTo() 方法,可以用它来判断两个元素的大小关系。 使用辅助函数 less() 和 swap() 来进行比较和交换的操作,使得代码的可读性和可移植性更好。 敲...
  • 快速排序算法Java实现

    2019-11-21 15:32:04
    快速排序算法Java实现 快速排序是运用广泛的一种排序算法,其时间复杂度是nlog(n),用到了分治的思想,以下是快排的Java实现。 首先定义一个接口Sorter,此接口的第一个sort方法接收一个list数组,该数组中的对象...
  • /** * 插入排序及其变体 * * List可转化为数组进行排序 * Object数组中的元素必须实现Comparable接口,即元素必须是可比的 */ public class InsertSort { /** * 直接插入排序 */ public static void insertSort...
  • java排序算法实现-多种排序参考 import java.util.Comparator; /** * 排序器接口(策略模式: 将算法封装到具有共同接口的独立的类中使得它们可以相互替换) * @author nnngu * */ public interface Sorter { /*...
  • 在PAT Basic Level的真题中,有” ...由此可见,在相同的情况下,实现Comparable接口排序算法效率更高。但是它的本质原因,我现在还不清楚。 当然,我的代码待改进的地方还很多,待续。
  • 聊聊 JDK 源码,聊聊算法。 本场 Chat 主要内容: 什么是选择问题 比较(Comparable)能力 ...String 源码中的排序算法 String 存储结构 String 比较方法源码解析 常见字符 ASCII 码 弊端分析总结 ...
  • JAVA内部排序算法汇总

    2008-04-02 17:46:06
    为了总结学习资料,特此整理一下...定义排序接口:Sort public interface Sort { int[] datas = {0,12,32,45,2,13,57,29,11,34,21,42,15,90}; int length =datas.length; public void sort(); public void publish(); }
  • package Utils.Sort;/***快速排序,要求待排序的数组必须实现Comparable接口*/public class ...//当元素数大于此值时采用快速排序/***利用快速排序算法对数组obj进行排序,要求待排序的数组必须实现了Comparable...
  • Java实现冒泡排序算法

    2016-06-01 14:48:40
    冒泡排序几乎是个程序员都写得出来,但是面试的时候如何写一个逼格高的冒泡排序却不是每个人都能做到,下面... * 排序接口 * */ public interface Sorter { /** * 排序 * @param list 待排序的数组 */ public
  • Collections.sort()Java排序可以用Collections.sort() 排序函数实现。用Collections.sort方法对list排序有两种方法:第一种是list中的对象实现Comparable接口,如下:/*** 根据order对User排序*/public class User...
  • java中常用的排序算法

    2019-09-14 20:12:33
    平时的工作中,如果遇到...但是常用的排序算法我们也有必要自己理解消化,作为锻炼思维的一种方式,下面我把自己实现的常用算法写出来,供大家参考学习。支持纯数组排序,也支持任意实现了Comparable接口的类的排序...
  • 叨叨两句 插,昨晚忘发了。今早补上。 Java编程基本思路 项目需求 需求分析 相关类/对象/方法/属性 核心逻辑 ...KeyListener接口 ...冒泡排序算法最终版 package com.test; import java.lang.reflect.Arr...
  • 一般多用于单线程环境下,它实现了Serializable接口,因此它支持序列化,能够通过序列化传输,但是实际上java类库中的大部分类都是实现了这个接口。实现了RandomAccess接口,支持快速随机访问,但...
  • 七种排序算法JAVA实现最近在找工作时很多面试官都会问到排序算法的实现,所以趁着周末有时间就来总结一下七种排序算法实现。 算法的实现我使用的是java语言,其中为了增强算法的可复用性,我使用了泛型这一特性...
  • 排序-Java系统库的排序算法

    千次阅读 2016-01-24 19:59:07
    - 一个适用于所有实现了Comparable接口的数据类型的排序方法; - 一个适用于实现了比较器Comparator的数据类型的排序方法。Java的系统程序员选择对原始数据类型使用(三向切分的)快速排序,对引用类型使用归并

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,241
精华内容 496
关键字:

java排序算法接口

java 订阅