Java自定义快排的几种方式
2021/4/13 12:55:16
本文主要是介绍Java自定义快排的几种方式,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
方法一、通过Arrays.sort来实现
Arrays类中有sort()方法,是Arrays类的静态方法,对数组排序时可以很方便的使用
其中一种使用形式为
public static <T> void sort(T[] a,int fromIndex, int toIndex, Comparator<? super T> c)
通过修改comparator,我们就可以对包括基本数据类型、字符串、类等按照我们自己的需求进行排序。
举一个例子,给定一组非负整数 nums
,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数(leetcode第179题)。在这题中,其中一种考虑方法就是先对数组进行排序,按照数值大的数放在高位。于是我们可以比较输入数组的每个元素的最高位,最高位相同的时候比较次高位,以此类推,完成排序。更简单的方法是将其拼接后比较拼接后的数据。例如,比较45,44谁放前面可以比较4544和4445的大小。
(1)创建类实现Comparator接口
public class Solution1 { public String largestNumber(int[] nums) { int n = nums.length; Integer[] numsArr = new Integer[n]; for(int i = 0;i < n; i++) { numsArr[i] = nums[i]; } MyComparator comparator = new MyComparator(); Arrays.sort(numsArr,comparator); if(numsArr[0]==0) { return "0"; } StringBuilder ret = new StringBuilder(); for(int num:numsArr) { ret.append(num); } return ret.toString(); } } class MyComparator implements Comparator<Integer>{ @Override public int compare(Integer o1, Integer o2) { long s1 = 10, s2 = 10; while (s1 <= o1) { s1 *= 10; } while (s2 <= o2) { s2 *= 10; } return (int) (-s2 * o1 - o2 + s1 * o2 + o1); } }
(2)匿名内部类
该方法只使用一次,却要单独写成一个类,这显得很不方便,这种情况下就可以使用匿名内部类来简化。
public class Solution2 { public String largestNumber(int[] nums) { int n = nums.length; Integer[] numsArr = new Integer[n]; for(int i = 0;i < n; i++) { numsArr[i] = nums[i]; } /* *也可以写成以下格式 *Comparator<Integer> comparator = new Comparator<Integer>() { * @Override * public int compare(Integer o1, Integer o2) { * long s1 = 10, s2 = 10; * while (s1 <= o1) { * s1 *= 10; * } * while (s2 <= o2) { * s2 *= 10; * } * return (int) (-s2 * o1 - o2 + s1 * o2 + o1); * } * }; * Arrays.sort(numsArr,comparator); * */ Arrays.sort(numsArr,new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { long s1 = 10, s2 = 10; while (s1 <= o1) { s1 *= 10; } while (s2 <= o2) { s2 *= 10; } return (int) (-s2 * o1 - o2 + s1 * o2 + o1); } }); if(numsArr[0]==0) { return "0"; } StringBuilder ret = new StringBuilder(); for(int num:numsArr) { ret.append(num); } return ret.toString(); } }
(3) lambda表达式
在java8中,java开始允许使用Lambda表达式,在Java程序中,我们经常遇到一大堆单方法接口,即一个接口只定义了一个方法。这种情况下无论是内部匿名类还是直接实现这个类,这两种写法都先对繁琐。这种情况下,就可以使用Lambda表达式替换单方接口。
public class Solution3 { public String largestNumber(int[] nums) { int n = nums.length; Integer[] numsArr = new Integer[n]; for(int i = 0;i < n; i++) { numsArr[i] = nums[i]; } Arrays.sort(numsArr,(o1,o2)->{ long s1 = 10, s2 = 10; while (s1 <= o1) { s1 *= 10; } while (s2 <= o2) { s2 *= 10; } return (int) (-s2 * o1 - o2 + s1 * o2 + o1); }); if(numsArr[0]==0) { return "0"; } StringBuilder ret = new StringBuilder(); for(int num:numsArr) { ret.append(num); } return ret.toString(); } }
方法二、通过Collections.sort来实现
Collections.sort()通常使用方法类似于Arrays.sort(),使用
Collections.sort(T[] a, Comparator<? super T> c)
使用时与arrays.sort类似,因此不再赘述。
注:arrays.sort()与Collections.sort()的选择与异同
Arrays.sort()方法,如果数组长度大于等于286且连续性好的话,就用归并排序,如果大于等于286且连续性不好的话就用双轴快速排序。如果长度小于286且大于等于47的话就用双轴快速排序,如果长度小于47的话就用插入排序。
Collections.sort专门给List排序,而Arrays.sort专门给数组进行排序。
这篇关于Java自定义快排的几种方式的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现