排序
Arrays.sort()方法，对于基本数据类型采用DualPivotQuicksort（多路快排）进行排序，对于引用类型的数组，采用MergeSort（归并排序）进行排序，下面我们分别来讲一下这两类排序算法。
对基本类型数组的排序
Java中的八种基本数据类型，除了boolean，其它七种都是可以且有需求进行排序的，如果一个数组是单一的基础类型，形如int[] data, long data[]都可以直接使用Arrays.sort()进行排序。对于所有可排序的基本类型，都是采用DualPivotQuicksort来进行排序的。首先来看个例子：
package com.adam.java.algo.arrays;
import java.util.Arrays;
import org.junit.Test;
public class ArraysBasicTest {
@Test
public void testSortInteger() {
int data[] = { 10, 8, 9, 1, 2, 5, 98, 3, 7, 66 };
Arrays.sort(data);
for (int i : data) {
System.out.print(i + " ");
}
}
@Test
public void testSortChar() {
char data[] = { 'D', 'B', 'E', 'C', 'H', 'A', 'Y', 'G', 'I', 'O' };
Arrays.sort(data);
for (char i : data) {
System.out.print(i + " ");
}
}
}
输出：
1 2 3 5 7 8 9 10 66 98
A B C D E G H I O Y
这里我们要看一下Arrays.sort()采用的算法了，我们查看下JDK源码。
/**
* Sorts the specified array into ascending numerical order.
*
* <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
发现所有的基本排序都是直接使用DualPivotQuicksort.sort()进行的，因此，我们有必要了解一下DualPivotQuicksort的原理。基本思想就是：
元素个数从1-47，则直接使用插入排序进行排序。
元素个数从47-286，则使用多路快速排序。
元素个数大于286，则使用归并排序
这里我们研究下多路快排的原理，首先我们回顾一下经典快排是怎么实现的。
经典快排实现思路：
1. 找一个中轴，一般情况选取数组的第一个元素。
2. 定义两个指针，分别指向最左边和最右边，从右边开始遍历，如果大于中轴，则右边指针左移一位，如果小于中轴，则互换位置；同理再从左边开始和中轴比较，如果小于中轴，指针向右移动，如果大于中轴，则互换位置。
3. 一趟排序下来，中轴左边的都小于中轴，右边的都大于中轴。
4.递归的对子数组进行如上操作，不稳定，时间复杂度最优情况O(nlogn)，最坏情况为基本有序时为O(n2)。关于快排的详细说明，请参考另一篇博文。
多路快排实现思路：
1. 选取两个中轴P1, P2。
2. 假设P1<P2，否则交换。
3. 过程中原数组会分为四个部分：小于中轴1，大于中轴2，介于两个中轴之间，未排序部分（刚开始除了两个中轴，其它元素都属于这部分）。
4. 开始后，从未排序部分选取一个数，和两个中轴作比较，然后放到合适的位置，一直到未排序部分无数据，结束一趟排序。
5. 递归地处理子数组，稳定排序，时间复杂度稳定为O(nlogn)。
对引用类型的数组排序
我们举个例子，对User类型的数组，根据年龄进行排序，此处用到Comparator接口，更多关于Comparator的介绍，请点击。
新建一个User类：
package com.adam.java.algo.arrays;
public class User {
private String name;
private String gender;
private int age;
public User(String name, String gender, int age) {
this.name = name;
this.gender = gender;
this.age = age;
}
/**
* @return the name
*/
public String getName() {
return name;
}
/**
* @param name
* the name to set
*/
public void setName(String name) {
this.name = name;
}
/**
* @return the gender
*/
public String getGender() {
return gender;
}
/**
* @param gender
* the gender to set
*/
public void setGender(String gender) {
this.gender = gender;
}
/**
* @return the age
*/
public int getAge() {
return age;
}
/**
* @param age
* the age to set
*/
public void setAge(int age) {
this.age = age;
}
}
再建一个排序类：
package com.adam.java.algo.arrays;
import java.util.Comparator;
public class UserComparator implements Comparator<User> {
@Override
public int compare(User o1, User o2) {
return o1.getAge() - o2.getAge();
}
}
测试：
package com.adam.java.algo.arrays;
import java.util.Arrays;
public class ArraysTest {
public static void main(String[] args) {
User[] users = new User[]{new User("egg", "male", 26), new User("Kity", "Female", 25), new User("Pole", "male", 23), new User("Jack", "male", 28)};
Arrays.sort(users, new UserComparator());
for (User user : users) {
System.out.println("name: " + user.getName() + " ,age: "+user.getAge());
}
}
}
输出：
name: Pole ,age: 23
name: Kity ,age: 25
name: egg ,age: 26
name: Jack ,age: 28
这就是一个简单的对引用类型的数组排序的例子，在JDK1.8中，对引用类型的排序，采用的归并排序的算法。
在JDK1.8中，对于排序方法，还引入了parallelSort()，每个sort()都有对应的并行排序方法，当数组元素个数大于2的13次（8196）后采用parallelSort()。
搜索
在用二分搜索对一个已经有序的数组进行查找，如果存在，返回key在该数组中的位置，如果不存在，返回负数，值为：-插入点-1，举个例子：
假设一个排好序的数组是：1,6,8,10,12，如果key为7，则返回值为-3，因为7应该插入到6,8之间，所以插入点为2（下标从0开始），所以返回值为-2-1=-3。
ArrayToList
这方面，是将一个数组，转换成一个list形式，注意：通常情况下，如果该数组是int型的，如int[[ data，这种情况会出现并不是直接将该数组中的所有元素转成新的list的所有元素，而是将整个数组，转成list的一个元素，这是一种特殊情况，将类型int改成Integer就可以避免了。此处感谢网友@Java我人生指正！
/**
* Returns a fixed-size list backed by the specified array. (Changes to
* the returned list "write through" to the array.) This method acts
* as bridge between array-based and collection-based APIs, in
* combination with {@link Collection#toArray}. The returned list is
* serializable and implements {@link RandomAccess}.
*
* <p>This method also provides a convenient way to create a fixed-size
* list initialized to contain several elements:
* <pre>
* List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
* </pre>
*
* @param <T> the class of the objects in the array
* @param a the array by which the list will be backed
* @return a list view of the specified array
*/
@SafeVarargs
@SuppressWarnings("varargs")
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
根据注释得知，返回的新list是个定长的list，而且并不可以就行添加或者删除元素，否则报：java.lang.UnsupportedOperationException异常。这是为什么？因为此处的ArrayList并非我们常用的java.util.ArrayList类，而是Arrays类的一个内部类，因为继承了AbstractList，所有可以和list相互转换，但是不具备add和remove等操作。
CopyOf
Arrays.copyOf()用来进行数组的复制，返回一个全新的数组，可以传入一个参数来定义新数组的大小，如果传入的数小于原来的数组长度，则直接把原数组多余的部分剪掉，如果传入的值大于原数组，则新数组多余的部分补默认值（对于int类型的，补0）。
网友评论