佛山企业网站自助建站,淮北发展论坛,仿大前端wordpress主题,郑州企业网站排名一、Arrays.sort()数组排序 Java Arrays中提供了对所有类型的排序。其中主要分为Primitive(8种基本类型)和Object两大类。 基本类型#xff1a;采用调优的快速排序#xff1b; 对象类型#xff1a;采用改进的归并排序。 1、对于基本类型源码分析如下#xff08;以int[]为例…一、Arrays.sort()数组排序 Java Arrays中提供了对所有类型的排序。其中主要分为Primitive(8种基本类型)和Object两大类。 基本类型采用调优的快速排序 对象类型采用改进的归并排序。 1、对于基本类型源码分析如下以int[]为例 Java对Primitiveintfloat等原型数据数组采用快速排序对Object对象数组采用归并排序。对这一区别sun在The Java Tutorial中做出的解释如下 The sort operation uses a slightly optimized merge sort algorithm that is fast and stable: * Fast: It is guaranteed to run in n log(n) time and runs substantially faster on nearly sorted lists. Empirical tests showed it to be as fast as a highly optimized quicksort. A quicksort is generally considered to be faster than a merge sort but isnt stable and doesnt guarantee n log(n) performance. * Stable: It doesnt reorder equal elements. This is important if you sort the same list repeatedly on different attributes. If a user of a mail program sorts the inbox by mailing date and then sorts it by sender, the user naturally expects that the now-contiguous list of messages from a given sender will (still) be sorted by mailing date. This is guaranteed only if the second sort was stable. 也就是说优化的归并排序既快速nlog(n)又稳定。 对于对象的排序稳定性很重要。比如成绩单一开始可能是按人员的学号顺序排好了的现在让我们用成绩排那么你应该保证本来张三在李四前面即使他们成绩相同张三不能跑到李四的后面去。 而快速排序是不稳定的而且最坏情况下的时间复杂度是O(n^2)。 另外对象数组中保存的只是对象的引用这样多次移位并不会造成额外的开销但是对象数组对比较次数一般比较敏感有可能对象的比较比单纯数的比较开销大很多。归并排序在这方面比快速排序做得更好这也是选择它作为对象排序的一个重要原因之一。 排序优化实现中快排和归并都采用递归方式而在递归的底层也就是待排序的数组长度小于7时直接使用冒泡排序而不再递归下去。 分析长度为6的数组冒泡排序总比较次数最多也就12345621次最好情况下只有6次比较。而快排或归并涉及到递归调用等的开销其时间效率在n较小时劣势就凸显了因此这里采用了冒泡排序这也是对快速排序极重要的优化。 源码中的快速排序主要做了以下几个方面的优化 1当待排序的数组中的元素个数较少时源码中的阀值为7采用的是插入排序。尽管插入排序的时间复杂度为0(n^2)但是当数组元素较少时插入排序优于快速排序因为这时快速排序的递归操作影响性能。 2较好的选择了划分元基准元素。能够将数组分成大致两个相等的部分避免出现最坏的情况。例如当数组有序的的情况下选择第一个元素作为划分元将使得算法的时间复杂度达到O(n^2). 源码中选择划分元的方法: 当数组大小为 size7 时 取数组中间元素作为划分元。int nm1;(此方法值得借鉴) 当数组大小 7size40时取首、中、末三个元素中间大小的元素作为划分元。 当数组大小 size40 时 从待排数组中较均匀的选择9个元素选出一个伪中数做为划分元。 3根据划分元 v 形成不变式 v* (v)* (v)* v* 普通的快速排序算法经过一次划分后将划分元排到素组较中间的位置左边的元素小于划分元右边的元素大于划分元而没有将与划分元相等的元素放在其附近这一点在Arrays.sort()中得到了较大的优化。 举例15、93、15、41、6、15、22、7、15、20 因 7size40,所以在15、6、和20 中选择v 15 作为划分元。 经过一次换分后 15、15、7、6、41、20、22、93、15、15. 与划分元相等的元素都移到了素组的两边。 接下来将与划分元相等的元素移到数组中间来形成7、6、15、15、15、15、41、20、22、93. 最后递归对两个区间进行排序[7、6]和[41、20、22、93]. 部分源代码一如下 1 package com.util;2 3 public class ArraysPrimitive {4 private ArraysPrimitive() {}5 6 /**7 * 对指定的 int 型数组按数字升序进行排序。8 */9 public static void sort(int[] a) {10 sort1(a, 0, a.length);11 }12 13 /**14 * 对指定 int 型数组的指定范围按数字升序进行排序。15 */16 public static void sort(int[] a, int fromIndex, int toIndex) {17 rangeCheck(a.length, fromIndex, toIndex);18 sort1(a, fromIndex, toIndex - fromIndex);19 }20 21 private static void sort1(int x[], int off, int len) {22 /*23 * 当待排序的数组中的元素个数小于 7 时采用插入排序 。24 * 25 * 尽管插入排序的时间复杂度为O(n^2),但是当数组元素较少时 插入排序优于快速排序因为这时快速排序的递归操作影响性能。26 */27 if (len 7) {28 for (int i off; i len off; i)29 for (int j i; j off x[j - 1] x[j]; j--)30 swap(x, j, j - 1);31 return;32 }33 /*34 * 当待排序的数组中的元素个数大于 或等于7 时采用快速排序 。35 * 36 * Choose a partition element, v37 * 选取一个划分元V38 * 39 * 较好的选择了划分元(基准元素)。能够将数组分成大致两个相等的部分避免出现最坏的情况。例如当数组有序的的情况下40 * 选择第一个元素作为划分元将使得算法的时间复杂度达到O(n^2).41 */42 // 当数组大小为size7时 取数组中间元素作为划分元。43 int m off (len 1);44 // 当数组大小 7size40时取首、中、末 三个元素中间大小的元素作为划分元。45 if (len 7) {46 int l off;47 int n off len - 1;48 /*49 * 当数组大小 size40 时 从待排数组中较均匀的选择9个元素50 * 选出一个伪中数做为划分元。51 */52 if (len 40) {53 int s len / 8;54 l med3(x, l, l s, l 2 * s);55 m med3(x, m - s, m, m s);56 n med3(x, n - 2 * s, n - s, n);57 }58 // 取出中间大小的元素的位置。59 m med3(x, l, m, n); // Mid-size, med of 360 }61 62 //得到划分元V63 int v x[m];64 65 // Establish Invariant: v* (v)* (v)* v*66 int a off, b a, c off len - 1, d c;67 while (true) {68 while (b c x[b] v) {69 if (x[b] v)70 swap(x, a, b);71 b;72 }73 while (c b x[c] v) {74 if (x[c] v)75 swap(x, c, d--);76 c--;77 }78 if (b c)79 break;80 swap(x, b, c--);81 }82 // Swap partition elements back to middle83 int s, n off len;84 s Math.min(a - off, b - a);85 vecswap(x, off, b - s, s);86 s Math.min(d - c, n - d - 1);87 vecswap(x, b, n - s, s);88 // Recursively sort non-partition-elements89 if ((s b - a) 1)90 sort1(x, off, s);91 if ((s d - c) 1)92 sort1(x, n - s, s);93 }94 95 /**96 * Swaps x[a] with x[b].97 */98 private static void swap(int x[], int a, int b) {99 int t x[a];
100 x[a] x[b];
101 x[b] t;
102 }
103
104 /**
105 * Swaps x[a .. (an-1)] with x[b .. (bn-1)].
106 */
107 private static void vecswap(int x[], int a, int b, int n) {
108 for (int i0; in; i, a, b)
109 swap(x, a, b);
110 }
111
112 /**
113 * Returns the index of the median of the three indexed integers.
114 */
115 private static int med3(int x[], int a, int b, int c) {
116 return (x[a] x[b] ? (x[b] x[c] ? b : x[a] x[c] ? c : a)
117 : (x[b] x[c] ? b : x[a] x[c] ? c : a));
118 }
119
120 /**
121 * Check that fromIndex and toIndex are in range, and throw an
122 * appropriate exception if they arent.
123 */
124 private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
125 if (fromIndex toIndex)
126 throw new IllegalArgumentException(fromIndex( fromIndex
127 ) toIndex( toIndex ));
128 if (fromIndex 0)
129 throw new ArrayIndexOutOfBoundsException(fromIndex);
130 if (toIndex arrayLen)
131 throw new ArrayIndexOutOfBoundsException(toIndex);
132 }
133 } 测试代码如下 1 package com.test;2 3 import com.util.ArraysPrimitive;4 5 public class ArraysTest {6 public static void main(String[] args) {7 int [] a{15,93,15,41,6,15,22,7,15,20};8 ArraysPrimitive.sort(a);9 for(int i0;ia.length;i){
10 System.out.print(a[i],);
11 }
12 //结果6,7,15,15,15,15,20,22,41,93,
13 }
14 } 2、对于Object类型源码分析如下 部分源代码二如下 1 package com.util;2 3 import java.lang.reflect.Array;4 5 public class ArraysObject {6 private static final int INSERTIONSORT_THRESHOLD 7;7 8 private ArraysObject() {}9 10 public static void sort(Object[] a) {11 //java.lang.Object.clone()理解深表复制和浅表复制12 Object[] aux (Object[]) a.clone();13 mergeSort(aux, a, 0, a.length, 0);14 }15 16 public static void sort(Object[] a, int fromIndex, int toIndex) {17 rangeCheck(a.length, fromIndex, toIndex);18 Object[] aux copyOfRange(a, fromIndex, toIndex);19 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);20 }21 22 /**23 * Src is the source array that starts at index 0 24 * Dest is the (possibly larger) array destination with a possible offset 25 * low is the index in dest to start sorting 26 * high is the end index in dest to end sorting 27 * off is the offset to generate corresponding low, high in src28 */29 private static void mergeSort(Object[] src, Object[] dest, int low,30 int high, int off) {31 int length high - low;32 33 // Insertion sort on smallest arrays34 if (length INSERTIONSORT_THRESHOLD) {35 for (int i low; i high; i)36 for (int j i; j low 37 ((Comparable) dest[j - 1]).compareTo(dest[j]) 0; j--)38 swap(dest, j, j - 1);39 return;40 }41 42 // Recursively sort halves of dest into src43 int destLow low;44 int destHigh high;45 low off;46 high off;47 /*48 * 无符号右移运算符49 * expression1 expresion2expression1的各个位向右移expression250 * 指定的位数。右移后左边空出的位数用0来填充。移出右边的位被丢弃。51 * 例如-142 结果为107374182052 */53 int mid (low high) 1;54 mergeSort(dest, src, low, mid, -off);55 mergeSort(dest, src, mid, high, -off);56 57 // If list is already sorted, just copy from src to dest. This is an58 // optimization that results in faster sorts for nearly ordered lists.59 if (((Comparable) src[mid - 1]).compareTo(src[mid]) 0) {60 System.arraycopy(src, low, dest, destLow, length);61 return;62 }63 64 // Merge sorted halves (now in src) into dest65 for (int i destLow, p low, q mid; i destHigh; i) {66 if (q high || p mid67 ((Comparable) src[p]).compareTo(src[q]) 0)68 dest[i] src[p];69 else70 dest[i] src[q];71 }72 }73 74 /**75 * Check that fromIndex and toIndex are in range, and throw an appropriate76 * exception if they arent.77 */78 private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {79 if (fromIndex toIndex)80 throw new IllegalArgumentException(fromIndex( fromIndex81 ) toIndex( toIndex ));82 if (fromIndex 0)83 throw new ArrayIndexOutOfBoundsException(fromIndex);84 if (toIndex arrayLen)85 throw new ArrayIndexOutOfBoundsException(toIndex);86 }87 88 public static T T[] copyOfRange(T[] original, int from, int to) {89 return copyOfRange(original, from, to, (ClassT[]) original.getClass());90 }91 92 public static T, U T[] copyOfRange(U[] original, int from, int to,93 Class? extends T[] newType) {94 int newLength to - from;95 if (newLength 0)96 throw new IllegalArgumentException(from to);97 T[] copy ((Object) newType (Object) Object[].class)98 ? (T[]) new Object[newLength]99 : (T[]) Array.newInstance(newType.getComponentType(), newLength);
100 System.arraycopy(original, from, copy, 0,
101 Math.min(original.length - from, newLength));
102 return copy;
103 }
104
105 /**
106 * Swaps x[a] with x[b].
107 */
108 private static void swap(Object[] x, int a, int b) {
109 Object t x[a];
110 x[a] x[b];
111 x[b] t;
112 }
113 } 测试代码如下 1 package com.test;2 3 import com.util.ArraysObject;4 5 public class ArraysObjectSortTest {6 public static void main(String[] args) {7 Student stu1new Student(1001,100.0F);8 Student stu2new Student(1002,90.0F);9 Student stu3new Student(1003,90.0F);
10 Student stu4new Student(1004,95.0F);
11 Student[] stus{stu1,stu2,stu3,stu4};
12 //Arrays.sort(stus);
13 ArraysObject.sort(stus);
14 for(int i0;istus.length;i){
15 System.out.println(stus[i].getId() : stus[i].getScore());
16 }
17 /* 1002 : 90.0
18 * 1003 : 90.0
19 * 1004 : 95.0
20 * 1001 : 100.0
21 */
22 }
23 }
24 class Student implements ComparableStudent{
25 private int id; //学号
26 private float score; //成绩
27 public Student(){}
28 public Student(int id,float score){
29 this.idid;
30 this.scorescore;
31 }
32 Override
33 public int compareTo(Student s) {
34 return (int)(this.score-s.getScore());
35 }
36 public int getId() {
37 return id;
38 }
39 public void setId(int id) {
40 this.id id;
41 }
42 public float getScore() {
43 return score;
44 }
45 public void setScore(float score) {
46 this.score score;
47 }
48 } 辅助理解代码 1 package com.lang;2 3 public final class System {4 //System 类不能被实例化。 5 private System() {}6 //在 System 类提供的设施中有标准输入、标准输出和错误输出流对外部定义的属性7 //和环境变量的访问加载文件和库的方法还有快速复制数组的一部分的实用方法。8 /**9 * src and dest都必须是同类型或者可以进行转换类型的数组
10 * param src the source array.
11 * param srcPos starting position in the source array.
12 * param dest the destination array.
13 * param destPos starting position in the destination data.
14 * param length the number of array elements to be copied.
15 */
16 public static native void arraycopy(Object src, int srcPos, Object dest,
17 int destPos, int length);
18 }1 package com.lang.reflect;2 3 public final class Array {4 private Array() {}5 6 //创建一个具有指定的组件类型和维度的新数组。7 public static Object newInstance(Class? componentType, int length)8 throws NegativeArraySizeException {9 return newArray(componentType, length);
10 }
11
12 private static native Object newArray(Class componentType, int length)
13 throws NegativeArraySizeException;
14 } 二、Arrays.asList 慎用ArrayList的contains方法使用HashSet的contains方法代替 在启动一个应用的时候发现其中有一处数据加载要数分钟刚开始以为是需要load的数据比较多的缘故查了一下数据库有6条左右但是单独写了一个数据读取的方法将这6万多条全部读过来却只需要不到10秒钟就觉得这里面肯定有问题于是仔细看其中的逻辑其中有一段数据去重的逻辑就是记录中存在某几个字段相同的就认为是重复数据就需要将重复数据给过滤掉。这里就用到了一个List来存放这几个字段所组成的主键如果发现相同的就不处理代码无非就是下面这样 1 Liststring uniqueKeyList new ArrayListstring();
2 //......
3 if (uniqueKeyList.contains(uniqueKey)) {
4 continue; } 根据键去查找是不是已经存在了来判断是否重复数据。经过分析这一块耗费了非常多的时候于是就去查看ArrayList的contains方法的源码发现其最终会调用他本身的indexOf方法 7public int indexOf(Object elem) {
8 if (elem null) {
9 for (int i 0; i size; i)
10 if (elementData[i]null)
11 return i;
12 } else {
13 for (int i 0; i size; i)
14 if (elem.equals(elementData[i]))
15 return i;
16 }
17 return -1;
18 } 原来在这里他做的是遍历整个list进行查找最多可能对一个键的查找会达到6万多次也就是会扫描整个List验怪会这么慢了。 于是将原来的List替换为Set Setstring uniqueKeySet new HashSetstring();
//......
if (uniqueKeySet.contains(uniqueKey)) { continue;
} 速度一下就上去了在去重这一块最多花费了一秒钟为什么HashSet的速度一下就上去了那是因为其内部使用的是Hashtable这是HashSet的contains的源码 public boolean contains(Object o) { return map.containsKey(o);
} 关于UnsupportedOperationException异常 在使用Arrays.asList()后调用addremove这些method时出现java.lang.UnsupportedOperationException异常。这是由于Arrays.asList() 返回java.util.Arrays$ArrayList 而不是ArrayList。Arrays$ArrayList和ArrayList都是继承AbstractListremoveadd等method在AbstractList中是默认throw UnsupportedOperationException而且不作任何操作。ArrayList override这些method来对list进行操作但是Arrays$ArrayList没有override remove()add()等所以throw UnsupportedOperationException。 转载于:https://www.cnblogs.com/ITtangtang/p/3948765.html
