Java如何实现集合的排序?- 本文以对Student对象集合为例进行排序Java通过Collections.sort(List<Student> stuList)和Collections.sort(List<Student> stuList,Compar ...
Java如何实现集合的排序?
- 本文以对Student对象集合为例进行排序
Java通过Collections.sort(List<Student> stuList)和Collections.sort(List<Student> stuList,Comparator c)两种方法实现排序。
用Collections.sort(List list) 方法实现排序:
step1: 确保Student类实现了Comparable接口,并重写了compareTo()方法。
step2:调用Collections.sort(List list) 方法进行排序。
1 public class Student implements Comparable<Student> { 2 3 private int age; 4 5 public Student(int age) { 6 this.age = age; 7 } 8 9 public int getAge() {10 return age;11 }12 13 @Override14 public int compareTo(Student student) { // 重写compareTo方法15 16 return (this.age < student.age) ? -1 : ((this.age == student.age) ? 0 : 1);17 }18 19 20 public static void main(String[] args) {21 List<Student> stuList = new ArrayList();22 stuList.add(new Student(5));23 stuList.add(new Student(3));24 stuList.add(new Student(7));25 stuList.add(new Student(2));26 stuList.add(new Student(4));27 stuList.add(new Student(6));28 stuList.add(new Student(1));29 30 Collections.sort(stuList); // 调用排序方法31 32 for (Student student : stuList) {33 System.out.println(student.getAge());34 }35 }36 }
原理分析:
step1: Collections类调用List.sort(Comparator c)方法,比较器c赋值为null.
1 public static <T extends Comparable<? super T>> void sort(List<T> list) {2 list.sort(null);3 }
step2: List接口中的sort方法将stuList集合转换成数组,通过Arrays.sort()方法对其进行排序,并将排序后的元素替换stuList中每个元素。
1 default void sort(Comparator<? super E> c) {2 Object[] a = this.toArray();3 Arrays.sort(a, (Comparator) c);4 ListIterator<E> i = this.listIterator();5 for (Object e : a) {6 i.next();7 i.set((E) e);8 }9 }
那到底时在哪里调用的compareTo方法的呢?
进入Arrays.sort()方法:
1 public static <T> void sort(T[] a, Comparator<? super T> c) { 2 if (c == null) { 3 sort(a); 4 } else { 5 if (LegacyMergeSort.userRequested) 6 legacyMergeSort(a, c); 7 else 8 TimSort.sort(a, 0, a.length, c, null, 0, 0); 9 }10 }
没有制定比较器,因此c==null为true,执行sort(a)方法:
1 public static void sort(Object[] a) {2 if (LegacyMergeSort.userRequested)3 legacyMergeSort(a);4 else5 ComparableTimSort.sort(a, 0, a.length, null, 0, 0);6 }
LegacyMergeSort.userRequested默认为false,表示是否使用传统归并排序,传统归并排序在1.5及之前是默认排序方法,1.5之后默认执行ComparableTimSort.sort()方法。除非程序中强制要求使用传统归并排序。语句如下:
System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
所以继续看ComparableTimSort.sort()方法:
1 static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) { 2 assert a != null && lo >= 0 && lo <= hi && hi <= a.length; 3 4 int nRemaining = hi - lo; 5 if (nRemaining < 2) 6 return; // Arrays of size 0 and 1 are always sorted 7 8 // If array is small, do a "mini-TimSort" with no merges 9 if (nRemaining < MIN_MERGE) {10 int initRunLen = countRunAndMakeAscending(a, lo, hi);11 binarySort(a, lo, hi, lo + initRunLen);12 return;13 }14 15 /**16 * March over the array once, left to right, finding natural runs,17 * extending short natural runs to minRun elements, and merging runs18 * to maintain stack invariant.19 */20 ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);21 int minRun = minRunLength(nRemaining);22 do {23 // Identify next run24 int runLen = countRunAndMakeAscending(a, lo, hi);25 26 // If run is short, extend to min(minRun, nRemaining)27 if (runLen < minRun) {28 int force = nRemaining <= minRun ? nRemaining : minRun;29 binarySort(a, lo, lo + force, lo + runLen);30 runLen = force;31 }32 33 // Push run onto pending-run stack, and maybe merge34 ts.pushRun(lo, runLen);35 ts.mergeCollapse();36 37 // Advance to find next run38 lo += runLen;39 nRemaining -= runLen;40 } while (nRemaining != 0);41 42 // Merge all remaining runs to complete sort43 assert lo == hi;44 ts.mergeForceCollapse();45 assert ts.stackSize == 1;46 }
line4的nRemaining表示没有排序的对象个数,方法执行前,如果这个数小于2,就不需要排序了。
如果2<= nRemaining <=32,即MIN_MERGE的初始值,表示需要排序的数组是小数组,可以使用mini-TimSort方法进行排序,否则需要使用归并排序。
mini-TimSort排序方法:先找出数组中从下标为0开始的第一个升序序列,或者找出降序序列后转换为升序重新放入数组,将这段升序数组作为初始数组,将之后的每一个元素通过二分法排序插入到初始数组中。注意,这里就调用到了我们重写的compareTo()方法了。
获取初始数组的方法:
1 private static int countRunAndMakeAscending(Object[] a, int lo, int hi) { 2 assert lo < hi; 3 int runHi = lo + 1; 4 if (runHi == hi) 5 return 1; 6 7 // Find end of run, and reverse range if descending 8 if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending 9 while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)10 runHi++;11 reverseRange(a, lo, runHi);12 } else { // Ascending13 while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)14 runHi++;15 }16 17 return runHi - lo;18 }
根据程序中举例,a[1].compareTo(a[0]) <0,所以向下循环查看a[2].compareTo(a[1]) <0、a[3].compareTo(a[2]) <0等等是否成立,我们发现a[2].compareTo(a[1]) <0不成立,所以循环终止,获取到最长的降序数组为a[]{5,3},再调用reverseRange()方法将其升序排列为a[]{3,5},作为初始数组,initRunLen=2。随后进行二分法插入操作,代码如下:
1 private static void binarySort(Object[] a, int lo, int hi, int start) { 2 assert lo <= start && start <= hi; 3 if (start == lo) 4 start++; 5 for ( ; start < hi; start++) { 6 Comparable pivot = (Comparable) a[start]; 7 8 // Set left (and right) to the index where a[start] (pivot) belongs 9 int left = lo;10 int right = start;11 assert left <= right;12 /*13 * Invariants:14 * pivot >= all in [lo, left).15 * pivot < all in [right, start).16 */17 while (left < right) {18 int mid = (left + right) >>> 1;19 if (pivot.compareTo(a[mid]) < 0)20 right = mid;21 else22 left = mid + 1;23 }24 assert left == right;25 26 /*27 * The invariants still hold: pivot >= all in [lo, left) and28 * pivot < all in [left, start), so pivot belongs at left. Note29 * that if there are elements equal to pivot, left points to the30 * first slot after them -- that's why this sort is stable.31 * Slide elements over to make room for pivot.32 */33 int n = start - left; // The number of elements to move34 // Switch is just an optimization for arraycopy in default case35 switch (n) {36 case 2: a[left + 2] = a[left + 1];37 case 1: a[left + 1] = a[left];38 break;39 default: System.arraycopy(a, left, a, left + 1, n);40 }41 a[left] = pivot;42 }43 }
循环下标>=2的所有元素,通过二分法将其插入到初始数组中的适当位置,这样,通过调用元素的compareTo()方法进行排序的功能实现完毕。
用Collections.sort(List list,Comparator c) 方法实现排序:
该方法传入一个比较器,用于比较各元素的大小。该方法不需要元素实现Comparable接口,但需要一个实现Comparator接口的实现类来实例化一个比较器,注意,这里的Comparator是一个接口而非类。这里通常采用匿名内部类的方法。
1 Collections.sort(stuList, new Comparator<Student>() {2 @Override3 public int compare(Student stu1, Student stu2) {4 return (stu1.getAge() < stu2.getAge()) ? -1 : (stu1.getAge() == stu2.getAge() ? 0 : 1);5 }6 });
这种方法实现排序的方式与上述方法基本相同。
先调用Collections.sort()方法,传入集合和比较器,sort()方法调用List的sort方法,传入比较器。(同上step1)代码如下:
1 public static <T> void sort(List<T> list, Comparator<? super T> c) {2 list.sort(c);3 }
List中sort()方法调用Arrays.sort()方法,传入数组和比较器。(同上step2)
1 default void sort(Comparator<? super E> c) {2 Object[] a = this.toArray();3 Arrays.sort(a, (Comparator) c);4 ListIterator<E> i = this.listIterator();5 for (Object e : a) {6 i.next();7 i.set((E) e);8 }9 }
Arrays.sort方法调用TimSort.sort()方法,代码如下:
1 public static <T> void sort(T[] a, Comparator<? super T> c) { 2 if (c == null) { 3 sort(a); 4 } else { 5 if (LegacyMergeSort.userRequested) 6 legacyMergeSort(a, c); 7 else 8 TimSort.sort(a, 0, a.length, c, null, 0, 0); 9 }10 }
legacyMergeSort(a,c)和TimSort.sort()方法中与方法一不同的地方只有一点,即方法一中使用a.compareTo(b)进行比较而方法二中使用comparator.compare(a,b)进行比较,其他均相同。
1 private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi, 2 Comparator<? super T> c) { 3 assert lo < hi; 4 int runHi = lo + 1; 5 if (runHi == hi) 6 return 1; 7 8 // Find end of run, and reverse range if descending 9 if (c.compare(a[runHi++], a[lo]) < 0) { // Descending10 while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)11 runHi++;12 reverseRange(a, lo, runHi);13 } else { // Ascending14 while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)15 runHi++;16 }17 18 return runHi - lo;19 }
总结:
1.Collections.sort()排序有两种实现方式,一是让元素类实现Comparable接口并覆盖compareTo()方法,二是给Collecitons.sort()方法传入比较器,通常采用匿名内部内的方式传入。
2.Collections.sort()通过调用Arrays.sort()方法进行排序,在Java1.6+中,如果集合大小<32则采用Tim-Sort算法,如果>=32则采用归并排序。
海外公司注册、海外银行开户、跨境平台代入驻、VAT、EPR等知识和在线办理:https://www.xlkjsw.com
原标题:Java集合排序功能实现分析
关键词:JAVA
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们:
admin#shaoqun.com
(#换成@)。