java排列组合工具类 java字符串排列组合算法 _生活百科

1. 引言排序是一个Java开发者，在日常开发过程中随处可见的开发内容，Java中有丰富的API可以调用使用。在Java语言中，作为集合工具类的排序方法，必定要做到通用、高效、实用这几点特征。使用什么样排序算法会比较合适，能够做到在尽量降低时间、空间复杂度的情况下，又要兼顾保证稳定性，达到优秀的性能。可能从性能角度出发首先会想到的是快速排序，或者归并排序。作为jdk提供的通用排序功能，使用又如此频繁，肯定有独特之处，一起来看学习下期中的奥秘。
文中不会过多的介绍几大基本排序算法的方式、由来和思想，主要精力集中在一块探讨java中排序方法所使用的算法，以及那些是值得我们学习和借鉴的内容。文中如有理解和介绍的错误，一起学习，一起探讨，一起进步。
2. 案例日常使用最为频繁的排序，莫过于如下代码案例，给定一个现有的序列进行一定规则下的排序，配合java8的stream特性，可以很方便的对一个集合进行排序操作（排序规则只是对排序对象及排序方案的限定，不在本文讨论范围内）。
List list = Arrays.asList(10, 50, 5, 14, 16, 80);System.out.println(list.stream().sorted().collect(Collectors.toList()));在代码执行的过程中SortedOps.java类中 Arrays.sort(array, 0, offset, comparator); 执行了Array集合类型的sort排序算法。
@Overridepublic void end() {Arrays.sort(array, 0, offset, comparator);downstream.begin(offset);if (!cancellationWasRequested) {for (int i = 0; i < offset; i++)downstream.accept(array[i]);}else {for (int i = 0; i < offset && !downstream.cancellationRequested(); i++)downstream.accept(array[i]);}downstream.end();array = null;}如果使用Collections.sort() 方法如下打印 list1 和 list2 结果一样，且调用的都是 Arrays 集合类中的 sort 方法。
List list1 = Arrays.asList(10, 50, 5, 14, 16, 80);System.out.println(list1.stream().sorted().collect(Collectors.toList()));List list2 = Lists.newArrayList();list2.addAll(list1);Collections.sort(list2);System.out.println(list2);// 输出：// [5, 10, 14, 16, 50, 80]// [5, 10, 14, 16, 50, 80]2. Collections.sort 方法介绍Collections类中关于sort方法定义如下：
public static <T extends Comparable<? super T>> void sort(List list) {list.sort(null);}通过该方法注释，查看到有三项值得关注的信息，大概意思是该方法实现了稳定且默认升序排序的功能。
1. Sorts the specified list into ascending order, according to the Comparable natural ordering of its elements.2. This sort is guaranteed to be stable equal elements will not be reordered as a result of the sort.3. The specified list must be modifiable, but need not be resizable.进入sort，代码进入到List类的sort方法，发现方法将入参list先转为了数组Object[]，之后利用Arrays.sort进行排序。
【java排列组合工具类 java字符串排列组合算法】default void sort(Comparator<? super E> c) {Object[] a = this.toArray();Arrays.sort(a, (Comparator) c);ListIterator i = this.listIterator();for (Object e : a) {i.next();i.set((E) e);}}首先在这里思考一个问题为什么要转为数组，问题答案已经在方法的英文注释中说明白了。
* The default implementation obtains an array containing all elements in* this list, sorts the array, and iterates over this list resetting each* element from the corresponding position in the array. (This avoids the* n2 log(n) performance that would result from attempting* to sort a linked list in place.)是为了避免直接对List的链表进行排序，从而耗费O(n2logn) 时间复杂度。当然这里在this.toArray()时，为了将list强行变为数组会损失一些性能和空间开销，源码中使用了System.arraycopy调用底层操作系统方法进行数据复制，详细内容可以查看相关实现。继续进入Arrays类的sort方法定义中，我们没有使用比较器，
LegacyMergeSort.userRequested表示进入老的归并排序算法，默认是关闭的，直接进入本文重点关注的TimSort.sort(…)方法。
public static <T> void sort(T[] a, Comparator<? super T> c) {if (c == null) {sort(a);} else {if (LegacyMergeSort.userRequested)legacyMergeSort(a, c);elseTimSort.sort(a, 0, a.length, c, null, 0, 0);}}3. TimSort 算法介绍Timsort是一个自适应的、混合的、稳定的排序算法，是由Tim Peter于2002年发明的，最早应用在Python中，现在广泛应用于Python、Java、Android 等语言与平台中，作为基础的排序算法使用。其中Java语言的Collection.sort在JDK1.6使用的是普通的归并排序，归并排序虽然时间复杂度低，但是空间复杂度要求较高，所以从JDK1.7开始就更改为了TimSort算法。